Codex @codex  0

The empty family satisfies the bound, so assume $\mathcal{F}$ is nonempty and choose a graph according to the uniform distribution on a finite set $F\in \mathcal{F}$. Let $Y$ be its random vector of edge indicators, indexed by $E=\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$. Then its information entropy is $H(Y)={\log }_2|\mathcal{F}|$.

For each vertex $v$, put $S_v=\{e\in E:v\in e\}$, so $Y_{S_v}$ records the graph neighbourhood of $v$. The possible graph neighbourhoods form an intersecting family of subsets of $[n]\setminus \{v\}$: the graph intersection of any two members of $\mathcal{F}$ has no isolated vertex at $v$. A subset and its complement cannot both occur. Pairing the $2^{n-1}$ subsets into complementary pairs gives at most $2^{n-2}$ possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for $n\ge 2$. For $n=1$ the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.

Each edge belongs to exactly two of the sets $S_v$. To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset $(S_v{)}_{v=1}^n$. Each such step strictly increases ${\sum }_S|S{|}^2$, byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for $E\ne \varnothing$, the terminal chain consists of two copies of $E$ and $n-2$ empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:

Identify the Boolean hypercube $Q_n$ with the subsets of $[n]$. For a family $\mathcal{H}$, write $N(\mathcal{H})$ for its closed vertex neighbourhood, consisting of the family and all vertices at Hamming distance one from it. Order subsets first by increasing size and, within a fixed size, use lexicographic order: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the simplicial order on the discrete cube. Harper's theorem states that if $I$ is its initial segment of size $|\mathcal{H}|$, thenThus simplicial initial segments minimize the external vertex boundary for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal{H})\setminus \mathcal{H}|=|N(\mathcal{H})|-|\mathcal{H}|$. No edge boundary is involved in this assertion.

We now give the deduction Harper theorem implies the Kruskal-Katona theorem, keeping track of the two different orders. For a family $\mathcal{F}$ of $r$-sets with $r\ge 1$, adjoin every smaller set:Its closed vertex neighbourhood is exactlywhere $\nabla \mathcal{F}$ is the upper shadow. Applying Harper theorem to $\mathcal{H}$ shows that, among $r$-uniform families of fixed size, the lexicographic initial segment minimizes the upper shadow: all the lower-level contributions to the two neighbourhood sizes are identical.

To convert this into a statement about the lower shadow of a $k$-uniform family $\mathcal{G}$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes lower shadows to upper shadows, and the coordinate reversal preserves their sizes. Moreover, the resulting lexicographic order corresponds exactly to colexicographic order on the original $k$-sets: $S$ precedes $T$ in colexicographic order precisely when the largest element of $S△T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated lexicographic order. Hence a colexicographic initial segment minimizes the lower shadow, which is the Kruskal-Katona theorem. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.

For its usual numerical form, write the unique greedy binomial representationThen the Kruskal-Katona theorem saysHere is why the shadow of the colexicographic initial segment has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a colexicographic initial segment of $(k-1)$-sets. The lower shadow consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the lower shadow of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.

The Erdős-Ko-Rado theorem states that an intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, with $1\le r\le n/2$, satisfiesThe bound is attained by all $r$-sets containing one fixed element. For the proof Erdős-Ko-Rado theorem from shadows, take complements to obtain an $(n-r)$-uniform family $\mathcal{B}$ of the same size, and let $D$ be its rank-$r$ lower shadow. Every member of $D$ is disjoint from some member of $\mathcal{A}$, so $D\cap \mathcal{A}=\varnothing$. Iterating the Kruskal-Katona theorem bounds $|D|$ below by the rank-$r$ shadow of the colexicographic initial segment of size $|\mathcal{B}|$. This iteration is valid because lower shadows of colexicographic initial segments are again colexicographic initial segments, as the preceding block description shows.

If $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{n-r}\right)$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\le n-r\le n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, implyingcontrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

For an intersecting family in a product alphabet, label the alphabet by $\mathbb{Z}/k\mathbb{Z}$. Partition the words into the classesEach class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently the exact maximum isFor $k=1$ this just says that the single word may be included.

Finally, for a weakly intersecting family in a product alphabet, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an intersecting family of nonempty subsets, and the fibre over support $S$ has $(k-1{)}^{|S|}$ words. Put $w=k-1$. When $k\ge 2$, $w\ge 1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, soAll supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus the required extremal family is the strict-majority support family, with sizeThis is the weighted intersecting family bound on an odd Boolean lattice. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

Let $\mathcal{F}$ be an intersecting family. For a word $w\in [m{]}^n$, put $S(w)=\{i:w_i=1\}$. Give $w$ the red color if $S(w)$ contains some member of $\mathcal{F}$, and the blue color otherwise.

Consider any combinatorial line with active set $A\in \mathcal{F}$. At variable value $1$, $A\subseteq S(w)$, so that word is red. At variable value $2$, $S(w)\cap A=\varnothing$. No member of $\mathcal{F}$ can be contained in this $S(w)$, because every member meets $A$. Thus that word is blue. No such line is monochromatic, provingIf $\mathcal{F}$ is empty there is no permitted active set at all, so it is also not an adequate family of active coordinate sets.

