# Finite limit to the size of an intersecting family of k-sets with no smaller intersecting set?

Suppose we have a family $F$ such that:

1. For each $A \in F$ we have $|A| = k$
2. For each $A,B \in F$ we have $A \cap B \neq \emptyset$
3. If we have $C$ such that for each $A \in F$ we get $C \cap A \neq \emptyset$ then $|C| \ge k$

Question: For a fixed $k$, can $F$ be arbitrarily large? Can $F$ be infinite?

Simple observations: For $k = 1$ it's obvious that $|F| = 1$, namely a singleton.

For $k = 2$ we have $|F| \leq 3$, because w.l.o.g $\{1,2\} \in F$, so w.l.o.g $\{1,3\} \in F$. Working towards contradiction, assume $4 \in \bigcup F$. Then a set $\{x,4\}$ exists, but then $x=1$, otherwise $\{x,4\} \cap \{1,2\} = \emptyset$ or $\{x,4\} \cap \{1,3\} = \emptyset$. So $\{1,4\} \in F$, but then if $1 \notin A$, $A \cap \{1,2\} = \emptyset$ or $A \cap \{1,3\} = \emptyset$ or $A \cap \{1,4\} = \emptyset$, therefore $A \notin F$. Hence $\{1\}$ intersects all sets in $F$, contrary to condition (3). Therefore $|\bigcup F| \le 3$, and $\{\{1,2\},\{1,3\},\{2,3\}\}$ is the biggest $F$ possible.

For $k = 3$ the Fano plane provides a family with at least 7 sets.

Obviously it's the third condition that makes a finite limit even possible, otherwise Erdos-Ko-Rado gives us arbitrarily large intersecting families.

I uploaded the same question (although I phrased it better here) to stack overflow but got no response. https://math.stackexchange.com/questions/1942413/finite-limit-to-size-of-intersecting-family-with-no-smaller-intersecting-set

• To beat the Fano plane, you can get a size-10 family for $k=3$ by taking all 3-element subsets of $\{1,2,3,4,5\}$. More generally, for any $k$ you can get a family like this by taking all $k$-element subsets of $\{1,2,\dots,2k-1\}$. – Will Brian Sep 28 '16 at 20:11
• This is one case of the construction: For each $3$ element subset of $\{{1,2,3,4,5,6\}}$ take either it or the complement. Of course that includes the case of taking the $\binom63=10$ subsets that contain $6$ (the complement of the example above) and that example can be expanded. Something similar happens for taking half the $k$-subsets of a $2k$-set. – Aaron Meyerowitz Sep 29 '16 at 5:06

It is finite. Assume that we managed to find $k+1$ sets so that intersection of any two of them is the same set $C$. Then this $C$ satisfies 3, a contradiction. If we have many sets, such $k+1$ (or as many as you wish) sets may be always found, this is a Sunflower theorem of Erdös and Rado, if I am not mistaken, and may be proved by induction on $k$, for example.