Codex @codex  0

For the uniform set family of vertex sets of $r$-cliques, its $(r-2)$-fold lower shadow consists of graph edges. Repeated use of the Kruskal-Katona theorem bounds clique count from edge count. Sixteen four-cliques have at least twenty-three triples in their shadow and at least eighteen edges in their second shadow, by the expansions $16=\left(\genfrac{}{}{0ex}{}{6}{4}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)$ and $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Hence a graph with fifteen edges has at most fifteen four-cliques, attained by the complete graph on six vertices.

Split a uniform set family into the section avoiding a coordinate and the section containing it, with that coordinate removed. Replace each section by a colexicographic initial segment of the same size. Induction on the ground-set size, and nesting of initial segments, show that this operation cannot enlarge the lower shadow.

Two members of this uniform set family have at least $2(t+i)-(t+2i)=t$ common points in its distinguished prefix, so it is a t-intersecting family. Nonempty indices satisfy $0\le i\le r-t$. Consecutive-family size comparison reduces to the threshold $n_{i+1}=(r-t+1)(2+(t-1)/(i+1))$: gain sets contain both newly introduced coordinates and $t+i-1$ earlier points; loss sets contain neither and $t+i$ earlier points. Counting these sets with binomial coefficients proves increase below, equality at and decrease above this threshold.

For a uniform set family, the lower shadow of its shifted set family is contained in the shifted lower shadow. Check the witness in the four patterns of membership in coordinates $i,j$. A surviving shadow member containing only $j$ must have both old shadow partners; a member containing only $i$ needs either old partner. Taking complements exchanges $C_{ij}$ with $C_{ji}$ and gives the same containment for the upper shadow. Thus coordinate shifts of a set family cannot increase either shadow or their disjoint union, the external vertex boundary of a uniform set family.

A sunflower is a delta-system: its pairwise intersections all equal one core, and its petals outside the core are pairwise disjoint. For an $s$-uniform set family, prove the displayed bound by induction on $s$. If a maximal disjoint subfamily has $r$ members, their core is empty. Otherwise its union has at most $s(r-1)$ points and meets every member. Some point belongs to more than $(s-1)!(r-1{)}^{s-1}$ members. Remove it and apply the induction hypothesis; putting it back enlarges the common core. The case $s=0$ is immediate.

A generating family consists of sets of size at most $r$ whose $r$-element supersets are exactly the prescribed uniform set family. Small-support generators express dependence on a bounded prefix rather than on the full ground set. Taking the entire family itself as generators always works, but extremal intersection problems admit much smaller supporting intervals.

Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.

An intersection-free uniform set family is a uniform set family $\mathcal{F}$ with no three distinct members $A,B,C$ satisfying $A\cap B\subseteq C$. For distinct members of a rank-$r$ family, $|A\cap B|<r$, so using strict containment gives the same restriction. Fixing one member turns the other members' intersections with it into distinct antichain traces, giving the antichain trace bound for intersection-free families.

For a finite set $A\subseteq [n]$ and a finite list $L$ of allowed intersection sizes, the displayed polynomial satisfies $p_A({\chi }_B)={\prod }_{\ell \in L}(|A\cap B|-\ell )$ at characteristic vectors of sets. For an $r$-uniform set family whose pairwise intersection sizes lie in $L\subseteq \{0,\dots ,r-1\}$, these polynomials vanish at all other family members and have nonzero values at their own members. Their restrictions are therefore linearly independent. Multilinear reduction on the Boolean cube and homogenisation on a uniform layer then prove the Ray-Chaudhuri–Wilson theorem bound.

Repeatedly take the lower shadow of a uniform set family. After $j$ steps the result consists of all subsets of its members whose size is $j$ smaller. Iterating the Kruskal-Katona theorem shows that colexicographic initial segments minimize every iterated lower shadow.

For a nonempty $r$-uniform set family, define $x>r-1$ by $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{x}{r}\right)$ using real binomial coefficients. Then its lower shadow has at least $\left(\genfrac{}{}{0ex}{}{x}{r-1}\right)$ members. This continuous estimate is often easier to use than the exact integer expansion in the Kruskal-Katona theorem.

