A347474 -id:A347474 - cp's OEIS frontend

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

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

A339635 Triangle read by rows, T(n, k) is the least number of 1's in an n X n binary matrix so that every k X k minor contains at least one 1.

Original entry on oeis.org

1, 4, 1, 9, 3, 1, 16, 7, 3, 1, 25, 13, 5, 3, 1, 36, 20, 10, 5, 3, 1, 49, 28, 16, 7, 5, 3, 1, 64, 40, 22, 13, 7, 5, 3, 1, 81, 52, 32, 20, 9, 7, 5, 3, 1, 100, 66, 40, 26, 16, 9, 7, 5, 3, 1, 121, 82, 52, 35, 23, 11, 9, 7, 5, 3, 1, 144, 99, 64, 44, 30, 19, 11, 9, 7, 5, 3, 1

Offset: 1

Michel Marcus, Dec 11 2020

This sequence is related to the Zarankiewicz problem. In particular, T(n,k) = n^2 - z(n,n; k,k) where z(m,n; s,t) is the Zarankiewicz function. (Here the Zarankiewicz function is as defined on Wikipedia. A number of OEIS sequences use a definition that is 1 greater). - Andrew Howroyd, Dec 23 2021

The terms represent solutions for a certain covering problem. k X k Minors are 'squaresets' in the Cartesian product rows X columns, i.e., subsets A X B with A subset of rows and B subset of columns, and with card(A) = card(B) = k. - Rainer Rosenthal, Dec 18 2022

			Triangle begins:
    1;
    4,  1;
    9,  3,  1;
   16,  7,  3,  1;
   25, 13,  5,  3,  1;
   36, 20, 10,  5,  3,  1;
   49, 28, 16,  7,  5,  3,  1;
   64, 40, 22, 13,  7,  5,  3, 1;
   81, 52, 32, 20,  9,  7,  5, 3, 1;
  100, 66, 40, 26, 16,  9,  7, 5, 3, 1;
  121, 82, 52, 35, 23, 11,  9, 7, 5, 3, 1;
  144, 99, 64, 44, 30, 19, 11, 9, 7, 5, 3, 1;
   ...
From _Rainer Rosenthal_, Dec 18 2022: (Start)
T(3,2) = 3 is visualized in short form in the example section of A350296. Here is a longer explanation, showing all the 2 X 2 minors of the 3 X 3 matrix:
.
       . . .      . . .      . . .
       . A A      B . B      C C .
       . A A      B . B      C C .
.
       . D D      E . E      F F .
       . . .      . . .      . . .
       . D D      E . E      F F .
.
       . G G      H . H      I I .
       . G G      H . H      I I .
       . . .      . . .      . . .
.
One can easily check that three 1's on a diagonal are enough to guarantee that each minor covers at least one of them. The diagonals are given by any of these two matrices:
.
        1 0 0         0 0 1
        0 1 0   and   0 1 0
        0 0 1         1 0 0
.
Evidently at least three 1's are needed, therefore we have T(3,2) = 3. (End)

Andrew Howroyd, Table of n, a(n) for n = 1..91
Chengcheng Yang, A Problem of Erdös Concerning Lattice Cubes, arXiv:2011.15010 [math.CO], 2020. See Table p. 27.
Wikipedia, Zarankiewicz problem

Columns 1..3 are A000290, A350296, A350237.

Cf. A016777, A347474.

T(n, 1) = n^2; T(n, n) = 1; T(2*n, n) = 3*n+1 = A016777(n).

T(n, k) = 2*(n-k) + 1 for k > n/2. - Andrew Howroyd, Dec 23 2021

Terms a(16) and beyond from Andrew Howroyd, Dec 22 2021

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

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

N. J. A. Sloane

a(n) <= A205805(2*n+1) + 1. - Max Alekseyev, Feb 02 2024

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.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

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

M. F. Hasler, Sep 28 2021

Related to Zarankiewicz's problem k_2(n) (cf. A001197 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 2 X 2 submatrix. This complementarity leads to the given formula which was used to compute the given values.

See A347473 and A347474 for the similar problem with a 3 X 3 resp. 4 X 4 zero submatrix.

			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.

Cf. A001197 (k_2(n)), A001198 (k_3(n)), A006613 - A006626.
Cf. A347473, A347474 (analog for 3 X 3 resp. 4 X 4 zero submatrix).
Cf. A350296.

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

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

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

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

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.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name updated at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

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

N. J. A. Sloane

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.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine and a(9) added by Max Alekseyev, Feb 02 2024

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

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. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006620, A006621, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name edited at the suggestion of Sean A. Irvine and a(8) added by Max Alekseyev, Feb 02 2024

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

N. J. A. Sloane

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.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Name changed at the suggestion of Sean A. Irvine and a(8) added by Max Alekseyev, Feb 02 2024

cp's OEIS Frontend

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

A339635 Triangle read by rows, T(n, k) is the least number of 1's in an n X n binary matrix so that every k X k minor contains at least one 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A006616 Zarankiewicz's problem k_4(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

References

Crossrefs

Extensions

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.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

References

Crossrefs

Extensions