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
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)
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
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
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
a(22)-a(24) from Jeremy Tan, Jan 23 2022
Edited by Max Alekseyev, Apr 03 2022
STATUS
approved