cp's OEIS Frontend

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.

%I A191873 #35 Aug 15 2025 02:27:14
%S A191873 0,2,6,9,12,16,21,24,29,34,39,45
%N 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.
%C A191873 In other words, the pattern
%C A191873   1...1
%C A191873   .....
%C A191873   1...1
%C A191873 is forbidden.
%C A191873 From _Don Knuth_, Aug 13 2014: (Start)
%C A191873 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.
%C A191873 Transposing cols 1<->4 and 5<->8 in the example by Guy 1967 page 130 as cited in A001197 gives a(8)=24:
%C A191873   01110000
%C A191873   10010100
%C A191873   00010011
%C A191873   01000101
%C A191873   10100010
%C A191873   11001000
%C A191873   00101001
%C A191873   00001110
%C A191873 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)
%C A191873 Conjecture: for n >= 3, a(n) = A072567(n) = A001197(n) - 1 (per above comment). - _Max Alekseyev_, Jan 29 2022
%D A191873 B. Bollobas, Extremal Graph Theory, pp. 309ff.
%H A191873 D. Bienstock and E. Gyori, <a href="http://dx.doi.org/10.1137/0404002">An extremal problem on sparse 0-1 matrices</a>, SIAM J. Discrete Math. 4 (1991), 17-27.
%Y A191873 Cf. A072567, A191874, A191965, A191966.
%K A191873 nonn,more
%O A191873 1,2
%A A191873 _R. H. Hardin_ and _N. J. A. Sloane_, Jun 18 2011
%E A191873 a(8) confirmed, a(9)-a(12) added by _Max Alekseyev_, Feb 07 2022