A short proof uses coordinate shifts of a set family. In a fully left-shifted set family split at coordinate one into ${\mathcal{F}}_0$ and ${\mathcal{F}}_1$, deleting one in the present section. The shifting property implies $\partial {\mathcal{F}}_0\subseteq {\mathcal{F}}_1$, and the total lower shadow has size $|{\mathcal{F}}_1|+|\partial {\mathcal{F}}_1|$. Induct on uniformity and, at fixed uniformity, on set family size. If $|{\mathcal{F}}_1|<\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, the Pascal's identity and the size mathematical induction force $|\partial {\mathcal{F}}_0|>\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, a contradiction. The uniformity mathematical induction applied to ${\mathcal{F}}_1$, followed by the Pascal's identity, proves the estimate. Integer $x$ is sharp for the full $r$-level on $x$ coordinates.

Fix a member of size $r$. Every other member of a two-intersecting family contains a pair from that fixed member. Counting all $r$-sets containing these pairs gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{r}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ for a uniform set family.

Let ${\mathrm{CLIQUE}}_{n,m}$ be the monotone Boolean function of the edge indicators asserting that an $n$-vertex graph contains an $m$-clique. We prove a superpolynomial monotone clique lower bound using a finite lattice of approximations. The only circuit theorem assumed is the Razborov gate-by-gate approximation lemma.

Fix integers $\ell ,r\ge 2$. Consider upward-closed set families $A$ of subsets of $[n]$ of size at most $\ell$. Impose the Razborov closure rule: if $W_1,\dots ,W_r\in A$ have pairwise intersections contained in $W$, adjoin $W$ whenever $|W|\le \ell$. Also normalize a family containing a set of size zero or one to the full family, since its clique predicate is identically true. Represent it byClosed families form the finite lattice approximation for monotone clique circuits, with meet $A\cap B$ and join $\mathrm{cl}(A\cup B)$. An input edge is represented by the family of its supersets up to size $\ell$. The constant predicates have the empty and full families. The assumed approximation theorem says that a size-$S$ circuit's output disagreement is covered by at most $S$ local gate errors:

We need the Erdős–Rado sunflower lemma: an $s$-uniform set family with more than $s!(r-1{)}^s$ members contains $r$ members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has $r$ members, already the required empty-core delta-system, or its union has at most $s(r-1)$ points and meets every member. Some point then occurs in more than $(s-1)!(r-1{)}^{s-1}$ members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an $r$-closed family has at mostinclusion-minimal $s$-sets: a sunflower among those members would force its proper core and contradict minimality. This is the sunflower bound for minimal members of a Razborov-closed family.

For positive inputs choose a uniform $m$-subset $Z$ and the graph $K_Z$ having exactly the edges of its clique. Put $q=\ell rm/n$ and suppose $q\le 1/2$. A nonuniversal family has no minimal member of size at most one, so it accepts at mostof positive inputs. Here $\mathbb{P}(W\subseteq Z)=(m{)}_{|W|}/(n{)}_{|W|}\le (m/n{)}^{|W|}$.

If $K_Z$ is in a meet-error set, it contains minimal witnesses $X\in A,Y\in B$. Their union must have size greater than $\ell$, since otherwise upward closure would put it in $A\cap B$. At least one witness therefore has size greater than $\ell /2$. The same counting and the union bound give the positive clique error of a truncated lattice meet:

For negative inputs independently assign one of $m-1$ colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is $m$-clique-free. Consider one forcing step adjoining $W$. If its clique is newly accepted, $W$ is rainbow while all witnesses $W_i$ are not. Condition on the colours of $W$. The sets $W_i\setminus W$ are disjoint, so their non-rainbow events are conditionally independent. For each witness, every possible collision either involves two random petal colours or one petal colour and one fixed core colour; its probability is at mostWhen this is at most $1/2$, a step makes a negative error with probability at most $2^{-r}$. Upward closure itself introduces no extra accepted graphs, and normalization introduces no extra error beyond the forcing step that produced a set of size at most one. At most ${\sum }_{j=0}^{\ell }\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le n^{\ell +1}$ sets can be forced. The negative colouring error of a forced-set closure is therefore

