login
A001198
Zarankiewicz's problem k_3(n).
(Formerly M4601 N1962)
13
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
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)).
Sequence in context: A070552 A272141 A289548 * A151915 A100263 A371059
KEYWORD
nonn,more,hard
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