cp's OEIS Frontend

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.

%I A339635 #44 Jun 16 2023 05:30:42
%S A339635 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,
%T A339635 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,
%U A339635 82,52,35,23,11,9,7,5,3,1,144,99,64,44,30,19,11,9,7,5,3,1
%N 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.
%C A339635 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
%C A339635 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
%H A339635 Andrew Howroyd, <a href="/A339635/b339635.txt">Table of n, a(n) for n = 1..91</a>
%H A339635 Chengcheng Yang, <a href="https://arxiv.org/abs/2011.15010">A Problem of Erdös Concerning Lattice Cubes</a>, arXiv:2011.15010 [math.CO], 2020. See Table p. 27.
%H A339635 Wikipedia, <a href="https://en.wikipedia.org/wiki/Zarankiewicz_problem">Zarankiewicz problem</a>
%F A339635 T(n, 1) = n^2; T(n, n) = 1; T(2*n, n) = 3*n+1 = A016777(n).
%F A339635 T(n, k) = 2*(n-k) + 1 for k > n/2. - _Andrew Howroyd_, Dec 23 2021
%e A339635 Triangle begins:
%e A339635     1;
%e A339635     4,  1;
%e A339635     9,  3,  1;
%e A339635    16,  7,  3,  1;
%e A339635    25, 13,  5,  3,  1;
%e A339635    36, 20, 10,  5,  3,  1;
%e A339635    49, 28, 16,  7,  5,  3,  1;
%e A339635    64, 40, 22, 13,  7,  5,  3, 1;
%e A339635    81, 52, 32, 20,  9,  7,  5, 3, 1;
%e A339635   100, 66, 40, 26, 16,  9,  7, 5, 3, 1;
%e A339635   121, 82, 52, 35, 23, 11,  9, 7, 5, 3, 1;
%e A339635   144, 99, 64, 44, 30, 19, 11, 9, 7, 5, 3, 1;
%e A339635    ...
%e A339635 From _Rainer Rosenthal_, Dec 18 2022: (Start)
%e A339635 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:
%e A339635 .
%e A339635        . . .      . . .      . . .
%e A339635        . A A      B . B      C C .
%e A339635        . A A      B . B      C C .
%e A339635 .
%e A339635        . D D      E . E      F F .
%e A339635        . . .      . . .      . . .
%e A339635        . D D      E . E      F F .
%e A339635 .
%e A339635        . G G      H . H      I I .
%e A339635        . G G      H . H      I I .
%e A339635        . . .      . . .      . . .
%e A339635 .
%e A339635 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:
%e A339635 .
%e A339635         1 0 0         0 0 1
%e A339635         0 1 0   and   0 1 0
%e A339635         0 0 1         1 0 0
%e A339635 .
%e A339635 Evidently at least three 1's are needed, therefore we have T(3,2) = 3. (End)
%Y A339635 Columns 1..3 are A000290, A350296, A350237.
%Y A339635 Cf. A016777, A347474.
%K A339635 nonn,tabl
%O A339635 1,2
%A A339635 _Michel Marcus_, Dec 11 2020
%E A339635 Terms a(16) and beyond from _Andrew Howroyd_, Dec 22 2021