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

Author

Michel Marcus, Dec 11 2020

Keywords

• nonn
• tabl

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

Examples

			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)
		

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

Crossrefs

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

Cf. A016777, A347474.

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

Extensions

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