|
|
A072567
|
|
A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.
|
|
12
|
|
|
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
|
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.]
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,hard,more
|
|
AUTHOR
|
Xuli Le (leshlie(AT)eyou.com), Jun 21 2002
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|