Codex @codex  0

For $0\le t\le k\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient with lower argument outside its usual range is zero. For $t=0$, or $n\le 2k-t$, the answer is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; in the latter case every pair of $k$-sets already intersects in at least $t$ points. The displayed candidate formula also attains this value: its largest allowed index is at least $n-k$, so every $k$-set has enough points in that candidate's block. For $t=k$ the answer is one. We prove the remaining cases without assuming the complete intersection theorem as an auxiliary result.

We first record the $t=1$ case of the Erdős-Ko-Rado theorem. For $n\ge 2k$, put the ground set in a cyclic ordering. An intersecting family contains at most $k$ of its length-$k$ intervals. To see this, rotate a selected interval to end at position $n$. Intervals ending at $k,\dots ,n-k$ miss it. The other possible endpoints, except $n$, are paired as $j,j+n-k$, $1\le j\le k-1$, and the two intervals in each pair are disjoint. Thus at most $1+(k-1)=k$ intervals are selected. Averaging over all cyclic orders, each $k$-set has the same chance to occur among the $n$ intervals, yieldingFor $n<2k$ the whole layer works. This proves the $t=1$ case, including $n=2k$ without any uniqueness assertion.

We may now suppose $2\le t<k$ and $n>2k-t$. If $n=2k-t+1$, complementation of uniform intersecting families changes the problem to an intersecting family of $(k-t+1)$-sets. The just-proved case gives $M(n,k,t)=\left(\genfrac{}{}{0ex}{}{n-1}{k-t}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. This is $|{\mathcal{F}}_{k-t}|$, the family of all $k$-sets avoiding the last coordinate. Hence it remains to treat $n\ge 2k-t+2$.

Apply coordinate shifts of a set family with $i<j$. They preserve cardinality and t-intersection. The only way a moved member could lose an intersection point with an unmoved member is that the former moves $j$ to $i$ while the latter contains $j$ and avoids $i$. The latter's shifted partner must already belong to the original family, since otherwise it too would move; that partner would have had an intersection of size less than $t$ with the original moved member, a contradiction. If both members move, their intersection size is unchanged. Every nontrivial shift decreases the sum of all coordinates in all members, so repeated shifts terminate at a left-compressed set family. We can therefore choose a maximum family $\mathcal{A}$ left-compressed.

We prove the small-support generating lemma for extremal intersecting families, including the replacement argument responsible for the threshold. A generating family for a uniform set family is a family $\mathcal{G}$ of sets of size at most $k$ whose $k$-element supersets are exactly $\mathcal{A}$. Start with $\mathcal{G}=\mathcal{A}$. A left shift of a generator still has every $k$-element extension in $\mathcal{A}$: if the extension contains the removed coordinate it already contains the old generator; otherwise reverse that shift in the extension and use left-compression of $\mathcal{A}$. Taking all left shifts of generators, then deleting inclusion-redundant generators, therefore gives an antichain of generators with the following property: every left shift of a generator contains a generator. This normalization never enlarges the support. Choose a normalized generating family whose largest support coordinate $m$ is as small as possible.

The generators themselves are t-intersecting. Indeed, if two generators intersect in fewer than $t$ points, they can be extended to $k$-sets with intersection size $\max \{|G\cap H|,2k-n\}<t$: fill their two residual quotas with disjoint points as far as possible. This contradicts the defining property of the generated family. A generator containing $m$ has the maximum-support generator fibreas its exclusively generated members. In fact, any extra coordinate $i<m$ in the prefix supplies a generator inside $G-\{m\}+\{i\}$, which avoids $m$ and also generates that member. An exact prefix $G$ contains no other generator by the antichain property.

If two generators containing $m$ have intersection exactly $t$, they must have union $[m]$: any earlier coordinate missing from both permits shifting $m$ out of one generator and lowers their intersection below $t$. Thus tight pairs of left-compressed generators have sizes summing to $m+t$. Write ${\mathcal{G}}_a$ for the generators of size $a$ containing $m$, and put $N=n-m$. Generators avoiding $m$ still meet a shortened generator in at least $t$ points, and shortened generators in classes $a,b$ still meet in at least $t$ unless $a+b=m+t$.

SupposeWe will contradict extremality or the minimality of $m$. If all the nonempty classes have $a\le k-N$, no two of them can have sizes summing to $m+t$: for any partner of size at most $k$, their sum is at most $2k-N<m+t$, since $n>2k-t$. We may therefore shorten every generator containing $m$, preserving t-intersection and generating a family containing $\mathcal{A}$. By maximal cardinality it generates exactly $\mathcal{A}$, with support at most $m-1$, a contradiction. There must be a class with $a>k-N$.

If such a class has $2a\ne m+t$, put $b=m+t-a$. Remove classes $a,b$ and insert all shortened generators from class $a$, or instead all shortened generators from class $b$. Both replacements remain t-intersecting. The first loses exactly $|{\mathcal{G}}_b|\left(\genfrac{}{}{0ex}{}{N}{k-b}\right)$ exclusively generated members and gains at least $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a+1}\right)$ new members with shortened exact prefixes and tails beyond $m$; the second gives the reversed comparison. If class $b$ is empty, the first gain is positive and contradicts extremality. Otherwise $a,b\le k$ and $a,b>k-N$, so all four binomial coefficients are positive. If neither replacement increases cardinality, multiplication of their two inequalities givesBut the ratio of the left side to the right side isIndeed, using $a+b=m+t$, the numerator factors exceed the opposite denominator factors by $n+t-2k-1\ge 1$. This contradiction excludes every noncentral class with positive fibre.

