cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 10 results.

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

			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)

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

Crossrefs

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

Formula

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

Extensions

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

Views

Author

Jeremy Tan, Dec 21 2021

Keywords

Comments

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

Examples

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

Links

Crossrefs

Column 3 of A339635.
Cf. A001198, A347473, A350304.

Formula

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

Extensions

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

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

Views

Author

M. F. Hasler, Sep 28 2021

Keywords

Comments

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.

Examples

			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.

Crossrefs

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.

Formula

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

Extensions

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

Views

Author

Andrew Howroyd, Dec 24 2021

Keywords

Comments

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

			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

References

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

Links

Crossrefs

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

Formula

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

Extensions

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

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

References

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

Crossrefs

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.

Extensions

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

Views

Author

M. F. Hasler, Sep 28 2021

Keywords

Comments

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.

Examples

			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.

Crossrefs

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.

Formula

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

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

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

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

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.

Extensions

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

Views

Author

N. J. A. Sloane

Keywords

References

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

Crossrefs

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.

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.