A350296 -id:A350296 - 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

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

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

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

A376167 Square array read by antidiagonals: T(n,k) = smallest r such that every n X k binary matrix with r ones contains a 2 X 2 submatrix of ones, with n, k >= 2.

Original entry on oeis.org

4, 5, 5, 6, 7, 6, 7, 8, 8, 7, 8, 9, 10, 9, 8, 9, 10, 11, 11, 10, 9, 10, 11, 13, 13, 13, 11, 10, 11, 12, 14, 15, 15, 14, 12, 11, 12, 13, 15, 16, 17, 16, 15, 13, 12, 13, 14, 16, 18, 19, 19, 18, 16, 14, 13, 14, 15, 17, 19, 20, 22, 20, 19, 17, 15, 14, 15, 16, 18, 21, 22, 23, 23, 22, 21, 18, 16, 15

Offset: 2

Paolo Xausa, Sep 13 2024

			Array begins (cf. Table 5 in Knuth (2023), section 7.2.2.2, p. 291, where T(n,k) is denoted by Z(m,n)):
  n\k|   2   3   4   5   6   7   8   9  10  11  12  ...
  -----------------------------------------------------
   2 |   4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, ...
   3 |   5,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, ...
   4 |   6,  8, 10, 11, 13, 14, 15, 16, 17, 18, 19, ...
   5 |   7,  9, 11, 13, 15, 16, 18, 19, 21, 22, 23, ...
   6 |   8, 10, 13, 15, 17, 19, 20, 22, 23, 25, 26, ...
   7 |   9, 11, 14, 16, 19, 22, 23, 25, 26, 28, 29, ...
   8 |  10, 12, 15, 18, 20, 23, 25, 27, 29, 31, 33, ...
   9 |  11, 13, 16, 19, 22, 25, 27, 30, 32, 34, 37, ...
  10 |  12, 14, 17, 21, 23, 26, 29, 32, 35, 37, 40, ...
  11 |  13, 15, 18, 22, 25, 28, 31, 34, 37, 40, 43, ...
  12 |  14, 16, 19, 23, 26, 29, 33, 37, 40, 43, 46, ...
  ...
T(3,4) = 8 because, no matter how 8 ones are arranged in a 3 X 4 matrix, a 2 X 2 submatrix of ones cannot be avoided (in the left configuration below, for example, the submatrix elements are highlighted by parentheses). 7 ones can avoid such submatrix (right).
.
  (1) 0 (1) 1       1  0  1  1
   0  1  0  1       0  1  0  1
  (1) 1 (1) 0       1  1  0  0

Donald E. Knuth, The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, section 7.2.2.2, pp. 289-291.

Cf. A001197 (main diagonal), A347472, A350296.

T(n,k) = T(k,n).
T(2,k) = k + 2.
T(n,2) = n + 2.

cp's OEIS Frontend

A001197 Zarankiewicz's problem k_2(n).

Views

Author

Keywords

Comments

References

Links

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

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

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

A376167 Square array read by antidiagonals: T(n,k) = smallest r such that every n X k binary matrix with r ones contains a 2 X 2 submatrix of ones, with n, k >= 2.

Views

Author

Keywords

Examples

References

Crossrefs

Formula