|
|
A006855
|
|
Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.
(Formerly M2320)
|
|
6
|
|
|
0, 1, 3, 4, 6, 7, 9, 11, 13, 16, 18, 21, 24, 27, 30, 33, 36, 39, 42, 46, 50, 52, 56, 59, 63, 67, 71, 76, 80, 85, 90, 92, 96, 102, 106, 110, 113, 117, 122, 127
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Keywords to help find this entry: C4-free. C_4-free, no 4-cycle, squarefree, quadrilateral-free, Zarankiewicz problem.
Lower bounds that have a good chance of being exact: a(41) >= 132, a(42) >= 137, a(43) >= 142, a(44) >= 148, a(45) >= 154, a(46) >= 157, a(47) >= 163, a(48) >= 168, a(49) >= 174. - Brendan McKay, Mar 08 2022
Upper bounds: a(41) <= 133, a(42) <= 139, a(43) <= 145, a(44) <= 151, a(45) <= 158, a(46) <= 165, a(47) <= 171, a(48) <= 176, a(49) <= 182. - Max Alekseyev, Jan 26 2023
|
|
REFERENCES
|
M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999. Chap. 20 gives a simple proof of the upper bound (n/4)(sqrt(4n-3)+1) and of the fact that it is asymptotically tight. - Christopher E. Thompson, Aug 14 2001
P. Kovari, V. T. Sos, and P. Turan. On a problem of K. Zarankiewicz, Colloq. Math. (4th ed.), 3 (1954), pp. 50-57.
Brendan McKay, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(n) <= n^(3/2)*(1/2 + o(1)) [Kovari, Sos, Turan]. But the upper bound mentioned in the Aigner-Ziegler reference (see above) is stronger. - N. J. A. Sloane, Mar 07 2022
For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - Max Alekseyev, Jan 26 2023
|
|
CROSSREFS
|
See A335820 for the number of graphs that achieve a(n).
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|