I'm interested in intersecting families of sets of size $r$, but where no set smaller than $r$ intersects the entire family. Meaning:

  1. For every $A,B \in F$ we have $A \subset \{0,...,n-1\}$, $|A| = r$, $A \cap B \neq \emptyset$.
  2. If $|C| < r$ there exists $D \in F$ such that $D \cap C = \emptyset$.

  3. I also ask that we "use" every element in $\{0,...,n-1\}$, i.e for all $i < n$ there exists $A \in F$ such that $i \in A$.

Question: Given $r$, is there a finite upper limit to $n$?


For two simple cases, the answer is yes:

  1. For $r=1$ trivially the maximal $n$ is $1$.
  2. For $r=2$, I claim the maximal $n$ is $3$. For suppose we have in $F$ w.l.o.g sets $A = \{1,2\}$ and $B= \{1,3\}$. To "use" $4$, while intersecting $A$, we must have a set $\{1,4\}$ or $\{2,4\}$. However $\{2,4\}$ obviously doesn't intersect $B$, so we're left with $\{1,3\}$. So every "new" element $x$ we want to use after $3$ must add set $\{1,x\}$ to $F$. However this means $\{x\}$ intersects all the sets in $F$, violating requirement (2). Therefore for $r =2 $ we have $n \le 3$.

But I have no idea how to generalize this result, if it's even true for greater $r$. The Fano plane shows that for $r=3$ the maximal $n \ge 7$.

The straightforward way of creating an intersecting family is just to pick a fixed element $x$, and take all the subsets of $\{1,...,n\}$ that include $x$. However, that means $\{x\}$, a set of size $1$, intersects all the other sets in the family, violating requirement (2) for $r > 1$.


1 Answer 1


Fedor Petrov provided an affirmative answer - for each $k$ there is a finite limit to the size $F$ (and hence also to $n$).

See the question in M.O (it is phrased more clearly there): https://mathoverflow.net/questions/250951/finite-limit-to-the-size-of-an-intersecting-family-of-k-sets-with-no-smaller-int/250952#250952


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.