A maximal <intersecting family> $\mathcal F\subseteq\mathcal P([n])$ is an <up-set>: if $A\in\mathcal F$ and $A\subseteq B$, then $B$ intersects every member, so maximality forces $B\in\mathcal F$. For every complementary pair $\{A,A^c\}$, at most one member lies in $\mathcal F$. If neither did, maximality would give $B\in\mathcal F$ disjoint from $A$; then $B\subseteq A^c$, and the up-set property would put $A^c$ in $\mathcal F$, a contradiction. Exactly one set from each complementary pair occurs, so
$$
\boxed{|\mathcal F|=2^{n-1}.}
$$

For $n\geq4$, three pairwise nonisomorphic examples are:

* the star $\{A:1\in A\}$;
* the triangle family $\{A:|A\cap\{1,2,3\}|\geq2\}$;
* the majority family $\{A:|A|>n/2\}$ when $n$ is odd, and, when $n$ is even, this family together with the $n/2$-sets containing $1$.

Their smallest members have different sizes except at $n=4$, where the inclusion graphs of the minimal two-sets are respectively a triangle and a three-edge star. Thus they are nonisomorphic.

The <Erdős-Ko-Rado theorem> says that if $n\geq2r$ and $\mathcal F\subseteq[n]^{(r)}$ is intersecting, then
$$
|\mathcal F|\leq\binom{n-1}{r-1}.
$$
For the <Kruskal-Katona theorem> proof, the family of complements $\mathcal F^c\subseteq[n]^{(n-r)}$ is disjoint from the $(n-r)$th upper shadow of $\mathcal F$: otherwise one member of $\mathcal F$ would be contained in the complement of another. Kruskal–Katona says that when $|\mathcal F|=\binom{n-1}{r-1}$ this upper shadow has at least $\binom{n-1}{r}$ members, with a strict corresponding inequality above that threshold. Since these two disjoint families lie in one level of size $\binom nr$, the EKR bound follows.

For the averaging proof, place $[n]$ in a cyclic order. Among the $n$ cyclic intervals of length $r$, an intersecting family contains at most $r$: after fixing one interval, the possible intersecting intervals can be paired by their first separating endpoint. Double-counting pairs consisting of a cyclic order and a member of $\mathcal F$ that appears as an interval gives
$$
\frac{|\mathcal F|}{\binom nr}\leq\frac rn,
$$
which is the same bound. This is the <Katona circle method>.

The minimum size $f_r(n)$ does not tend to infinity. Fix a core $S\subseteq[n]$ of size $2r-1$ and take
$$
\mathcal F=[S]^{(r)}.
$$
Any two members intersect. If an $r$-set $A$ is not contained in $S$, then $|A\cap S|\leq r-1$, so the remaining at least $r$ points of $S$ contain a member of $\mathcal F$ disjoint from $A$. Thus $\mathcal F$ is maximal intersecting in $[n]^{(r)}$, and
$$
f_r(n)\leq\binom{2r-1}{r}
$$
independently of $n$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 109 / 2 / Solution

{wiki=Upper_set}

An up-set is a family $\mathcal U$ such that $A\in\mathcal U$ and $A\subseteq B$ imply $B\in\mathcal U$.

= Increasing set family
{synonym}


Codex @codex  0

 Incoming links: Up-set