|
%I #26 May 01 2021 22:01:51
%S 0,0,1,0,2,3,0,4,5,6,0,6,8,9,10,0,9,12,13,14,15,0,12,16,18,19,20,21,0,
%T 16,21,24,25,26,27,28,0,20,27,30,32,33,34,35,36,0,25,33,37,40,41,42,
%U 43,44,45,0,30,40,45,48,50,51,52,53,54,55,0,36,48,54,57,60,61,62,63,64,65,66,0,42
%N Triangle read by rows: T(n,k) is the number of edges in the (n,k)-Turán graph.
%C From _Mikhail Lavrov_, Apr 05 2021: (Start)
%C The (n,k)-Turán graph is a complete k-partite graph with n vertices, and all parts of order either floor(n/k) or ceiling(n/k). This graph maximizes the number of edges in any n-vertex graph with no (k+1)-clique.
%C A193331 is an upper bound on this sequence derived from Turán's theorem. The error term in this upper bound, before rounding, is r(k-r)/(2k), where r = n mod k. This is at most k/8, so in particular, A193331 and this sequence agree for all k < 8. When n=12 and k=8, A193331's upper bound gives 63 and this sequence gives 62. (End)
%H Brian M. Scott, <a href="https://math.stackexchange.com/q/1213738">Deriving the number of edges in a Turán graph</a>, Math StackExchange, 2015.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TuranGraph.html">Turan Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TuransTheorem.html">Turans Theorem </a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a>
%F T(n,k) = (n^2 - (n mod k)*ceiling(n/k)^2 - (k-n mod k)*floor(n/k)^2)/2.
%F T(n,k) = (1-1/k)*n^2/2 - r(k-r)/(2k), where r = n mod k. - _Mikhail Lavrov_, Apr 05 2021
%e Triangle begins:
%e 0,
%e 0, 1,
%e 0, 2, 3;
%e 0, 4, 5, 6;
%e 0, 6, 8, 9, 10;
%e 0, 9, 12, 13, 14, 15;
%e 0, 12, 16, 18, 19, 20, 21;
%e ...
%e The (5,2)-Turán graph is a complete bipartite graph with parts of size 2 and 3. It has 6 edges.
%e The (12,8)-Turán graph is a complete 8-partite graph with parts of size 2,2,2,2,1,1,1,1. It has 8 vertices of degree 10 and 4 vertices of degree 11, so it has 62 edges.
%t Flatten[Table[(n^2 - Mod[n, k] Ceiling[n/k]^2 - (k - Mod[n, k]) Floor[n/k]^2)/2, {n, 20}, {k, n}]]
%t Flatten[Table[(1 - 1/k)n^2/2 - (Mod[n,k](k - Mod[n,k]))/(2k), {n, 20}, {k, n}]] (* _Mikhail Lavrov_, Apr 05 2021 *)
%t Flatten[Table[EdgeCount[TuranGraph[n, k]], {n, 20}, {k, n}]] (* _Mikhail Lavrov_, Apr 05 2021 *)
%o (PARI) T(n,k) = {(n^2 - (n % k)*ceil(n/k)^2 - (k - n % k)*floor(n/k)^2)/2} \\ _Andrew Howroyd_, Apr 05 2021
%Y Cf. A193331 (upper bound on this sequence).
%K tabl,easy,nonn
%O 1,5
%A _Chao Xu_, Oct 29 2011
|