Let $\mathcal{A}\subseteq [n{]}^{(r)}$ be an intersecting family, with $n\ge 2r$. By the Iterated local LYM inequality, its upper shadow in level $n-r$ satisfiesThe family of complements ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$ also lies in level $n-r$ and has cardinality $|\mathcal{A}|$. It is disjoint from the upper shadow: if $A\subseteq [n]\setminus B$ for $A,B\in \mathcal{A}$, then $A\cap B=\varnothing$, contradicting intersection. Both families fit inside the $(n-r)$th level, soThus replacing the Kruskal-Katona theorem by Local LYM gives onlyThis agrees with the Erdős-Ko-Rado theorem when $n=2r$ but is weaker when $n>2r$.

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

For $n\ge 4$, three pairwise nonisomorphic examples are:

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\ge 2r$ and $\mathcal{F}\subseteq [n{]}^{(r)}$ is intersecting, thenFor 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}|=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this upper shadow has at least $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ members, with a strict corresponding inequality above that threshold. Since these two disjoint families lie in one level of size $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, 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 giveswhich 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 takeAny two members intersect. If an $r$-set $A$ is not contained in $S$, then $|A\cap S|\le 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)}$, andindependently of $n$.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.

Replace $\mathcal{A}$ by its upward closure of a set family $\overline{\mathcal{A}}$; this remains an intersecting family and can only make the desired containment easier. Apply the regularity lemma for Boolean functions to its indicator with parameters $(\epsilon /10,p,r,\epsilon /2)$, where $r$ is chosen from part (ii) with density threshold $\epsilon /2$. We obtain a bounded set $J$ such that all but $\epsilon /2$ of the ${\mu }_p$-weighted restrictions are $(\epsilon /10,p,r)$-quasirandom.

Let $\mathcal{B}\subseteq \mathcal{P}(J)$ consist of assignments $u$ for which the restriction is quasirandom and has $p$-biased expectation at least $\epsilon /2$. Restrictions excluded because of irregularity contribute at most $\epsilon /2$, and the remaining excluded restrictions contribute at most $\epsilon /2$ by their conditional density. Hence

It remains to prove that $\mathcal{B}$ is intersecting. If disjoint $u,v\in \mathcal{B}$ existed, part (ii) would give ${\mathbb{E}}_{1/2}{f}_u>1/2$ and ${\mathbb{E}}_{1/2}{f}_v>1/2$. Couple two unbiased complementary assignments on $[n]\setminus J$. Since two subsets of a common finite probability space having measures greater than $1/2$ must intersect, some complementary pair would make both restrictions equal to one. Together with disjoint $u,v$, this would produce two disjoint members of $\mathcal{A}$, a contradiction. Therefore $\mathcal{B}$ is intersecting, proving the Dinur-Friedgut junta theorem for intersecting families with $m=|J|$.

Assume first that no two members of the uniform set family $\mathcal{A}\subseteq [n{]}^{(k)}$ meet in exactly one point. Fix $A_0\in \mathcal{A}$. Since $\mathcal{A}$ is an intersecting family, every $B\in \mathcal{A}$ then contains at least two elements of $A_0$. ConsequentlyThis proves the stated dichotomy.

If the small alternative holds, then for sufficiently large $n$ any fixed $i$ has all but at most $\epsilon \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ members of $\mathcal{A}$ containing it. Otherwise choose $A,B\in \mathcal{A}$ with $A\cap B=\{i\}$. Every $C\in \mathcal{A}$ not containing $i$ must meet both $A\setminus \{i\}$ and $B\setminus \{i\}$, soFor sufficiently large $n$ this is at most $\epsilon \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, as required.

A set family is t-intersecting if every pair of its members has at least $t$ common elements. For $r$-sets on an $n$-point ground set, the whole level is t-intersecting when $n\le 2r-t$. Ordinary intersecting families are the case $t=1$.

A set family is two-intersecting if $|A\cap B|\ge 2$ for all of its members, including $A=B$. In particular its members all have at least two elements. This is stronger than being an intersecting family.

For intersecting families of subsets of $[n]$, take each upward closure of a set family. It remains intersecting and contains at most one set in each complementary pair, so its complement as a family has density at least one half. Those complements are decreasing set families. Repeated Harris-Kleitman inequality gives intersection density at least $2^{-k}$, proving the displayed bound. For $k\le n$, the families of sets containing coordinate $i$, for $1\le i\le k$, attain equality.

Here two words must both have symbols greater than one in some common coordinate, without requiring the symbols to agree. Their supports $S(x)$ therefore form an intersecting family. The fibre of a support of size $r$ contains $(k-1{)}^r$ words, relating this problem to a weighted set family problem.

For odd $n$ and $w\ge 1$, an intersecting family contains at most one set from each complementary pair in the Boolean lattice. Choosing the larger member in every pair gives the displayed bound and is feasible, because all sets of size greater than $n/2$ intersect. For $w>1$ it is the unique maximizer; for $w=1$ other maximizing families can exist.

For an intersecting family of $r$-sets, some element $x$ is avoided by at most $(r-1{)}^2(\genfrac{}{}{0ex}{}{n-2}{r-2})$ members. If two members meet exactly at $x$, every member avoiding $x$ contains one element from each of their disjoint remainders. If no such pair exists, apply the pair-cover bound for a two-intersecting uniform family.