A339635 -id:A339635 - cp's OEIS frontend

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

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

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).

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.

Cf. A001198 (k_3), A072567, A339635, A347472, A350296.
Cf. also A006613 - A006626 (other sizes, in particular A006616 = k_4).
Main diagonal of A376167.

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

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

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

N. J. A. Sloane

Guy denotes k_{a,b}(m,n) the least k such that any m X n matrix with k '1's and '0's elsewhere has an a X b submatrix with all '1's, and omits b (resp. n) when b = a (resp. n = m). With this notation, a(n) = k_3(n). Sierpiński (1951) found a(4..6), a(7) is due to Brzeziński and a(8) due to Čulík (1956). - M. F. Hasler, Sep 28 2021

			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.

Cf. A001197 (k_2(n)), A006613 (k_{2,3}(n)), ..., A006626 (k_4(n,n+1)).

Cf. A339635, A347473, A350237, A350304.

a(n) = A350304(n) + 1 = n^2 - A347473(n) = n^2 - A350237(n) + 1. - Andrew Howroyd, Dec 26 2021

a(11)-a(13) from Andrew Howroyd, Dec 26 2021
a(14)-a(15) computed from A350237 by Max Alekseyev, Apr 01 2022
a(16) from Jeremy Tan, Oct 02 2022

A350237 Minimum number of 1's in an n X n binary matrix with no zero 3 X 3 submatrix.

Original entry on oeis.org

0, 0, 1, 3, 5, 10, 16, 22, 32, 40, 52, 64, 77, 91, 105, 128

Offset: 1

Jeremy Tan, Dec 21 2021

The submatrix's rows and columns need not be contiguous, so the following matrix does not show a(4) = 1:
   ....
   .1..
   ....
   ....

			a(4) = 3 because the following 4 X 4 binary matrix with 3 1's has no zero 3 X 3 submatrix, and all such matrices with fewer 1's have at least one zero 3 X 3 submatrix:
   1...
   .1..
   ..1.
   ....

Jeremy Tan, Python program with illustration of initial terms
Jeremy Tan, Two genies and their kind of chess, Puzzling Stack Exchange, Dec 19 2021. (shows a(8) = 22)
Jeremy Tan, What's the minimum number of people required?, Mathematics Stack Exchange, Dec 20 2021.
Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Column 3 of A339635.

Cf. A001198, A347473, A350304.

a(n) = A347473(n) + 1 = n^2 - A001198(n) + 1.

a(n) = n^2 - A350304(n). - Max Alekseyev, Oct 31 2022

a(12)-a(13) from Andrew Howroyd, Dec 23 2021
a(14)-a(15) from Jeremy Tan, Jan 03 2022
a(16) from Jeremy Tan, added by Max Alekseyev, Oct 31 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

M. F. Hasler, Sep 28 2021

Related to Zarankiewicz's problem k_3(n) (cf. A001198 and other crossrefs), which asks the converse: how many 1's must be in an n X n {0,1}-matrix in order to guarantee the existence of an all-ones 3 X 3 submatrix. This complementarity leads to the given formula which was used to compute the given values.

			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.

Cf. A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626 (other sizes of the main matrix and the submatrix).
Cf. A347472, A347474 (analog for 2 X 2 resp. 4 X 4 zero submatrix).
Cf. A339635, A350237, A350304.

a(n) = n^2 - A001198(n).
a(n) = A350237(n) - 1. - Andrew Howroyd, Dec 24 2021
a(n) = n^2 - A350304(n) - 1. - Max Alekseyev, Oct 31 2022

a(11)-a(13) from Andrew Howroyd, Dec 24 2021

a(14)-a(16) computed from A350237 by Max Alekseyev, Apr 01 2022, Oct 31 2022

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

M. F. Hasler, Sep 28 2021