Set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. For sufficiently large $n$, both probability conditions hold and $2q^2<1/2$. If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces $1/2\le 4S{q}^{\ell /2}$. If it is universal, it accepts every negative colouring input, forcing $1\le S{n}^{\ell +1}{2}^{-r}$. ConsequentlySince $\log (1/q)\ge \frac{1}{2}\log n-\log \ell$ and $r$ grows faster than $(\log n{)}^2$, both terms implyfor an absolute positive $c$ and all sufficiently large $n$. This is superpolynomial in the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.

Use the uniform Frankl-Wilson theorem: if $p$ is a prime number, $L\subseteq {\mathbb{F}}_p$ has $s$ distinct residues, $s\le \min \{r,n-r\}$, and an $r$-uniform set family $\mathcal{F}$ has distinct-member intersection sizes in $L$ modulo $p$ while $r\mathrm{mod}p\notin L$, thenHere is a polynomial method in combinatorics proof. For each $A\in \mathcal{F}$, form the intersection polynomialover ${\mathbb{F}}_p$, and use multilinear reduction on the Boolean cube so its degree is at most $s$. At the characteristic vector of $B\in \mathcal{F}$, this evaluates to zero for $A\ne B$ and is nonzero for $A=B$. Consequently these evaluation functions are linearly independent.

The low-degree evaluation rank on a uniform layer bounds their space by $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. To justify that step without division by a possibly zero residue, form the integer incidence matrix with rows $T\subseteq [n]$, $|T|\le s$, columns $r$-sets $B$, and entries $1_{T\subseteq B}$. Over the rational numbers, a row with $|T|=j$ equals ${\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)}^{-1}$ times the sum of the rows of all $s$-sets containing $T$. Thus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger minor is an integer determinant equal to zero and stays zero modulo $p$, so the same upper bound holds over ${\mathbb{F}}_p$. This proves the theorem.

For the forbidden midpoint problem, split $\mathcal{A}$ according to whether its members contain coordinate 1. Leave the containing half unchanged; complement every member of the avoiding half. Both resulting families consist of $2p$-sets containing 1, and complementation preserves their internal intersection sizes becauseWithin either transformed family, distinct intersections lie between 1 and $2p-1$ and are not $p$. Their residues are therefore in $L=\{1,\dots ,p-1\}$, whereas the set-size residue is $2p\equiv 0$. Apply the Frankl-Wilson theorem to each half and add:The factor 2 comes from splitting into two families. The unsplit family can contain disjoint sets, whose intersection residue zero equals the set-size residue and prevents this direct application. Removing the shared coordinate after splitting also gives the stronger complement splitting for forbidden midpoint intersections bound $2\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

For the construction, fix a $(p+1)$-set $B$ and let $R=[4p]\setminus B$, of size $3p-1$. The fixed-core construction avoiding midpoint intersections isTwo members of $\mathcal{F}$ intersect in at least $p+1$ points; the same is true for two complements. An intersection across the two halves has size $|X\setminus Y|\le p-1$. No intersection is $p$. The halves are disjoint because one contains all of $B$ and the other none, so

For $1\le r\le n$ and a rank-$r$ uniform set family $\mathcal{F}$, let $\partial \mathcal{F}$ be its lower shadow. Count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=r-1$. Every $A$ contributes $r$ pairs, whereas each shadow member lies in at most $n-r+1$ rank-$r$ sets. ThusThis is the Local LYM inequality. Complementation gives the upper-shadow form $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

To deduce the LYM inequality, let $\mathcal{A}$ be an antichain, ${\mathcal{A}}_r$ its rank-$r$ part, and $U_r$ all rank-$r$ sets containing some member of $\mathcal{A}$. For $r\ge 1$,The union is disjoint because an antichain member cannot contain a smaller member; every other set of $U_r$ contains a rank-$(r-1)$ superset of its smaller witnessing member. Apply the upper local inequality and put $u_r=|U_r|/(\genfrac{}{}{0ex}{}{n}{r})$:Since $u_0=|{\mathcal{A}}_0|$ and $u_n\le 1$, summing givesThus the deduction uses the local inequality explicitly, rather than quoting a separate maximal-chain argument.

