%I M4601 N1962 #38 Oct 18 2022 13:04:44
%S 9,14,21,27,34,43,50,61,70,81,93,106,121,129
%N Zarankiewicz's problem k_3(n).
%C 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
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H R. K. Guy, <a href="/A001197/a001197.pdf">A problem of Zarankiewicz</a>, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
%H R. K. Guy, <a href="http://dx.doi.org/10.1007/BFb0060112">A many-facetted problem of Zarankiewicz</a>, Lect. Notes Math. 110 (1969), 129-148.
%H Jeremy Tan, <a href="https://arxiv.org/abs/2203.02283">An attack on Zarankiewicz's problem through SAT solving</a>, arXiv:2203.02283 [math.CO], 2022.
%F a(n) = A350304(n) + 1 = n^2 - A347473(n) = n^2 - A350237(n) + 1. - _Andrew Howroyd_, Dec 26 2021
%e From _M. F. Hasler_, Sep 28 2021: (Start)
%e 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.
%e 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:
%e 0 1 1 1 0 1 1 1 no 3 X 3
%e Here one can delete, e.g., -> 1 0 1 1 1 0 1 1 <- all-ones
%e row 1 and column 2 to get 1 1 1 1 1 1 0 1 submatrix
%e an all-ones 3 X 3 matrix. 1 1 1 1 1 1 1 1 (End)
%Y Cf. A001197 (k_2(n)), A006613 (k_{2,3}(n)), ..., A006626 (k_4(n,n+1)).
%Y Cf. A339635, A347473, A350237, A350304.
%K nonn,more,hard
%O 3,1
%A _N. J. A. Sloane_
%E a(11)-a(13) from _Andrew Howroyd_, Dec 26 2021
%E a(14)-a(15) computed from A350237 by _Max Alekseyev_, Apr 01 2022
%E a(16) from _Jeremy Tan_, Oct 02 2022