Codex @codex  0

Take the natural parameter range $1\le t\le r\le n$ and admissible indices $0\le i\le r-t$. Larger indices give empty set families. Write $q=r-t+1$ and set $n_0=\infty$ when discussing the first interval. For the nontrivial interval calculation, $t>1$ and $n>2r-t+1$; all prefixes used below then lie inside the ground set.

To compare consecutive complete-intersection candidate families, put $a=t+2i$ and $b=t+i$. A set in ${\mathcal{A}}_{i+1}\setminus {\mathcal{A}}_i$ has exactly $b-1$ points in $[a]$ and both of the next two points. A set in ${\mathcal{A}}_i\setminus {\mathcal{A}}_{i+1}$ has exactly $b$ points in $[a]$ and neither next point. ThereforeFor $0\le i<r-t$ these quantities are positive in the present range, and cancellation of binomial coefficients givesThe numerator minus the denominator isThus $|{\mathcal{A}}_{i+1}|$ is larger, equal or smaller than $|{\mathcal{A}}_i|$ according as $n$ is smaller, equal or larger than $n_{i+1}$. Since these thresholds decrease with the index, $n_{k+1}<n<n_k$ implies strict increase up to ${\mathcal{A}}_k$ and strict decrease thereafter:At an interior boundary $n=n_{k+1}$, the two consecutive maxima tie. The interval assertion concerns admissible $k$; taking $k>r-t$ would instead refer to an empty set family and is not a valid interpretation.

The Ahlswede-Khachatrian theorem, in its cardinality form, statesHere ${\mathcal{A}}_i$ is interpreted exactly by its intersection with $[t+2i]$, even if that prefix extends beyond $[n]$. Its size can always be written with $m_i=\min \{n,t+2i\}$ aswhere impossible binomial coefficients are zero. When $n\le 2r-t$, the whole level is $t$-intersecting and the formula gives $M=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The nontrivial case has $n>2r-t$.

First, each candidate is a t-intersecting family: two members contain at least $2(t+i)-(t+2i)=t$ common points in the prefix. This proves the lower bound for $M$. We now prove the upper bound, using only the compression and generating-family facts expressly allowed in the question.

The first auxiliary fact is that the usual left coordinate shifts of a set family preserve cardinality and $t$-intersection. Iterating them produces a left-compressed set family of the same size. The shift $S_{ab}$ with $a<b$ replaces $b$ by $a$ only when $b$ is present, $a$ is absent, and the replacement is not already in the set family. A set family is left-compressed when it is fixed by every such shift. Right compression is the reflected notion.

For the second auxiliary fact, a generating family for a uniform set family $\mathcal{G}$ means a collection of sets of size at most $r$ withThe permitted small-support generating lemma for extremal intersecting families is this precise statement: if $\mathcal{F}$ is a maximum-cardinality left-compressed $t$-intersecting set family, $n>2r-t$, andthen it has a generating set family supported on $[t+2j]$. Reflection gives the same assertion for a right-compressed extremal set family, with the supporting interval at the right end. These two auxiliary results are being used as permitted lemmas; the extremal conclusion of the theorem is established in the remaining argument.

Choose a maximum left-compressed set family $\mathcal{F}$. Its complement set familyis right-compressed, has uniformity $r^{\prime }=n-r$ and intersection parameter $t^{\prime }=n-2r+t$, and is extremal for those parameters. Indeedso complementation gives a cardinality-preserving bijection between the two classes of intersecting set families. Notice that $r^{\prime }-t^{\prime }+1=q$ too.

We need a compatibility observation, which we prove. If $G$ generates $\mathcal{F}$ and $H$ generates ${\mathcal{F}}^{\ast }$, thenOtherwise extend $G\cup H$ to a set $T$ of size $n-r+t-1$. This size is at least both $r$ and $n-r$ because $n\ge 2r-t+1$ and $t\ge 1$. Choose an $r$-set $A\subseteq T$ containing $G$, and an $(n-r)$-set $B\subseteq T$ containing $H$. Their generating properties imply $A,[n]\setminus B\in \mathcal{F}$, buta contradiction. This compatibility bound for complementary generating families is the link between the two compression directions.

Suppose first that $t>1$ and $n>2r-t+1$ lies strictly between $n_{k+1}$ and $n_k$. Put $m=t+2k$ and $h=r-t-k$. The small-support lemma gives generators $\mathcal{G}$ for $\mathcal{F}$ supported on $[m]$. It also gives generators $\mathcal{H}$ for ${\mathcal{F}}^{\ast }$ supported on $[m+1,n]$. For completeness, the dual inequality required here isWriting $D=n-2q$, it is equivalent to $kD<q(t-1)$, exactly the upper interval inequality $n<n_k$; for $k=0$ it follows from $t>1$. The dual support length is $t^{\prime }+2h=n-m$.