Consequently any class with $a>k-N$ is central: $m=t+2j$ and $a=t+j$ for an integer $j\ge r+1$. Shorten the central generators. Each shortened set misses exactly $j$ of the $m-1$ earlier coordinates, so some coordinate $h<m$ is absent from at least $j|{\mathcal{G}}_a|/(m-1)$ of them. Call that subfamily $\mathcal{T}$. Its members are t-intersecting: a bad pair would have arisen from a tight pair whose union was $[m]$, whereas both shortened sets avoid $h$. They also meet all unchanged generators in at least $t$ points; a conflicting class would have to be the central class itself. Remove the entire central class and insert $\mathcal{T}$. The loss relative to the unaffected generators is exactly $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a}\right)$. Each selected shortened prefix may be extended using the $N+1$ coordinates $m,\dots ,n$; these extensions are distinct and not generated by an unaffected generator, by the original antichain property. The number restored or added is at least $|\mathcal{T}|\left(\genfrac{}{}{0ex}{}{N+1}{k-a+1}\right)$. Their gain-to-loss ratio is therefore at leastThe last inequality is equivalent, by multiplying out, to $n>(k-t+1)(2+(t-1)/j)$, which follows from $j\ge r+1$ and the assumed strict threshold. This finishes the generator replacement proof of the small-support intersection lemma:Reflection gives the analogous supporting suffix for a right-compressed optimum.

The second ingredient is the compatibility bound for complementary generating families. Let $\mathcal{H}$ generate ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$, a $(n-2k+t)$-intersecting family of $(n-k)$-sets. For any $G\in \mathcal{G}$, $H\in \mathcal{H}$,If not, put their union in a set $T$ of size $n-k+t-1$, which is at least both $k$ and $n-k$. Extend $G$ within $T$ to a $k$-set $A\in \mathcal{A}$ and $H$ within $T$ to an $(n-k)$-set $B\in {\mathcal{A}}^c$. Then $B^c\in \mathcal{A}$, but $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

SetFirst suppose $n_{r+1}<n<n_r$. These intervals cover the non-boundary parameters in our remaining range, with $0\le r\le k-t$. The support lemma gives generators on the prefix $[t+2r]$. Write $k^{\prime }=n-k$, $t^{\prime }=n-2k+t$ and $r^{\prime }=k-t-r$. Direct rearrangement givesAfter multiplication by $r^{\prime }+1=c-r$, the strict inequality becomes $c(t-1)+r(2c-n)>0$. For $r>0$ this is exactly $n<n_r$; for $r=0$ it is $c(t-1)>0$. Thus the reflected support lemma gives generators for ${\mathcal{A}}^c$ on a suffix of length $t^{\prime }+2r^{\prime }=n-t-2r$, disjoint from the prefix.

