A350304 -id:A350304 - cp's OEIS frontend

A001198 Zarankiewicz's problem k_3(n).

9, 14, 21, 27, 34, 43, 50, 61, 70, 81, 93, 106, 121, 129

Offset: 3

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

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

A350189 Triangle T(n,k) read by rows: the number of symmetric binary n X n matrices with k ones and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 1, 3, 6, 10, 9, 9, 4, 1, 4, 12, 28, 46, 72, 80, 80, 60, 16, 1, 5, 20, 60, 140, 296, 500, 780, 1005, 1085, 992, 560, 170, 1, 6, 30, 110, 330, 876, 1956, 4020, 7140, 11480, 16248, 19608, 20560, 16500, 9720, 3276, 360, 1, 7, 42, 182, 665, 2121, 5852, 14792, 33117, 68355, 126994, 214158

Offset: 0

R. J. Mathar, Mar 09 2022

There are 2^(n^2) binary n X n matrices (entries of {0,1}). There are 2^(n*(n+1)/2) symmetric binary matrices. There are A184948(n,k) symmetric binary n X n matrices with k ones.
This sequence is the triangle T(n,k) of symmetric binary n x n matrices with k ones but no 2 X 2 submatrix with all entries = 1. [So in the display of these matrices there is no rectangle with four 1's at the corners.]
The row lengths minus 1 are 0, 1, 3, 6, 9, 12, 17, 21, 24, 29, ... and indicate the maximum number of 1's than can be packed into a symmetric binary n X n matrix without creating an all-1 quadrangle/submatrix of order 2.

			The triangle starts
  1;
  1 1;
  1 2 2 2;
  1 3 6 10 9 9 4;
  1 4 12 28 46 72 80 80 60 16;
  1 5 20 60 140 296 500 780 1005 1085 992 560 170;
  ...
To place 4 ones, one can place 2 of them in C(n,2) ways on the diagonal and the other 2 in n*(n-1)/2 ways outside the diagonal, avoiding one matrix that builds an all-1 submatrix, which are C(n,2)*(n*(n-1)/2-1) matrices. One can place all 4 on the diagonal in C(n,4) ways. One can place 2 outside the diagonal (the other 2 mirror symmetrically) in C(n*(n-1)/2,2) ways. Sum of the 3 terms is T(n,4) = C(n,3)*(5*n+3)/2. - _R. J. Mathar_, Mar 10 2022

Max Alekseyev, Table of n, a(n) for n = 0..361 (rows 0..14; rows 0..9 from R. J. Mathar)
P. Erdos and D. Kleitman, On collections of subsets containing no 4-member boolean algebra, Proc. Am. Math. Soc. 28 (1) (1971) 87.
R. J. Mathar, Illustration of graphs with these incidence matrices
Index entries for sequences of binary matrices
Index entries for sequences of squarefree graphs

Cf. A001197 (conjectured row lengths), A352258 (row sums), A352801 (rightmost terms), A350296, A350304, A350237, A352472 (traceless symmetric).

Cf. A002378, A006331, A000217, A147875.

T(n,0) = 1.
T(n,1) = n.
T(n,2) = A002378(n-1).
T(n,3) = A006331(n-1).
T(n,4) = n*(n-1)*(n-2)*(5*n+3)/12 = A147875(n)*A000217(n-1)/3. - R. J. Mathar, Mar 10 2022
T(n,5) = n*(n-1)*(n-2)*(13*n^2-n-24)/60. T(n,6) = n*(n-1)*(n-2)*(19*n^3-18*n^2-97*n+60)/180. T(n,7) = n*(n-1)*(n-2)*(n-3)*(58*n^3+75*n^2-223*n+180)/1260. - Conjectured by R. J. Mathar, Mar 11 2022; proved by Max Alekseyev, Apr 02 2022
G.f.: F(x,y) = Sum_{n,k} T(n,k)*x^n/n!*y^k = exp( Sum_G x^n(G) * y^u(G) / |Aut(G)| ), where G runs over the connected squarefree graphs with loops, n(G) is the number of nodes in G, u(G) the number of ones in the adjacency matrix of G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + x*y + x^2*y^2 + (2/3*x^3 + x^2)*y^3 + (5/12*x^4 + 3/2*x^3)*y^4 + (13/60*x^5 + 3/2*x^4 + 3/2*x^3)*y^5 + (19/180*x^6 + 7/6*x^5 + 8/3*x^4 + 2/3*x^3)*y^6 + (29/630*x^7 + 3/4*x^6 + 19/6*x^5 + 10/3*x^4)*y^7 + O(y^8)), implying the above formulas for T(n,k). - Max Alekseyev, Apr 02 2022
Conjecture: the largest k such that T(n,k) is nonzero is k = A072567(n) = A001197(n) - 1. - Max Alekseyev, Apr 03 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

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

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

A350189 Triangle T(n,k) read by rows: the number of symmetric binary n X n matrices with k ones and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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