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!)
A191873 A problem of Zarankiewicz: maximal number of 1's in an n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners. 8
0, 2, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
In other words, the pattern
1...1
.....
1...1
is forbidden.
From Don Knuth, Aug 13 2014: (Start)
Well, it is well known from A001197 that a(8)<25. A001197 is essentially the same problem, but increased by 1, and without restricting the diagonals. The diagonal restriction is however of little interest, because it's easy to permute rows and columns and get all 0's or all 1's or probably any of the 2^n possible settings of the diagonal. At least, this is true when n=8; hence a(8) in this sequence is 24.
Transposing cols 1<->4 and 5<->8 in the example by Guy 1967 page 130 as cited in A001197 gives a(8)=24:
01110000
10010100
00010011
01000101
10100010
11001000
00101001
00001110
But as stated above, I think this is quite trivial, and I believe this sequence should be downplayed. Readers should look at the sequence A001197 --- that's what Zarankiewicz's problem asked for in 1951, namely the min number that forces a rectangle, not the max number that doesn't exclude it.
(end)
Conjecture: for n >= 3, a(n) = A072567(n) = A001197(n) - 1 (per above comment). - Max Alekseyev, Jan 29 2022
REFERENCES
B. Bollobas, Extremal Graph Theory, pp. 309ff.
LINKS
D. Bienstock and E. Gyori, An extremal problem on sparse 0-1 matrices, SIAM J. Discrete Math. 4 (1991), 17-27.
CROSSREFS
Sequence in context: A190777 A184619 A184119 * A293789 A112870 A169915
KEYWORD
nonn,more
AUTHOR
R. H. Hardin and N. J. A. Sloane, Jun 18 2011
EXTENSIONS
a(8) confirmed, a(9)-a(12) added by Max Alekseyev, Feb 07 2022
STATUS
approved

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 29 10:44 EDT 2024. Contains 371268 sequences. (Running on oeis4.)