If every prefix generator has size at least $t+r$, then $\mathcal{A}\subseteq {\mathcal{F}}_r$. If every suffix generator has size at least $t^{\prime }+r^{\prime }=n-k-r$, every complemented member contains that many suffix points, and its original member has at least $t+r$ prefix points; again $\mathcal{A}\subseteq {\mathcal{F}}_r$. At least one of these alternatives holds: otherwise generators of sizes at most $t+r-1$ and $n-k-r-1$ would have union of size at most $n-k+t-2$, violating compatibility. Since ${\mathcal{F}}_r$ itself is t-intersecting and $\mathcal{A}$ is maximum,

Finally suppose $n=n_{r+1}>2k-t+1$. The support lemma, now with index $r+1$, places $\mathcal{G}$ in $[t+2r+2]$. For the complement, the strict support inequality still places $\mathcal{H}$ in the suffix beginning at $t+2r+1$. These supports overlap in two coordinates, which is harmless for the union bound in compatibility. Either every $G$ has size at least $t+r+1$, placing $\mathcal{A}$ inside ${\mathcal{F}}_{r+1}$, or every $H$ has size at least $n-k-r$, placing $\mathcal{A}$ inside ${\mathcal{F}}_r$. If neither held, a pair of generators would have union of size at most $n-k+t-1$, again impossible.

The two candidate sizes agree at this boundary. In passing from ${\mathcal{F}}_r$ to ${\mathcal{F}}_{r+1}$, the gained sets have $t+r-1$ points in the old block and both new points; the lost sets have $t+r$ old-block points and neither new point. Their counts areThe ratio is one exactly when $(r+1)n=c(t+2r+1)$, that is, $n=n_{r+1}$. Therefore $M=|{\mathcal{F}}_r|=|{\mathcal{F}}_{r+1}|$ there. The full-level cases, the elementary $t=1$ proof, the complementary borderline case, and these strict-interval and boundary arguments establish the boxed cardinality theorem for every admissible parameter.

For $1\le t\le r\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient is taken as zero if its lower argument is outside its usual range.

First reduce to left-compressed set families. One of the coordinate shifts of a set family, $C_{ij}$ with $i<j$, replaces $j$ by $i$ only when the target set is absent. It preserves cardinality and the property of being t-intersecting. To verify the latter, a pair of newly moved sets has the same intersection size as its old pair. If just one member moves and its intersection with a retained member decreases, the retained member contains $j$ and avoids $i$. Its own shifted partner must already have belonged to the old family, otherwise it would have moved too. The old moved member and that shifted partner have the same intersection size as the allegedly bad new pair, a contradiction. Repeating changing shifts terminates because the sum of all point labels strictly decreases.

A generating family for a uniform set family is a collection $\mathcal{G}$ of sets of size at most $r$ such thatUse the following small-support generating lemma for extremal intersecting families, the auxiliary result permitted here. If $n>2r-t$, $j\ge 0$, andthen every maximum-cardinality left-compressed set family that is t-intersecting has a generating family contained in $\mathcal{P}([t+2j])$. Reflection gives the corresponding right-end supporting interval for a right-compressed optimum. The inequality is strict.

The main ideas of the generating lemma are as follows. When $n=2r-t+1$, its hypothesis forces $t+2j\ge n$, making the support conclusion automatic. Otherwise $n\ge 2r-t+2$. Choose inclusion-minimal compressed generators minimizing their furthest point $q$. Partition generators containing $q$ by size. A pair whose intersection would fall below $t$ on deleting $q$ must fill $[q]$ and have sizes summing to $q+t$. Compare the two replacements associated to those complementary size classes; counting their rank-$r$ extensions makes one replacement larger unless the sizes are equal. In that balanced case, put $q=t+2j+\delta$, where $\delta \ge 2$ is even. Delete $q$ from generators avoiding a suitably chosen earlier point. Averaging supplies a proportion at least $(q-t)/(2(q-1))$. The ratio of the guaranteed gain to the loss isIt exceeds one precisely when $n>(r-t+1)(2+(t-1)/(j+\delta /2))$, implied by the stated hypothesis. This contradicts maximal cardinality; redundant generators are removed after each replacement. These extension counts explain both the support bound and its strict threshold.

