A001197 Zarankiewicz's problem k_2(n).

4, 7, 10, 13, 17, 22, 25, 30, 35, 40, 46, 53, 57, 62, 68, 75, 82, 89, 97, 106, 109, 116, 123

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more

Comments

a(n) is the minimum number k_2(n) such that any n X n matrix having that number of nonzero entries has a 2 X 2 submatrix with only nonzero entries. - M. F. Hasler, Sep 28 2021

a(n) <= (1 + sqrt(4*n-3))*n/2 + 1. - Max Alekseyev, Apr 03 2022

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.
• Richard J. Nowakowski, Zarankiewicz's Problem, PhD Dissertation, University of Calgary, 1978, page 202.
• 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.

Crossrefs

Cf. A001198 (k_3), A072567, A339635, A347472, A350296.

Cf. also A006613 - A006626 (other sizes, in particular A006616 = k_4).

Main diagonal of A376167.

Formula

a(n) = A072567(n) + 1. - Rob Pratt, Aug 09 2019

a(n) = n^2 - A347472(n) = n^2 - A350296(n) + 1. - Andrew Howroyd, Dec 26 2021

Extensions

Nowakowski's thesis, directed by Guy, corrected Guy's value for a(15) and supplied a(16)-a(21) entered by Don Knuth, Aug 13 2014

a(1) deleted following a suggestion from M. F. Hasler. - N. J. A. Sloane, Oct 22 2021

a(22)-a(24) from Jeremy Tan, Jan 23 2022