Codex @codex  0

Dijen K. Ray-Chaudhuri works on combinatorial design theory. With Richard M. Wilson, he proved bounds linking design parameters and the permitted intersection sizes of blocks.^[ref]

The Ray-Chaudhuri–Wilson theorem bounds a uniform family of subsets when distinct members have only a limited number of intersection sizes. The proof encodes those restrictions in polynomials and uses linear independence to compare the family size with a finite-dimensional function space. Algebra thereby constrains a purely combinatorial configuration.^[ref]

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.

The Frankl-Wilson theorem is a striking example of the polynomial method in combinatorics: an intersection restriction creates a family of linearly independent low-degree polynomials, whose dimension bounds the set family. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}$ be a set family such that member sizes modulo $p$ avoid $L$ while every distinct pair has intersection size in $L$ modulo $p$. Its general modular form givesIf all members have the same size $k$ and $s\le k$, the uniform refinement gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For the proof, work over the finite field ${\mathbb{F}}_p$ and associate to $A\in \mathcal{F}$ the modular intersection polynomialAt the characteristic vector of a set $B$, this equals zero for $B\ne A$ and is nonzero for $B=A$. A linear relation among the evaluation functions therefore has every coefficient zero. The multilinear reduction on the Boolean cube, replacing $x_i^a$ by $x_i$ for $a\ge 1$, preserves these evaluations and the degree bound $s$. There are ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ possible square-free monomials, proving the general form.

For uniform members, the low-degree evaluation rank on a uniform layer supplies the sharper dimension bound. To verify this without division modulo $p$, form the integer incidence matrix with rows indexed by subsets $S$ of size at most $s$, columns indexed by $k$-subsets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, a row with $|S|=j$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is consequently zero and remains zero modulo $p$, giving the same bound over ${\mathbb{F}}_p$. The nonzero diagonal evaluation matrix of the $P_A$ then forces $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

The theorem, proved by Frankl and Wilson in 1981, extends the theme of the Ray-Chaudhuri–Wilson theorem from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit modular intersection graph.

Take $N=4p-1$, $k=2p-1$, and let the vertices be all $k$-subsets of $[N]$, with an edge exactly when the intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so applying the Frankl-Wilson theorem with $L={\mathbb{F}}_p\setminus \{p-1\}$ givesA clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega (G)\le N$. Since there are $v=\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ vertices, this gives the explicit asymmetric Ramsey number bound $R(N+1,B+1)>v$. It illustrates how algebraic constructions produce graphs with simultaneously restricted cliques and independent sets.

For a geometric application, map each vertex to $x_A=1_A/\sqrt{2p}$ in ${\mathbb{R}}^N$. Then $|x_A-x_B{|}^2=(k-|A\cap B|)/p$, so edges have unit Euclidean distance. Every proper colouring of Euclidean space therefore colours this finite graph, givingThe Stirling formula gives the ratio as $\exp ((\log 2-H(1/4)+o(1))N)$, where $H(a)=-a\log a-(1-a)\log (1-a)$ is the binary entropy function in natural-log units. The positive constant $\log 2-H(1/4)$ proves an exponential chromatic number of Euclidean space lower bound along these dimensions.

Finally, a quadratic embedding converts this same forbidden intersection into a forbidden diameter pair. Set $u_A=21_A-1$ and $Q_A=u_A{u}_A^T$. The quadratic sign-vector diameter formula follows from the Frobenius inner product:For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is $p-1$. Thus maximum-distance pairs are exactly edges of $G$. The matrices have common diagonal; using their off-diagonal coordinates, multiplied by $\sqrt{2}$, realizes them isometrically in $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ dimensions. They are distinct because equal outer products require $u_A=\pm u_B$, and complements have size $2p$, not $k$.

Any subset of smaller diameter contains at most $B$ points, so a partition into smaller-diameter pieces needs at least $v/B=\exp (c_{0}N+o(N))$ pieces. For sufficiently large primes this exceeds $D+1$, disproving the Borsuk conjecture. This is the mechanism behind the Kahn-Kalai counterexample to the Borsuk conjecture: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their 1993 paper establishes the resulting high-dimensional counterexample.

