|
|
A001197
|
|
Zarankiewicz's problem k_2(n).
(Formerly M3300 N1330)
|
|
25
|
|
|
4, 7, 10, 13, 17, 22, 25, 30, 35, 40, 46, 53, 57, 62, 68, 75, 82, 89, 97, 106, 109, 116, 123
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
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
|
|
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]
|
|
FORMULA
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
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
|
|
STATUS
|
approved
|
|
|
|