login
A198787
Triangle read by rows: T(n,k) is the number of edges in the (n,k)-Turán graph.
1
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, 16, 21, 24, 25, 26, 27, 28, 0, 20, 27, 30, 32, 33, 34, 35, 36, 0, 25, 33, 37, 40, 41, 42, 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
OFFSET
1,5
COMMENTS
From Mikhail Lavrov, Apr 05 2021: (Start)
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.
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)
LINKS
Brian M. Scott, Deriving the number of edges in a Turán graph, Math StackExchange, 2015.
Eric Weisstein's World of Mathematics, Turan Graph
Eric Weisstein's World of Mathematics, Turans Theorem
Wikipedia, Turán graph
FORMULA
T(n,k) = (n^2 - (n mod k)*ceiling(n/k)^2 - (k-n mod k)*floor(n/k)^2)/2.
T(n,k) = (1-1/k)*n^2/2 - r(k-r)/(2k), where r = n mod k. - Mikhail Lavrov, Apr 05 2021
EXAMPLE
Triangle begins:
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;
...
The (5,2)-Turán graph is a complete bipartite graph with parts of size 2 and 3. It has 6 edges.
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.
MATHEMATICA
Flatten[Table[(n^2 - Mod[n, k] Ceiling[n/k]^2 - (k - Mod[n, k]) Floor[n/k]^2)/2, {n, 20}, {k, n}]]
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 *)
Flatten[Table[EdgeCount[TuranGraph[n, k]], {n, 20}, {k, n}]] (* Mikhail Lavrov, Apr 05 2021 *)
PROG
(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
CROSSREFS
Cf. A193331 (upper bound on this sequence).
Sequence in context: A007945 A011150 A100112 * A193331 A091246 A271439
KEYWORD
tabl,easy,nonn
AUTHOR
Chao Xu, Oct 29 2011
STATUS
approved