A006855 Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

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

• Max A. Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.
• C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without four-cycles, J. Graph Theory 13 (1) (1989) 29-47
• Zoltán Füredi, Quadrilateral-free graphs with maximum number of edges, Extended abstract, Proceedings of the Japan Workshop on Graph Th. and Combinatorics, University, Yokohama, Japan 1994, pp. 13-22 (see Section 6).
• Zoltán Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory (B) 68 (1996), 1-6.
• Jie Ma and Tianchi Yang, Upper bounds on the extremal number of the 4-cycle, arxiv:2107.11601 (2021).
• Brendan McKay, Extremal Graphs and Turan numbers.

Crossrefs

See A335820 for the number of graphs that achieve a(n).

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

a(n) = A191965(n)/2. - Max Alekseyev, Apr 02 2022

For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - Max Alekseyev, Jan 26 2023

Extensions

a(23)-a(31) from Michel Marcus, Jul 23 2014

a(32)-a(39) from Brendan McKay, Mar 08 2022

a(40) from Brendan McKay, communicated by Max Alekseyev, Mar 13 2023