

A072567


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


7



1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, 122
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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


LINKS

Table of n, a(n) for n=1..24.
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 34 , pp 269273.
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), 4244. (in Russian)


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


EXAMPLE

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


CROSSREFS

Cf. A001197.
Sequence in context: A214050 A260706 A194199 * A186353 A061796 A113241
Adjacent sequences: A072564 A072565 A072566 * A072568 A072569 A072570


KEYWORD

nonn,nice,hard,more


AUTHOR

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


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


STATUS

approved



