1
$\begingroup$

Is it possible to determine (or give bounds for) the following extremal problem:

Let $k,m,r$ be positive integers such that $k,m \geq r$. What is the least number $n$ such that for any $r \times n$ matrix in which any subset of $k$ columns have full rank $r$, must contain a size $m$ subset of the columns in which any $r$-subset has full rank.

Improve this question
$\endgroup$
2
  • $\begingroup$ Obviously $n\leqslant R_r(k,m)$ (the Ramsey number for $r$-uniform hypergraphs). $\endgroup$
    – Fedor Petrov
    Commented Jul 5, 2016 at 11:06
  • 1
    $\begingroup$ My bad, I should have mentioned this in the question. If we colour an $r$-subset of the columns blue if they have full rank and red otherwise, then $n = R_r(k,m)$ suffices to guarantee a monochromatic $m$-subset in blue since we are prohibiting a monochromatic red $k$-subset. I think however that this bound can be improved a lot since far from all such colourings actually represent valid ranks of $r \times r$ sub-matrices. Is it somehow possible to use the extra structure in this problem to improve on the Ramsey bound? $\endgroup$
    – user94267
    Commented Jul 5, 2016 at 12:24

1 Answer 1

Reset to default
1
$\begingroup$

We may get a better bound by the greedy algorithm. Choose columns one by one so that any $r$ chosen columns are linearly independent. Assume that $N<m$ columns are chosen and we cannot proceed. Then any other column lies in one of hyperplanes defined by some $r-1$ chosen vectors. Each such hyperplane contains at most $k-r$ new (not chosen yet) vectors, thus we get $n\leqslant N+(k-r)\binom{N}{r-1}$. In other words, if $n\geqslant m+(k-r)\binom{m-1}{r-1}$, we choose at least $m$ vectors. This is tight for $r=1$ and for $r=2$, but I expect that better bounds should hold for greater values of $r$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, this is already a good improvement on $R_r(k,m)$. I agree it feels like better bounds should still be available. In the greedy approach I suppose one is overestimating the number of $r$-subsets without full rank i.e the number of $r$ vectors contained in a hyperplane. With a better estimate on this number it should of course be possible to improve the bound further. I would appreciate any further thoughts on how to proceed with this problem, otherwise your answer is perfectly acceptable. $\endgroup$
    – user94267
    Commented Jul 6, 2016 at 14:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .