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)

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,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

Table of n, a(n) for n=1..40.

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.

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

Crossrefs

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

Sequence in context: A286809 A352178 A244239 * A301766 A229173 A066499

Adjacent sequences: A006852 A006853 A006854 * A006856 A006857 A006858

Keyword

nonn,more

Author

N. J. A. Sloane

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

Status

approved