Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.

Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided

(a) $A$ is a $k\times k$ submatrix of $M$, and

(b) $A$ overlaps with each and every $B\in\mathcal{F}$.

QUESTION. What is the best upper bound for the cardinality of $\mathcal{F}$, in terms of $n$ and $k$?

up vote 5 down vote accepted

To each such matrix $A$ we can associate $A_1,A_2$, the sets of column indices and row indices respectively. The families $\mathcal F_i=\{A_i| A\in \mathcal F\}$ are intersecting families of subsets, therefore by Erdos-Ko-Rado we have $$|\mathcal F_i|\le \binom{2n-1}{k-1}$$ Since a matrix $A$ is uniquely determined by its set of rows and columns we have $$|\mathcal F|\le |\mathcal F_1||\mathcal F_2|\le \binom{2n-1}{k-1}^2$$ and this maximum can be achieved by taking all the $k\times k$ submatrices that contain the $(1,1)$ entry.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.