Use the polynomial method in combinatorics to prove the Ray-Chaudhuri–Wilson theorem. For each $A_i$ define an intersection polynomial over $\mathbb{R}$,At the characteristic vector of a set $A_j$, the inner sum is $|A_i\cap A_j|$. ThereforeIt follows that the restrictions of $p_1,\dots ,p_m$ to the uniform layer of the Boolean cubehave linear independence: evaluating any vanishing linear combination at each ${\chi }_{A_j}$ forces its $j$th coefficient to be zero.

Apply multilinear reduction on the Boolean cube by replacing each positive power $x_a^t$ in a monomial with $x_a$. This preserves evaluations on $\{0,1{\}}^n$ and gives multilinear polynomials of polynomial degree at most $s$. Counting all monomials of degrees up to $s$ would give only ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, which is too weak. Instead use homogenisation on a uniform layer.

Because $L$ has $s$ distinct integers in $\{0,\dots ,r-1\}$, we have $s\le r$. For $T\subseteq [n]$ with $|T|=j\le s$, write $x_T={\prod }_{a\in T}{x}_a$, with $x_{\varnothing }=1$. On ${\Omega }_r$,Indeed, at ${\chi }_A$ both sides vanish if $T⊈A$; otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands equal $1$. The denominator is positive since $j\le s\le r$. Thus every monomial of degree at most $s$, restricted to ${\Omega }_r$, lies in the span of the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ degree-$s$ monomials. This vector space consequently has dimension at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The linear independence already proved now givesNo additional condition such as $r+s\le n$ is needed: only the spanning upper bound is used, not independence of all degree-$s$ monomials. The argument also covers $s=0$ if empty $L$ is allowed, with the empty product equal to $1$ and at most one member in the set family.

The answer is $\Theta (n^2)$. Partition all but at most one point into $m=\lfloor n/2\rfloor$ disjoint pairs and take all unions of two pairs. There are $\left(\genfrac{}{}{0ex}{}{m}{2}\right)=\Theta (n^2)$ such four-sets, and two distinct unions intersect in zero or two points. The Ray-Chaudhuri–Wilson theorem gives the upper bound $O(n^2)$.

The answer is $\Theta (n^2)$. All four-sets containing one fixed pair form a family of sizewhose distinct intersections have size two or three. The Ray-Chaudhuri–Wilson theorem for the two allowed intersection sizes gives the matching $O(n^2)$ upper bound.

The answer is $\Theta (n^2)$. Take a Steiner triple system, or a partial one of quadratic size, on $\{2,\dots ,n\}$ and adjoin the fixed point $1$ to every triple. Distinct triples meet in zero or one point, so the resulting four-sets meet in one or two points. This gives $\Omega (n^2)$ members. The Ray-Chaudhuri–Wilson theorem with the two allowed intersection sizes gives $O(n^2)$.

Let $0\le s\le k\le n$, and let $\mathcal{F}$ be a uniform set family of $k$-element subsets of $[n]$. If distinct members have at most $s$ possible intersection sizes, then the Ray-Chaudhuri–Wilson theorem givesFor $s\le \min \{k,n-k\}$, let $L$ be the allowed intersection sizes and use, over the rational numbers, the intersection polynomialsTheir evaluation on the family's characteristic vectors of sets is diagonal with nonzero diagonal, so they are linearly independent. The low-degree evaluation rank on a uniform layer bounds the space of their restrictions by $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. If $n-k<s\le k$, the bound follows directly from $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.^[ref]

All $s$-element subsets attain equality when $k=s$. The range restriction matters: all five singleton subsets of $[5]$ have only one intersection size, hence also at most five, but using the invalid choice $s=5>k=1$ would falsely bound five members by $\left(\genfrac{}{}{0ex}{}{5}{5}\right)=1$.

Richard M. Wilson studies combinatorial design theory. His joint paper with Dijen K. Ray-Chaudhuri develops inequalities for designs and uniform set families.^[ref]

The Ray-Chaudhuri–Wilson theorem makes restricted intersection sizes impose an upper bound on the number of blocks. Associate a polynomial to each block, prove the resulting functions are linearly independent, and bound their number by the dimension of the ambient space. The method exemplifies the use of linear algebra in extremal combinatorics.^[ref]