Related to Zarankiewicz's problem k_4(n) (cf. A006616 and other crossrefs) which asks the converse: how many 1's must be in an n X n {0,1}-matrix in order to guarantee the existence of an all-ones 4 X 4 submatrix. This complementarity leads to the given formula which was used to compute the given values.

			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.

Cf. A347472, A347473 (analog for 2 X 2 resp. 3 X 3 zero submatrix).
Cf. A006616 (k_4(n)), A001198 (k_3(n)), A001197 (k_2(n)), A006613 - A006626.
Cf. A339635.

a(n) = n^2 - A006616(n).

a(n) = A339635(n,4) - 1. - Andrew Howroyd, Dec 23 2021

a(9)-a(12) from Andrew Howroyd, Dec 23 2021

a(13) computed from A006616 by Max Alekseyev, Feb 02 2024

A350304 Maximum number of 1's in an n X n binary matrix without an all-ones 3 X 3 submatrix.

Original entry on oeis.org

1, 4, 8, 13, 20, 26, 33, 42, 49, 60, 69, 80, 92, 105, 120, 128

Offset: 1

Andrew Howroyd, Dec 24 2021

Equivalently, the maximum number of edges in a bipartite graph that is a subgraph of K_{n,n} and has no K_{3,3} induced subgraph.

			Examples of a(3)=8, a(4)=13, a(5)=20, a(6)=26:
  x x x    x x x x    x x x x .    x x x x x .
  x x x    x x x .    x x x . x    x x x x . x
  x x .    x x . x    x x . x x    x x . . x x
           x . x x    x . x x x    x . x . x x
                      . x x x x    . x . x x x
                                   . . x x x x

W. Sierpiński, Sur un problème concernant un réseau à 36 points, Ann. Soc. Polon. Math., 24: 173-174 (1951).

Wikipedia, Zarankiewicz problem

Cf. A001198, A072567, A339635, A347473, A350237.

a(n) = A001198(n) - 1 = n^2 - A350237(n) = n^2 - A347473(n) - 1.

a(14)-a(16) computed from A350237 by Max Alekseyev, Apr 01 2022, Oct 31 2022

A006616 Zarankiewicz's problem k_4(n).

Original entry on oeis.org

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

Offset: 4

N. J. A. Sloane

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

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. 34.

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

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

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

A350296 Minimum number of 1's in an n X n binary matrix with no zero 2 X 2 submatrix.

Original entry on oeis.org

0, 1, 3, 7, 13, 20, 28, 40, 52, 66, 82, 99, 117, 140, 164, 189, 215, 243, 273, 304, 336, 376, 414, 454

Offset: 1

Andrew Howroyd, Dec 23 2021

			Solutions for a(3)=3, a(4)=7, a(5)=13, a(6)=20:
  . . x    . . . x    . . . . x    . . . x x x
  . x .    . x x .    . x x x .    . x x . . x
  x . .    x . x .    x . x x .    x . x . x .
           x x . .    x x . x .    x x . x . .
                      x x x . .    . x x x x .
                                   x . x x . x

Column 2 of A339635.

Cf. A001197, A072567, A152125, A227133, A347472.

a(n) = A347472(n) + 1 = n^2 - A001197(n) + 1 = n^2 - A072567(n).

a(n) >= A152125(n).

a(22)-a(24) computed from A001197, added by Max Alekseyev, Feb 08 2022

cp's OEIS Frontend

A001197 Zarankiewicz's problem k_2(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A001198 Zarankiewicz's problem k_3(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A350237 Minimum number of 1's in an n X n binary matrix with no zero 3 X 3 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A347473 Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 3 X 3 zero submatrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A347474 Maximum number of nonzero entries allowed in an n X n matrix to ensure there is a 4 X 4 zero submatrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A350304 Maximum number of 1's in an n X n binary matrix without an all-ones 3 X 3 submatrix.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A006616 Zarankiewicz's problem k_4(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A350296 Minimum number of 1's in an n X n binary matrix with no zero 2 X 2 submatrix.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions