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

KEYWORD

nonn,tabl

AUTHOR

Michel Marcus, Dec 11 2020

EXTENSIONS

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

STATUS

approved