2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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\}$. $\endgroup$ – Will Brian Sep 28 '16 at 20:11
  • $\begingroup$ 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. $\endgroup$ – Aaron Meyerowitz Sep 29 '16 at 5:06
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the swift reply. Could you provide a source to this theorem? $\endgroup$ – Alon Navon Sep 28 '16 at 20:03
  • $\begingroup$ I think I found it myself. gilkalai.wordpress.com/2015/11/03/… $\endgroup$ – Alon Navon Sep 28 '16 at 20:09
  • $\begingroup$ Also, worth noting that not only is it finite, but there is an actual upper bound for each k. $\endgroup$ – Alon Navon Sep 28 '16 at 20:28

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.