A001197
Zarankiewicz's problem k_2(n).
Original entry on oeis.org
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
- 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).
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
A006626
Zarankiewicz's problem k_4(n,n+1).
Original entry on oeis.org
19, 27, 37, 46, 56, 68, 80, 94, 109
Offset: 4
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A347474
Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 4 X 4 zero submatrix.
Original entry on oeis.org
0, 2, 4, 6, 12, 19, 25, 34, 43, 51
Offset: 4
For n < 4, there is no solution, since there cannot be a 4 X 4 submatrix in a matrix of smaller size.
For n = 4, there must not be any nonzero entry in an n X n = 4 X 4 matrix, if one wants a 4 X 4 zero submatrix, whence a(4) = 0.
For n = 5, having at most 2 nonzero entries in the n X n matrix guarantees that there is a 4 X 4 zero submatrix (delete, e.g., the row with the first nonzero entry, then the column with the second nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 4 X 4 zero submatrix. Hence, a(5) = 2.
A006620
A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 2 X 2 submatrix.
Original entry on oeis.org
5, 8, 11, 15, 19, 23, 27, 32, 37, 43, 49, 54, 59, 64
Offset: 2
- R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Cf.
A006613,
A006614,
A006615,
A006616,
A006617,
A006618,
A006619,
A006621,
A006622,
A006623,
A006624,
A006625,
A006626.
A006614
A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 2 X 4 submatrix.
Original entry on oeis.org
14, 21, 26, 32, 41, 48, 56, 67
Offset: 4
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- 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. 35.
Cf.
A006613,
A006615,
A006616,
A006617,
A006618,
A006619,
A006620,
A006621,
A006622,
A006623,
A006624,
A006625,
A006626.
A006615
A variant of Zarankiewicz's problem: a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.
Original entry on oeis.org
15, 22, 31, 38, 46, 57
Offset: 4
- R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Cf.
A006613,
A006614,
A006616,
A006617,
A006618,
A006619,
A006620,
A006621,
A006622,
A006623,
A006624,
A006625,
A006626.
A006622
A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.
Original entry on oeis.org
12, 18, 26, 33, 41, 51
Offset: 3
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Cf.
A006613,
A006614,
A006615,
A006616,
A006617,
A006618,
A006619,
A006620,
A006621,
A006623,
A006624,
A006625,
A006626.
A006625
A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+2) {0,1}-matrix with k ones contains an all-ones 3 X 4 submatrix.
Original entry on oeis.org
14, 21, 28, 36, 45, 55
Offset: 3
- R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Cf.
A006613,
A006614,
A006615,
A006616,
A006617,
A006618,
A006619,
A006620,
A006621,
A006622,
A006623,
A006624,
A006626.
Showing 1-8 of 8 results.
Comments