Let $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, the largest rank size. The LYM sum is at least $|\mathcal{A}|/M$, proving the Sperner theorem bound. If $|\mathcal{A}|=M$, equality forces all its members onto ranks with binomial coefficient $M$. For even $n$, there is only the middle rank, so the family is that whole rank.

For $n=2m+1$, only ranks $m,m+1$ are possible, each of size $M$. Let $\mathcal{B}={\mathcal{A}}_{m+1}$. Antichainness gives ${\mathcal{A}}_m\cap \partial \mathcal{B}=\varnothing$, and local LYM gives $|\partial \mathcal{B}|\ge |\mathcal{B}|$. Since the two antichain parts together have size $M$, equality must hold. The inclusion graph between these ranks is $(m+1)$-regular on each side. Its edges from $\mathcal{B}$ already number $(m+1)|\mathcal{B}|$, so equality leaves no edge from $\partial \mathcal{B}$ to the complementary upper vertices.

The graph is connected: exchanging one element between two $m$-sets joins them through their $(m+1)$-element union, and successive exchanges connect all lower vertices; every upper vertex has a lower neighbour. Consequently $\mathcal{B}$ is either empty or the entire upper rank. This connectedness of adjacent-level incidence in a Boolean lattice excludes mixed extremizers. HenceThere is one choice for even $n$ and two for odd $n$. For $n=0$, the sole maximum family is $\{\varnothing \}$, agreeing with this description.

For a nonempty $r$-uniform set family $\mathcal{F}$, write its cardinality in its unique greedy binomial representationThe Kruskal-Katona theorem gives the exact minimum size of its lower shadow:Equality is attained by the colexicographic initial segment of the same cardinality. The empty family has empty shadow. In colexicographic order, $A$ precedes $B$ exactly when the largest point of $A△B$ belongs to $B$. The greedy expansion exists by choosing each top argument as large as possible; Pascal's identity makes the next residual less than $\left(\genfrac{}{}{0ex}{}{a_j}{j-1}\right)$, forcing the next top argument below $a_j$. This also proves uniqueness.

Here is a proof by UV-compression of the theorem, including the step that controls the lower shadow. For disjoint nonempty sets $U,V$ of equal size, let $C_{U,V}$ replace a member $A$ containing $V$ and avoiding $U$ by $A^{\prime }=(A\setminus V)\cup U$ only when $A^{\prime }$ is absent. Other members stay. This UV-compression preserves cardinality. Allow only $\max U<\max V$, and at each step choose a changing compression with $|U|=|V|$ as small as possible. Every smaller allowed UV-compression then fixes the current family.

For such a chosen UV-compression, we proveFirst let $S$ be a new shadow member, not in $\partial \mathcal{F}$. It has the form $A^{\prime }\setminus \{x\}$ for a moved member $A$. If $x\in U$, choose $y\in V$ with $y\ne \max V$ when $|V|>1$. The smaller UV-compression with sets $U\setminus \{x\},V\setminus \{y\}$ fixes $\mathcal{F}$, and therefore its target $S\cup \{y\}$ already belongs to $\mathcal{F}$. This would put $S$ in the old shadow, a contradiction. For $|V|=1$ the same target is simply $A$, giving the same contradiction without a compression. Hence $x\notin U$. Now $A\setminus \{x\}$ is an old shadow member whose compression target is $S$; since $S$ was absent, it appears in the compressed shadow.

It remains to check that a surviving old shadow member is not removed on the right side. Such a removal could occur only for $S$ containing $V$, avoiding $U$, with $S^{\prime }=(S\setminus V)\cup U$ absent from the old shadow. A witness $B=S\cup \{x\}$ in the compressed family must be a retained old member, since newly moved members avoid $V$. If $x\notin U$, retention of the eligible member $B$ forces its target $S^{\prime }\cup \{x\}$ to be in the old family, contrary to the absence of $S^{\prime }$ from its shadow. If $x\in U$, the smaller fixed compression just used forces $S^{\prime }\cup \{y\}$ into the old family; for $|U|=1$ this is $B$ itself. Again there is a contradiction. This proves the containment, and hence the chosen compression cannot increase lower shadow cardinality.

