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
A001198
Zarankiewicz's problem k_3(n).
Original entry on oeis.org
9, 14, 21, 27, 34, 43, 50, 61, 70, 81, 93, 106, 121, 129
Offset: 3
From _M. F. Hasler_, Sep 28 2021: (Start)
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.
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:
0 1 1 1 0 1 1 1 no 3 X 3
Here one can delete, e.g., -> 1 0 1 1 1 0 1 1 <- all-ones
row 1 and column 2 to get 1 1 1 1 1 1 0 1 submatrix
an all-ones 3 X 3 matrix. 1 1 1 1 1 1 1 1 (End)
- 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.
- 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).
- 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.
- Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.
A347473
Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 3 X 3 zero submatrix.
Original entry on oeis.org
0, 2, 4, 9, 15, 21, 31, 39, 51, 63, 76, 90, 104, 127
Offset: 3
For n = 3, there must not be any nonzero entry in an n X n = 3 X 3 matrix, if one wants a 3 X 3 zero submatrix, whence a(3) = 0.
For n = 4, having at most 2 nonzero entries in the n X n matrix guarantees that there is a 3 X 3 zero submatrix (delete, e.g., the row which has the first nonzero entry, then the column with the remaining nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 3 X 3 zero submatrix. Hence, a(4) = 2.
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.
A347472
Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 2 X 2 zero submatrix.
Original entry on oeis.org
0, 2, 6, 12, 19, 27, 39, 51, 65, 81, 98, 116, 139, 163, 188, 214, 242, 272, 303, 335, 375, 413, 453
Offset: 2
For n = 2, there must not be any nonzero entry in an n X n = 2 X 2 matrix, if one wants a 2 X 2 zero submatrix, whence a(2) = 0.
For n = 3, having at most 2 nonzero entries in the n X n matrix still guarantees that there is a 2 X 2 zero submatrix (delete the row of the first nonzero entry and then the column of the remaining nonzero entry, if any), but if one allows 3 nonzero entries and they are placed on the diagonal, then there is no 2 X 2 zero submatrix. Hence, a(3) = 2.
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-10 of 10 results.
Comments