Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I M2320 #76 Aug 15 2024 10:58:21
%S 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 67,71,76,80,85,90,92,96,102,106,110,113,117,122,127
%N Maximum number of edges in an n-node squarefree graph, or, in a graph containing no 4-cycle, or no C_4.
%C Keywords to help find this entry: C4-free. C_4-free, no 4-cycle, squarefree, quadrilateral-free, Zarankiewicz problem.
%C 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 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 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 P. Kovari, V. T. Sos, and P. Turan. On a problem of K. Zarankiewicz, Colloq. Math. (4th ed.), 3 (1954), pp. 50-57.
%D Brendan McKay, personal communication.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H 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 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 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 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 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 Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/extremal.html">Extremal Graphs and Turan numbers</a>.
%F 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 a(n) = A191965(n)/2. - _Max Alekseyev_, Apr 02 2022
%F For n > 2, a(n) <= floor(a(n-1) * n / (n-2)). - _Max Alekseyev_, Jan 26 2023
%Y See A335820 for the number of graphs that achieve a(n).
%K nonn,more
%O 1,3
%A _N. J. A. Sloane_
%E a(23)-a(31) from _Michel Marcus_, Jul 23 2014
%E a(32)-a(39) from _Brendan McKay_, Mar 08 2022
%E a(40) from _Brendan McKay_, communicated by _Max Alekseyev_, Mar 13 2023