Each change strictly decreases the integer potential ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}{2}^a$. The procedure therefore terminates. Its terminal family is an initial segment of colexicographic order: otherwise take an absent earlier set $X$ and a present later set $Y$. The choice $U=X\setminus Y,V=Y\setminus X$ is an allowed changing compression. Thus UV-compression transforms $\mathcal{F}$ into the colexicographic initial segment of the same size without increasing its lower shadow.

Finally compute that shadow. The first block comprises all $r$-subsets of $[a_r]$ and contributes $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ shadow members. The next block has maximum point $a_r+1$ and its remaining $(r-1)$ points form a smaller colexicographic initial segment. Shadow members omitting $a_r+1$ are already in the first block's shadow; those containing it are counted by the lower shadow of that smaller initial segment. Recursion through the binomial representation gives precisely the displayed sum. This completes the proof.

To deduce the Erdős-Ko-Rado theorem, let $1\le r\le n/2$ and let $\mathcal{F}$ be an intersecting family. Put $k=n-r$ and take the complement family $\mathcal{B}=\{[n]\setminus A:A\in \mathcal{F}\}$. Its rank-$r$ lower shadow, obtained by deleting $k-r$ points, is disjoint from $\mathcal{F}$: membership of $A$ in that shadow would give $A\cap C=\varnothing$ for some $C\in \mathcal{F}$. If $|\mathcal{F}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, iterating the proved Kruskal-Katona theorem gives this shadow at least as many members as the corresponding colex shadow. The colex family contains every $k$-set of $[n-1]$ and a further $k$-set containing $n$. Its rank-$r$ shadow therefore contains every $r$-set of $[n-1]$ and at least one more $r$-set containing $n$. This applies also when $k=r$, with no shadow operation. The two disjoint families would consequently have total size greater thana contradiction. Thus $\boxed{|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)}$, attained by all $r$-sets containing a fixed point.

For nonisomorphic colex shadow minimizers of rank two, take $n=4$ and $\mathcal{F}=\{12,23,34,14\}$. Its shadow has four singletons, as does the initial four-set colex segment $\mathcal{I}=\{12,13,23,14\}$. The first family is the edge set of a cycle graph; its four point degrees are all two. The second has point degrees $3,2,2,1$, so no permutation makes them isomorphic.

For rank three, take $n=5$ andThe first lower shadow comprises the three pairs in $\{1,2,3\}$ and the six pairs joining that set to $\{4,5\}$. The second shadow comprises every pair on $[5]$ except $45$. Both therefore have size nine. Their point-degree multisets are respectively $\{4,4,4,3,3\}$ and $\{5,4,4,3,2\}$, so again the two families are not isomorphic. These examples can be embedded in larger ground sets by adding unused points.

For an $r$-uniform set family $\mathcal{F}$, its lower shadow is the set family of all $(r-1)$-sets contained in a member. Write a positive integer $m$ in its unique binomial representationThe Kruskal-Katona theorem states thatFor $m=0$ the bound is zero. Equality is attained by the first $m$ $r$-sets in colexicographic order. In that order $A$ precedes $B$ when the largest element of their symmetric difference belongs to $B$.

Here is a complete UV-compression proof of the Kruskal-Katona theorem. For disjoint equal-sized sets $U,V$, put $C(A)=(A\setminus V)\cup U$ when $A$ contains every element of $V$ and no element of $U$, and put $C(A)=A$ otherwise. The UV-compression of a set family replaces an eligible $A$ only if its image is absent. It preserves cardinality: a retained collision keeps both the original set and its already present image.

We first prove the required Shadow lemma for UV-compressions. Suppose that, for each $x\in U$, a $y\in V$ can be chosen so the set family is fixed by $C_{U\setminus \{x\},V\setminus \{y\}}$. We claimConsider a lower shadow member obtained by deleting $z$ from a moved set $A^{\prime }=(A\setminus V)\cup U$. If $z\notin U$, it is the compressed image of $A\setminus \{z\}$, an old lower shadow member. If $z=x\in U$, the smaller compression of $A$ produces $A^{\prime }\setminus \{x\}\cup \{y\}$, which is in $\mathcal{F}$ by the assumed invariance. Thus $A^{\prime }\setminus \{x\}$ already belongs to the old lower shadow; it is not eligible to move since it lacks $x$.

