4
$\begingroup$

Let $n$ and $k \le n/2$ be positive integers, and consider a family $\mathcal{F}$ of $k\times k$ sub-matrices of an $n\times n$ matrix such that every two elements of $\mathcal{F}$ intersect. What non-trivial (I know I'm already annoying people by this term) properties of $\mathcal{F}$ one could claim? (in particular related to its cardinality).

$\endgroup$
  • $\begingroup$ You state “On the size of a family of submatrices” in the title and ask “properties of F” (as opposed to “properties of |F|”) in the body of the question. Which is correct? $\endgroup$ – Tsuyoshi Ito Feb 8 '11 at 20:39
  • $\begingroup$ This isn't really about matrices so much as it is about grids, right? I.e., these 'matrices' don't have any values in them, you're effectively just talking about pairwise nondisjoint square subgrids of an $n\times n$ grid... $\endgroup$ – Steven Stadnicki Feb 8 '11 at 22:21
  • $\begingroup$ What would be a good upper bound on the size of such family? $\endgroup$ – user2471 Feb 9 '11 at 4:56
2
$\begingroup$

As @Steven Stadnicki points out in his comment, acording to your question, the contents of the matrices are not important here, but the number $k$ and $n$. Therefore, you can look at $\mathcal{F}$ as a family of intersecting $k$-subsets of $\{1,\dots,n\}$.

You can derive properties from something called a Sunflower.

Definition: A sunflower with $m$ petals and a core $Y$ is a collection of sets $S_1,\dots,S_m$ such that $S_i\cap S_j=Y$ for all $i\neq j$. Moreover, the sets $S_i\setminus Y\neq \emptyset$.

Sunflower Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}|>k!(k-1)^k$ then $\mathcal{F}$ contains a sunflower with $k$ petals.

You can make relaxations to the sunflower, like the petals not being intersected by a set of size smaller than $c$. In this case we have the following lemma.

Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}| > (c-1)^k$ then $\mathcal{F}$ contains a flower with $k$ petals.

There are more properties that you can look for in the book:

Extremal Combinatorics with Applications to Computer Science by Stasys Jukna.

The definitions and lemmas above are from chapter 7. Take a look at the excercises, and maybe also chapter 8 on Intersecting Families.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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