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.

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,2

Comments

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

Links

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

Formula

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

Example

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)

Crossrefs

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

Cf. A016777, A347474.

Sequence in context: A331153 A331149 A331145 * A085691 A055461 A324999

Adjacent sequences: A339632 A339633 A339634 * A339636 A339637 A339638

Keyword

nonn,tabl

Author

Michel Marcus, Dec 11 2020

Extensions

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

Status

approved