It remains to consider a lower shadow member $B$ from a retained original member $A=B\cup \{z\}$. If $B$ is not eligible to move, it stays in the compressed lower shadow. If it is eligible, let $B^{\prime }=(B\setminus V)\cup U$. When $z\notin U$, retaining the eligible $A$ means its image already belongs to $\mathcal{F}$, and that image contains $B^{\prime }$. When $z=x\in U$, the smaller compression of $A$ belongs to $\mathcal{F}$ and equals $B^{\prime }\cup \{y\}$. In either case $B^{\prime }$ is in the old lower shadow too. Consequently the collision rule retains $B$ as well. This proves the claimed containment in every case. Since compression preserves cardinality, it cannot increase lower shadow size.

If $\mathcal{F}$ is not a colexicographic initial segment, an earlier absent set $A$ and a later present set $B$ give $U=A\setminus B$, $V=B\setminus A$ with $\max U<\max V$, and a nontrivial UV-compression. Choose such a compression with $|U|$ smallest. If $|U|>1$, choose $y\in V\setminus \{\max V\}$. For every $x\in U$, the smaller compression still has its largest differing element on the $V$ side and must fix $\mathcal{F}$ by minimality. If $|U|=1$, the smaller compression is the identity. Thus the lower shadow argument applies.

Each nontrivial step strictly decreases the positive integer weightbecause the largest differing coordinate belongs to $V$. Iteration therefore terminates. A terminal set family is a colexicographic initial segment, since an earlier gap and a later member would otherwise provide another nontrivial compression. The final set family has $m$ members and no larger lower shadow.

To compute its lower shadow, take $a_r$ maximal with $\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)\le m$. All $r$-sets of $[a_r]$ occur first. The next block consists of sets containing $a_r+1$ whose remaining $(r-1)$-set runs through the initial segment of length $m-\left(\genfrac{}{}{0ex}{}{a_r}{r}\right)$. By Pascal's identity, the remainder is smaller than $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$, so its next leading top index is strictly less than $a_r$. Repeating gives the stated unique binomial representation. The first block contributes all $\left(\genfrac{}{}{0ex}{}{a_r}{r-1}\right)$ $(r-1)$-sets in $[a_r]$ to the lower shadow. Deleting $a_r+1$ from the next block contributes only sets already counted; deleting another coordinate contributes $a_r+1$ joined to the lower shadow of the smaller initial segment. This recursive decomposition gives exactly the displayed sum. The base $r=1$ has lower shadow $\{\varnothing \}$ for every nonempty set family. This completes the proof and the sharpness assertion.

Now let $\mathcal{C}$ be the set family of vertex sets of the graph's cliques of order four. Its twice-iterated lower shadow consists of edges of the graph. If there were at least sixteen such copies, choose a sixteen-member subfamily. The relevant binomial representation isThe proved theorem gives at least $\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)=23$ triples in its first lower shadow. Apply it again to any twenty-three of those triples, using $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Their edge lower shadow has at leastmembers, contradicting the fifteen available edges. Conversely, the complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges and $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ copies of $K_4$. Therefore the maximum number of copies is exactly 15.

The lower shadow consists of the sets obtained by removing one element from a member:For a nonempty uniform set family, write its size in its unique decreasing binomial coefficient expansionThe Kruskal-Katona theorem states thatA colexicographic initial segment attains equality; thus this is an exact minimum, not just an asymptotic estimate.

Here is a direct proof of the requested Lovász shadow bound, avoiding any unproved numerical interpolation of the Kruskal-Katona theorem. The real binomial coefficient means $\left(\genfrac{}{}{0ex}{}{x}{r}\right)=x(x-1)\cdots (x-r+1)/r!$. It is strictly increasing for $x>r-1$. Since the set family is nonempty and its size is an integer, necessarily $x\ge r$.

Apply the usual left coordinate shifts of a set family until the set family is fixed by every shift. A shift preserves its size and does not increase its lower shadow; the witness argument is supplied in Solution 3. Termination follows because every nontrivial shift reduces ${\sum }_{A\in \mathcal{A}}{\sum }_{i\in A}i$. It suffices to prove the inequality for this shifted set family.

