cp's OEIS Frontend

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

%I A072567 #56 Apr 04 2022 09:05:11
%S A072567 1,3,6,9,12,16,21,24,29,34,39,45,52,56,61,67,74,81,88,96,105,108,115,
%T A072567 122
%N A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.
%C A072567 Proving a(13) < 53 and finding a(7) were problems at the 1975 USSR National Olympiad and are presented in the Ross Honsberger 1985 book "Mathematical Gems III" (see links). - _Tanya Khovanova_, Oct 12 2007
%C A072567 The growth rate of a(n) is O(n^{3/2}). For a lower bound, take the incidence graph of a finite projective plane. For prime powers q, you get a(q^2+q+1) >= (q+1)(q^2+q+1). For an upper bound, the matrix is an adjacency matrix of a bipartite graph of girth 6. These have at most O(n^{3/2}) edges. - _Peter Shor_, Jul 01 2013
%C A072567 Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - _Max Alekseyev_, Apr 03 2022
%H A072567 Brendan McKay's <a href="https://mathoverflow.net/q/99770">Largest graphs of girth at least 6</a>, MathOverflow, 2012. [The number of edges given there for even n seem to be the terms of this sequence. They are certainly bounded above by them.]
%H A072567 Stefan Neuwirth, <a href="http://arxiv.org/abs/math/0102210">The size of bipartite graphs with girth eight</a>, arXiv:math/0102210 [math.CO], 2001.
%H A072567 I. Reiman, <a href="http://dx.doi.org/10.1007/BF02020254 ">Über ein Problem von K. Zarankiewicz</a>, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 3-4 , pp 269-273.
%H A072567 R. Honsberger, <a href="/A072567/a072567.pdf">Two Problems from the 1974 USSR National Olympiad (#4 and #9)</a>. Excerpt from "Mathematical Gems III" book, 1985. [In fact, these problems are from the olympiad of 1975, not 1974, and were published as Problem M335 in Kvant 7 (1975).]
%H A072567 E. Belaga, <a href="https://kvant.ras.ru/1976/03/resheniya_zadachnika_kvanta_ma.htm">Solution to Problem M335</a>, Kvant 3 (1976), 42-44. (in Russian)
%F A072567 For prime powers q, a(q^2+q+1) = (q+1)(q^2+q+1). It follows from equality case of Reiman inequality. For example, a(21)=105 and a(31)=186. - _Senya Karpenko_, Jul 23 2014
%F A072567 a(n) = A001197(n) - 1 for n>=2. - _Rob Pratt_, Aug 09 2019
%e A072567 Examples of a(2)=3, a(3)=6, and a(4)=9:
%e A072567 11   110   1110
%e A072567 10   101   1001
%e A072567      011   0101
%e A072567            0011
%e A072567 a(4)=9 is also achieved at a symmetric matrix:
%e A072567 0111
%e A072567 1010
%e A072567 1100
%e A072567 1001 - _Max Alekseyev_, Apr 03 2022
%Y A072567 Cf. A001197.
%K A072567 nonn,nice,hard,more
%O A072567 1,2
%A A072567 Xuli Le (leshlie(AT)eyou.com), Jun 21 2002
%E A072567 a(1) = 1 from _Don Reble_, Oct 13 2007
%E A072567 More terms (using formula and A001197) from _Rob Pratt_, Aug 09 2019
%E A072567 a(22)-a(24) from _Jeremy Tan_, Jan 23 2022
%E A072567 Edited by _Max Alekseyev_, Apr 03 2022