login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle. 12

%I #56 Apr 04 2022 09:05:11

%S 1,3,6,9,12,16,21,24,29,34,39,45,52,56,61,67,74,81,88,96,105,108,115,

%T 122

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

%C 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 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 Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - _Max Alekseyev_, Apr 03 2022

%H 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 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 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 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 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 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 a(n) = A001197(n) - 1 for n>=2. - _Rob Pratt_, Aug 09 2019

%e Examples of a(2)=3, a(3)=6, and a(4)=9:

%e 11 110 1110

%e 10 101 1001

%e 011 0101

%e 0011

%e a(4)=9 is also achieved at a symmetric matrix:

%e 0111

%e 1010

%e 1100

%e 1001 - _Max Alekseyev_, Apr 03 2022

%Y Cf. A001197.

%K nonn,nice,hard,more

%O 1,2

%A Xuli Le (leshlie(AT)eyou.com), Jun 21 2002

%E a(1) = 1 from _Don Reble_, Oct 13 2007

%E More terms (using formula and A001197) from _Rob Pratt_, Aug 09 2019

%E a(22)-a(24) from _Jeremy Tan_, Jan 23 2022

%E Edited by _Max Alekseyev_, Apr 03 2022

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)