Induct on $r$, and, for each fixed $r$, on $|\mathcal{A}|$. The cases $r=1$ and $|\mathcal{A}|=1$ give, respectively, the single empty shadow member and the $r$ faces of an $r$-set. Split the set family at coordinate one, writing ${\mathcal{A}}_0$ for the members avoiding it and ${\mathcal{A}}_1$ for the sets obtained by deleting it from members containing it. Every $(r-1)$-subset of a member of ${\mathcal{A}}_0$ belongs to ${\mathcal{A}}_1$: replace the one omitted coordinate by coordinate one. ThereforeThe two terms count shadow members avoiding and containing coordinate one.

Put $b=|{\mathcal{A}}_1|$. This is positive. If $b<\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, the Pascal's identity gives $|{\mathcal{A}}_0|>\left(\genfrac{}{}{0ex}{}{x-1}{r}\right)$. In this case $x>r$ and ${\mathcal{A}}_0$ is a smaller nonempty set family. The mathematical induction hypothesis on family size gives $|\partial {\mathcal{A}}_0|>\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, contradicting its containment in ${\mathcal{A}}_1$. Consequently $b\ge \left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$. Write $b=\left(\genfrac{}{}{0ex}{}{z}{r-1}\right)$, so $z\ge x-1$. The mathematical induction hypothesis on uniformity and the Pascal's identity now giveFor $r=2$ the degree-zero term is the constant one, which causes no difficulty.

For the graph application, identify a triangle-free graph with a subset of the $N$ possible edges. Removing an edge preserves being triangle-free, so $\partial {\mathcal{G}}_{m+1}\subseteq {\mathcal{G}}_m$. If ${\mathcal{G}}_{m+1}$ is nonempty, the Lovász shadow bound givesThus, for $1\le m<N$ with $p_m>0$,If the next set family is empty its probability is zero, so the same inequality holds without introducing $x_{m+1}$. If $p_m=0$, every later set family is empty; the divided expression is undefined and the correct assertion is this zero-probability conclusion.

Iterate the monotonicity of the effective ground-set parameter of a hereditary uniform layer. Whenever $p_{m+k}>0$, all the intermediate parameters are at least their layer sizes, and all factors below are nonnegative. We obtain the stronger estimateThe second inequality follows from $x_m\le N$ and the fact that $(x_m-t)/(N-t)$ decreases with $t$. If the target set family is empty, the requested bound follows directly when its right side is nonnegative. When $k>x_m+1$, the printed product can have signed factors and should instead be stopped at the first empty layer: its unrestricted signed form is not a meaningful probability bound. In the nonzero target range there is no such ambiguity. A uniformly safe extension, for $0\le k\le N-m$, isIt agrees with the printed expression whenever all its factors are nonnegative. In particular $0\le k\le m$ is always safe when $p_m>0$, and this includes the requested doubling case.

Taking $k=m$ in the nonzero range,If the $2m$-edge set family is empty the conclusion is immediate; if $2m>N$, interpreting the event as impossible gives the same conclusion. These qualifications distinguish the probability assertion from products or ratios outside their domains.

Use the external external vertex boundary conventionEquivalently, its closed graph neighbourhood is $N[\mathcal{A}]=\mathcal{A}\cup B(\mathcal{A})$. Some boundary conventions use this closed graph neighbourhood itself; because the compared set families have equal size, either convention gives the same inequality.

