cp's OEIS Frontend

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

%I A006855 M2320 #76 Aug 15 2024 10:58:21
%S A006855 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,
%T A006855 67,71,76,80,85,90,92,96,102,106,110,113,117,122,127
%N A006855 Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.
%C A006855 Keywords to help find this entry: C4-free. C_4-free, no 4-cycle, squarefree, quadrilateral-free, Zarankiewicz problem.
%C A006855 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
%C A006855 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
%D A006855 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
%D A006855 P. Kovari, V. T. Sos, and P. Turan. On a problem of K. Zarankiewicz, Colloq. Math. (4th ed.), 3 (1954), pp. 50-57.
%D A006855 Brendan McKay, personal communication.
%D A006855 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006855 Max A. Alekseyev, <a href="https://arxiv.org/abs/2303.02872">On computing sets of integers with maximum number of pairs summing to powers of 2</a>, arXiv:2303.02872 [math.CO], 2023.
%H A006855 C. R. J. Clapham, A. Flockhart, and J. Sheehan, <a href="https://doi.org/10.1002/jgt.3190130107">Graphs without four-cycles</a>, J. Graph Theory 13 (1) (1989) 29-47
%H A006855 Zoltán Füredi, <a href="http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_C4abs.pdf">Quadrilateral-free graphs with maximum number of edges</a>, Extended abstract, Proceedings of the Japan Workshop on Graph Th. and Combinatorics, University, Yokohama, Japan 1994, pp. 13-22 (see Section 6).
%H A006855 Zoltán Füredi, <a href="https://doi.org/10.1006/jctb.1996.0052">On the number of edges of quadrilateral-free graphs</a>, J. Combin. Theory (B) 68 (1996), 1-6.
%H A006855 Jie Ma and Tianchi Yang, <a href="https://arxiv.org/abs/2107.11601">Upper bounds on the extremal number of the 4-cycle</a>, arxiv:2107.11601 (2021).
%H A006855 Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/extremal.html">Extremal Graphs and Turan numbers</a>.
%F A006855 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
%F A006855 a(n) = A191965(n)/2. - _Max Alekseyev_, Apr 02 2022
%F A006855 For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - _Max Alekseyev_, Jan 26 2023
%Y A006855 See A335820 for the number of graphs that achieve a(n).
%K A006855 nonn,more
%O A006855 1,3
%A A006855 _N. J. A. Sloane_
%E A006855 a(23)-a(31) from _Michel Marcus_, Jul 23 2014
%E A006855 a(32)-a(39) from _Brendan McKay_, Mar 08 2022
%E A006855 a(40) from _Brendan McKay_, communicated by _Max Alekseyev_, Mar 13 2023