<p>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\}$.</p>

<p>You can derive properties from something called a <em>Sunflower</em>.</p>

<p><strong>Definition:</strong> 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$.</p>

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

<p>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.</p>

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

<p>There are more properties that you can look for in the book:</p>

<p><a href="http://books.google.com/books?id=g6X2VWuB8qIC&amp;printsec=frontcover&amp;dq=extremal+combinatorics&amp;hl=es&amp;ei=YA9STeKsJIagvQPmqp2vCQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">Extremal Combinatorics with Applications to Computer Science</a> by Stasys Jukna.</p>

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

CC BY-SA 2.5
2011-02-09T03:56:37.063Z
2011-02-09T03:56:37.063Z
Marcos Villagra
<p>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 <b>non-trivial</b> (I know I'm already annoying people by this term) properties of $\mathcal{F}$ one could claim? (in particular related to its cardinality). </p>

CC BY-SA 2.5
2011-02-08T20:39:08.083Z
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?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T22:21:38.983Z
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...
Steven Stadnicki
CC BY-SA 2.5
2011-02-09T04:56:25.583Z
What would be a good upper bound on the size of such family?
user2471
<co.combinatorics><matrices>
On the properties of a family of submatrices
user2471
# On the properties of a family of submatrices

(Asked by: username_0 on 2011-02-08)

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).

**Tags:** co.combinatorics, matrices
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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...  
> **username_0**: What would be a good upper bound on the size of such family?  

---

## 1 answers

### Answer by username_3 on 2011-02-09. Score: 2

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](http://books.google.com/books?id=g6X2VWuB8qIC&printsec=frontcover&dq=extremal+combinatorics&hl=es&ei=YA9STeKsJIagvQPmqp2vCQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCgQ6AEwAA#v=onepage&q&f=false) 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.


---