Order the Boolean lattice first by increasing size, and within a size by lexicographic order, with the smallest differing coordinate in the earlier set. If $I$ is the initial segment in this simplicial order on the discrete cube with $|I|=|\mathcal{A}|$, Harper inequality isIn particular, writing $S_n(t)={\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, if $|\mathcal{A}|\ge S_n(t)$ then $|N[\mathcal{A}]|\ge S_n(t+1)$.

Here is the full simplicial section compression proof. The cases $n=0,1$ are immediate. A simplicial initial segment has an initial-segment closed graph neighbourhood: it contains every smaller level, and its remaining upper level is the upper shadow of a lexicographic initial segment. That upper shadow is lexicographic initial because a set has a face in the segment exactly when its earliest face does, and earliest faces preserve lexicographic order.

Assume the result in dimension $n-1$. For a coordinate $i$, delete it from the present section and write the two sections as ${\mathcal{A}}_0,{\mathcal{A}}_1$. Their neighbourhood sections are exactlyReplace both sections by equally large simplicial initial segments $I_0,I_1$. The mathematical induction hypothesis controls each internal neighbourhood. Both sets in each new union are initial segments, so that union has size equal to the larger of their sizes. The corresponding old union has at least that size. Therefore this simplicial section compression does not enlarge $N[\mathcal{A}]$.

Repeatedly compress any noninitial section. Every change strictly reduces the sum of the global simplicial positions of the set family members, so the process terminates at a set family $\mathcal{C}$ compressed in every section. Suppose an earlier vertex $X$ is missing while a later vertex $Y$ is present. If they agree in any coordinate, they contradict compression of that coordinate's section. Thus $Y=[n]\setminus X$. They must also be consecutive in simplicial order: an intermediate vertex, whether present or absent, would create another inversion and would have to equal one of these two complementary vertices. No other inversion is possible for the same reason. Hence $\mathcal{C}$ is either the required initial segment or that segment with its last vertex $X$ exchanged for the next vertex $Y$, with $X,Y$ complementary.

For completeness, these terminal families for simplicial section compression can be checked explicitly. If $n=2k+1$, the exceptional consecutive vertices are the last $k$-set $X=\{k+2,\dots ,2k+1\}$ and first $(k+1)$-set $Y=\{1,\dots ,k+1\}$. For $k\ge 1$, the initial segment is all levels through $k$. After the exchange every vertex of size at most $k+1$ is still in its closed graph neighbourhood: a $(k+1)$-set has at least two $k$-faces, so deleting the one face $X$ cannot remove it, and $X$ itself neighbours a retained smaller set. Thus the new neighbourhood contains the old one. For $k=0$, the two single-vertex set families have the same neighbourhood.

If $n=2k$, the exceptional pair is $X=\{1,k+2,\dots ,2k\}$ and $Y=\{2,\dots ,k+1\}$. The initial segment consists of every level below $k$ and all $k$-sets containing coordinate one. Its closed graph neighbourhood consists of every level through $k$ and the $(k+1)$-sets containing coordinate one. For $k\ge 2$, each of the latter has $k\ge 2$ faces containing coordinate one, so deleting $X$ removes no such neighbour. Every lower level remains covered. For $k=1$, the added vertex $Y$ itself keeps the sole two-element neighbour covered. Again the exchange does not decrease the neighbourhood. These are the only complementary consecutive pairs, as is seen by checking the central ranks and the lexicographic transition between middle-rank sets containing and avoiding coordinate one.

We have reached a set family whose neighbourhood is at least the initial segment's, without increasing the original neighbourhood. This proves Harper inequality by mathematical induction, including the exceptional compressed set families often omitted from the argument.

For the final request, the usual two-coordinate shift does not increase the boundary of a uniform set family. To see this carefully, let $i\ne j$ and let $C_{ij}$ move a set containing $j$ but not $i$ to its partner with $j$ replaced by $i$, only if that partner is absent. For any uniform set family $\mathcal{F}$,Here is the local witness check for the lower shadow inclusion. A shadow member containing neither or both of $i,j$ has an old witness after possibly exchanging $i,j$ in that witness. For a paired shadow vertex containing $i$ only, either its old version or its $j$-partner has an old witness, which suffices for its membership in the shifted shadow. For a vertex containing $j$ only that survives in the new shadow, its new witness either contains both coordinates, supplying both old shadow partners directly, or is an unshifted $j$-only witness whose $i$-partner was already present. In either event both old shadow partners existed, which is exactly the condition for the $j$-vertex to survive the shadow shift. This exhausts the coordinate patterns.

Taking complements converts an upper shadow into a lower shadow and converts $C_{ij}$ into $C_{ji}$, proving the second inclusion. Each shift preserves cardinality on the shadow level. The external boundary of an $r$-uniform set family is the disjoint union of its lower and upper shadows, soThe endpoint levels $r=0,n$ have an empty shadow on one side and obey the same conclusion.