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