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

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

Offset: 1

Author

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

Keywords

• nonn
• nice
• hard
• more

Comments

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

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

Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - Max Alekseyev, Apr 03 2022

Examples

			Examples of a(2)=3, a(3)=6, and a(4)=9:
11   110   1110
10   101   1001
     011   0101
           0011
a(4)=9 is also achieved at a symmetric matrix:
0111
1010
1100
1001 - _Max Alekseyev_, Apr 03 2022
		

Links

• Brendan McKay's Largest graphs of girth at least 6, 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.]
• Stefan Neuwirth, The size of bipartite graphs with girth eight, arXiv:math/0102210 [math.CO], 2001.
• I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 3-4 , pp 269-273.
• R. Honsberger, Two Problems from the 1974 USSR National Olympiad (#4 and #9). 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).]
• E. Belaga, Solution to Problem M335, Kvant 3 (1976), 42-44. (in Russian)

Crossrefs

Cf. A001197.

Formula

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

a(n) = A001197(n) - 1 for n>=2. - Rob Pratt, Aug 09 2019

Extensions

a(1) = 1 from Don Reble, Oct 13 2007

More terms (using formula and A001197) from Rob Pratt, Aug 09 2019

a(22)-a(24) from Jeremy Tan, Jan 23 2022

Edited by Max Alekseyev, Apr 03 2022