We also need the compatibility bound for complementary generating families, which has a short direct proof. Write $\overline{\mathcal{F}}=\{[n]\setminus A:A\in \mathcal{F}\}$. If $G$ generates $\mathcal{F}$ and $H$ generates $\overline{\mathcal{F}}$, thenOtherwise contain their union in a set $T$ of size $n-r+t-1$. Under $n>2r-t$ this size is at least both $r$ and $n-r$. Extend $G,H$ inside $T$ to sets $A,B$ of those respective sizes. Then $A,B^c\in \mathcal{F}$, whereas $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

The easy parameter ranges can now be disposed of. If $n\le 2r-t$, every two $r$-sets intersect in at least $t$ points, and $M(n,r,t)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. This is a candidate value too: choose $i=n-r$, for which the minimum possible intersection with $[t+2i]$ is exactly $t+i$. If $t=1$ and $n\ge 2r$, Question 1 gives $M(n,r,1)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=|{\mathcal{A}}_0|$. If $n=2r-t+1$, complementation of uniform intersecting families turns the problem into an intersecting family of rank $n-r=r-t+1$, on a ground set of size at least twice that rank. Question 1 then giveswith equality from that candidate, the family of all $r$-sets avoiding the last point.

It remains to treat $t>1$ and $n>2r-t+1$. Put $R=r-t+1$ andSince $N_R=2r-t+1$, there is $0\le k\le R-1$ with $N_{k+1}\le n<N_k$. Take a maximum left-compressed set family $\mathcal{F}$. Its complement family is right-compressed and has parametersIt is maximum for those parameters, since complementation is a cardinality-preserving bijection between the two intersection problems. Put $\ell =r-t-k=R-1-k$. The strict inequality $n<N_k$ impliesFor $k>0$, multiplying out reduces this to $nk<R(2k+t-1)$, exactly $n<N_k$; for $k=0$ it reduces to $t>1$. The reflected generating lemma therefore gives generators $\mathcal{H}$ for $\overline{\mathcal{F}}$ supported on

First suppose $N_{k+1}<n<N_k$. The original generating lemma supplies generators $\mathcal{G}$ supported on $X=[t+2k]$. If every $G\in \mathcal{G}$ has size at least $t+k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. The same conclusion follows if every $H\in \mathcal{H}$ has size at least $n-r-k$: every complement member then has at least that many points in $Y$, forcing each original member to have at least $t+k$ points in $X$. If neither condition holds, choose $|G|\le t+k-1$ and $|H|\le n-r-k-1$. Thencontradicting the proved compatibility bound. Thus $M(n,r,t)\le |{\mathcal{A}}_k|$, and the candidate itself attains equality.

Now suppose $n=N_{k+1}$. The earlier exceptional case excludes $k=R-1$. Since $t>1$, $n>N_{k+2}$, so the original generating lemma gives $\mathcal{G}$ supported on $[t+2k+2]$, while the same dual argument still gives $\mathcal{H}$ supported on $Y=[t+2k+1,n]$. If all $G$ have size at least $t+k+1$, then $\mathcal{F}\subseteq {\mathcal{A}}_{k+1}$. If all $H$ have size at least $n-r-k$, then $\mathcal{F}\subseteq {\mathcal{A}}_k$. Otherwise a pair with $|G|\le t+k$ and $|H|\le n-r-k-1$ violates compatibility. HenceBoth candidates are available, so this proves the maximum formula also at the boundaries.

For completeness, their equality and the maximizing intervals follow from a direct count, with no appeal to the theorem. Moving from ${\mathcal{A}}_i$ to ${\mathcal{A}}_{i+1}$ adds sets containing both new coordinates and exactly $t+i-1$ old block points, and loses sets containing neither new coordinate and exactly $t+i$ old block points. ThusIn the nontrivial range, the gain-to-loss ratio is $\frac{(t+i)(r-t-i)}{(i+1)(n-r-i-1)}$. It exceeds, equals or falls below one according as $n$ is below, equal to or above $N_{i+1}$. Since the thresholds decrease with $i$ when $t>1$, the largest candidate is ${\mathcal{A}}_k$ in each strict interval and the consecutive candidates tie at $n=N_{k+1}$. This completes the proof of the cardinality theorem in every parameter range.