A001198 Zarankiewicz's problem k_3(n). (Formerly M4601 N1962)

9, 14, 21, 27, 34, 43, 50, 61, 70, 81, 93, 106, 121, 129

Offset

3,1

Comments

Guy denotes k_{a,b}(m,n) the least k such that any m X n matrix with k '1's and '0's elsewhere has an a X b submatrix with all '1's, and omits b (resp. n) when b = a (resp. n = m). With this notation, a(n) = k_3(n). Sierpiński (1951) found a(4..6), a(7) is due to Brzeziński and a(8) due to Čulík (1956). - M. F. Hasler, Sep 28 2021

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.

R. K. Guy, A problem of Zarankiewicz, in P. Erdős and G. Katona, editors, Theory of Graphs (Proceedings of the Colloquium, Tihany, Hungary), Academic Press, NY, 1968, pp. 119-150.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=3..16.

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Formula

a(n) = A350304(n) + 1 = n^2 - A347473(n) = n^2 - A350237(n) + 1. - Andrew Howroyd, Dec 26 2021

Example

From M. F. Hasler, Sep 28 2021: (Start)
For n = 3 it is clearly necessary and sufficient that there be 3 X 3 = 9 ones in the n X n matrix in order to have an all-ones 3 X 3 submatrix.
For n = 4 there may be at most 2 zeros in the 4 X 4 matrix in order to be guaranteed to have a 3 X 3 submatrix with all '1's, whence a(4) = 16 - 2 = 14: If 3 zeros are placed on a diagonal, it is no more possible to find a 3 X 3 all-ones submatrix, but if there are at most 2 zeros, one always has such a submatrix, as one can see from the following two diagrams:
                                       0 1 1 1        0 1 1 1      no 3 X 3
     Here one can delete, e.g.,   ->   1 0 1 1        1 0 1 1  <-  all-ones
     row 1 and column 2 to get         1 1 1 1        1 1 0 1      submatrix
     an all-ones 3 X 3 matrix.         1 1 1 1        1 1 1 1        (End)

Crossrefs

Cf. A001197 (k_2(n)), A006613 (k_{2,3}(n)), ..., A006626 (k_4(n,n+1)).

Cf. A339635, A347473, A350237, A350304.

Sequence in context: A070552 A272141 A289548 * A151915 A100263 A371059

Adjacent sequences: A001195 A001196 A001197 * A001199 A001200 A001201

Keyword

nonn,more,hard

Author

N. J. A. Sloane

Extensions

a(11)-a(13) from Andrew Howroyd, Dec 26 2021

a(14)-a(15) computed from A350237 by Max Alekseyev, Apr 01 2022

a(16) from Jeremy Tan, Oct 02 2022

Status

approved