A006616 Zarankiewicz's problem k_4(n).

16, 23, 32, 43, 52, 62, 75, 87, 101, 118

Offset: 4

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more

Comments

a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all ones 4 X 4 submatrix. - Sean A. Irvine, May 17 2017

References

• 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.
• Dmitry I. Ignatov, When contranominal scales give a solution to the Zarankiewicz problem?, Workshop Notes, 12th Int'l Wksp. Formal Concept Analysis Artif. Intel. (FCA4AI 2024), 27-38. See p. 34.

Crossrefs

Cf. A001197, A001198, A006626, A339635, A347474.

Formula

a(n) = n^2 - A347474(n). - Andrew Howroyd, Dec 26 2021

Extensions

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