A193331 - OEIS

A193331

Triangle read by rows: T(n,k) = floor((k-1)*n^2/(2*k)) is an upper bound on the number of edges in the (n-k)-Turán graph.

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, 63, 64, 64, 65, 66

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

From Mikhail Lavrov, Apr 05 2021: (Start)

This is the bound derived from Turán's theorem; it is tight when n is divisible by k.

The exact number of edges is given by A198787(n,k). The difference between the two is at most k/8; in particular, A198787 and this sequence agree for all k<8. When n=12 and k=8, A198787 gives 62 and this sequence gives 63. (End)

LINKS

Reinhard Zumkeller, Rows n = 1..100 of triangle, flattened

P. Erdős, R. J. Faudree, and C. C. Rousseau, Extremal problems involving vertices and edges on odd cycles, Disc. Math. 101 (1992) 23-31.

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

FORMULA

T(n,k) = floor((k-1)*n^2/(2*k)).

EXAMPLE

The triangle T(n,k) begins:

0, 1;

0, 2, 3;