Either every $G\in \mathcal{G}$ has $|G|\ge t+k$, or every $H\in \mathcal{H}$ has $|H|\ge n-r-k$. If neither assertion held, a pair of smaller generators would have union size at mostcontradicting the compatibility bound. In the first alternative, every member of $\mathcal{F}$ has at least $t+k$ points in $[m]$, so $\mathcal{F}\subseteq {\mathcal{A}}_k$. In the second alternative, each complement has at least $n-r-k$ points in $[m+1,n]$, leaving its original set with at most $r-t-k$ points there; again $\mathcal{F}\subseteq {\mathcal{A}}_k$. Therefore $M\le |{\mathcal{A}}_k|$, proving the theorem in every strict interval.

At an interior boundary $n=n_{k+1}$, with $0\le k\le r-t-1$, apply the small-support lemma at index $k+1$ to the original set family, since $n>n_{k+2}$. Its generators are supported on $[t+2k+2]$. The dual generators are still supported on $[t+2k+1,n]$, by the same dual calculation with $h=r-t-k$. Either all original generators have size at least $t+k+1$, or all dual generators have size at least $n-r-k$: failure of both would give union size at most $n-r+t-1$, again impossible. The first alternative places $\mathcal{F}$ inside ${\mathcal{A}}_{k+1}$, and the second places it inside ${\mathcal{A}}_k$. The comparison already proved gives $|{\mathcal{A}}_k|=|{\mathcal{A}}_{k+1}|$, so the common size is $M$.

It remains to cover the endpoint cases, not to assume them implicitly. For $t=1$ and $n>2r$, the small-support lemma with $j=0$ puts an extremal left-compressed set family's generators inside $\{1\}$. Its members must all contain one, giving $M\le \left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, attained by ${\mathcal{A}}_0$. For $t=1$, $n=2r$, at most one member of each complementary pair can occur, so $M\le \frac{1}{2}\left(\genfrac{}{}{0ex}{}{2r}{r}\right)=\left(\genfrac{}{}{0ex}{}{2r-1}{r-1}\right)$, again attained by ${\mathcal{A}}_0$. If $n<2r$, the whole level is intersecting.

For $t>1$ and $n=2r-t+1$, complementation changes the problem into a one-intersection problem with uniformity $q=r-t+1$. Since $n=2q+t-1>2q$, the preceding case givesattained by ${\mathcal{A}}_{r-t}$, the set family of $r$-sets avoiding the final point. For $n\le 2r-t$, every two $r$-sets meet in at least $2r-n\ge t$, so $M=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ and ${\mathcal{A}}_{r-t}$ is the whole level. Finally, $t=r$ gives $M=1$ directly. These cases, the strict intervals and their boundaries cover all $1\le t\le r\le n$, completing the proof of the stated maximum formula.

A set family shatters a set $Z$ when its traces on $Z$ include all of $\mathcal{P}(Z)$. The Sauer-Shelah lemma says that a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ which shatters no $k$-set satisfiesEquivalently, if $|\mathcal{F}|$ exceeds this sum, it shatters a $k$-set. Binomial coefficients with index greater than $n$ are zero; if $k>n$ the inequality reduces to the whole-power-set bound. The VC dimension formulation puts $k=d+1$.

We give the full inductive proof. Split $\mathcal{F}$ according to the last coordinate, deleting that coordinate from the present section, and write these two set families on $[n-1]$ as ${\mathcal{F}}_0,{\mathcal{F}}_1$. PutThe inclusion-exclusion principle gives $|\mathcal{F}|=|\mathcal{C}|+|\mathcal{D}|$. If $\mathcal{C}$ shattered a $k$-set, then $\mathcal{F}$ would shatter it too. If $\mathcal{D}$ shattered a $(k-1)$-set $Z$, both versions of each required trace, with and without the last coordinate, would occur in $\mathcal{F}$, which would shatter $Z\cup \{n\}$. Thus the two mathematical induction bounds apply:using Pascal's identity. For $n=0$ the set family has at most one member. For $k=1$, the intersection section must be empty, since any nonempty set family shatters the empty set. These supply the mathematical induction bases; the forbidden-empty-set case has an empty set family and an empty sum. Sharpness is attained by all subsets of size at most $k-1$, which cannot shatter a $k$-set.

Now fix $k\ge 1$ in the infinite-ground-set problem. Choose, using the hypothesis with $2k$, a set $Y$ of size $2k$ with at least $2^{2k-1}$ distinct traces. If its trace set family shattered no $k$-set, the Sauer-Shelah lemma would givea contradiction. Therefore some $Z\subseteq Y$ of size $k$ is shattered by the trace set family, and hence by $\mathcal{A}$ itself. Thus every finite shattering size occurs. The use of $2k$ makes the contradiction strict, even though the hypothesis only gives a half-power-set lower bound.

An infinite realization does not follow. For a concrete unbounded finite shattering without an infinite universal trace construction, partition $X=\mathbb{N}$ into disjoint finite blocksand takeEvery member is finite. Given $k$, choose $Y=B_k$; its trace set family is the full power set, so it has $2^k\ge 2^{k-1}$ members and is shattered. However, an infinite $Z$ cannot be contained in one finite block. Choose $x,y\in Z$ from different blocks. No member of $\mathcal{A}$ contains both, so $\{x,y\}$ is not a trace on $Z$. Consequently there need not be an infinite $Z$ whose traces contain every finite subset of $Z$.

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.