Codex @codex  0

If every cross-intersection of two set families on $[n]$ has even size, the spans of their indicator vectors are orthogonal in ${\mathbb{F}}_2^n$. The orthogonal complement over the binary field dimension formula bounds the sum of their dimensions by $n$, giving the displayed cardinality bound.

Appending a coordinate one to each indicator vector changes every odd cross-intersection dot product into an even one in ${\mathbb{F}}_2^{n+1}$. The argument for the even cross-intersection bound then gives the displayed bound. It is a valid bound without a claim that it is sharp.

Let $Z$ be the set of isolated vertices of the finite simple graph $G=(V,E)$. Introduce a nonnegative integer $x_v$ for every vertex. Use the integer programEvery nonisolated vertex belongs to an edge, whose inequality and the other endpoint's nonnegativity already imply $x_v\le 1$. The explicit bounds on $Z$ therefore make all variables binary. For an integer feasible point, $S=\{v:x_v=1\}$ is an independent set, and its cardinality is the objective. Conversely the indicator vector of any independent set is feasible. Thus the optimal value is the maximum independent set size. Including the isolated-vertex bounds is essential for an arbitrary graph; without them the formulation would be unbounded whenever an isolated vertex is present.

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.

Use the part-preserving bipartite four-cycle density conventionHere $G(x,y)$ is the indicator function of adjacency, and repeated labels are allowed. This is the homomorphism density convention appropriate to the four-cycle norm. We derive the needed counting and operator norm facts directly.

Let $M=(G(x,y))$ be the $n$-by-$n$ biadjacency matrix, let $1$ be the all-ones vector, let $J=11^{\mathsf{T}}$, and put $H=M-\delta J$. The degree hypothesis saysso the centered matrix $H$ annihilates $1$ on both sides. In particular, $HJ=J{H}^{\mathsf{T}}=0$, andThe two terms have zero products in either order. Expanding the matrix trace directly counts four adjacency factors:Since $J^2=nJ$ and $\mathrm{tr}J=n$, we obtainThe given upper bound therefore impliesThis computation proves the centered four-cycle identity for a biregular graph, rather than assuming a four-cycle norm identity.

The matrix $Q=H{H}^{\mathsf{T}}$ is a positive semidefinite matrix. By the spectral theorem for real symmetric matrices it has nonnegative eigenvalues ${\lambda }_j$, andMoreover, for the Euclidean norm,Indeed $\Vert H^{\mathsf{T}}v{\Vert }_2^2=v^{\mathsf{T}}Qv$, whose maximum on unit vectors is ${\lambda }_{\max }$; the Cauchy-Schwarz inequality characterization $\Vert H{\Vert }_{\mathrm{op}}={\sup }_{\Vert u{\Vert }_2=\Vert v{\Vert }_2=1}|u^{\mathsf{T}}Hv|$ also shows that $H$ and $H^{\mathsf{T}}$ have the same operator norm. Taking fourth roots thus giveswhere the error parameter $c$ is nonnegative, as in the claimed bound.

Finally use the indicator vectors $a=1_A$, $b=1_B$. Their Euclidean norms are $\sqrt{|A|}$ and $\sqrt{|B|}$, so the Cauchy-Schwarz inequality and the operator norm estimate yieldThis is the required discrepancy bound. It also holds when either subset is empty or $\delta =0$. In fact, because $H$ annihilates constants, replacing $a,b$ by $a-\alpha 1,b-\beta 1$ gives the stronger bound $c\delta n^2\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. This is the spectral discrepancy bound for a biregular graph.

We prove both the general modular intersection bound for a set family and its sharper uniform version, the Frankl-Wilson theorem. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose each member's cardinality modulo $p$ is outside $L$, whereas every intersection of two distinct members has cardinality modulo $p$ in $L$. Then the general modular intersection bound iswith $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. If every member has the same size $k$ and $s\le \min \{k,n-k\}$, the uniform Frankl-Wilson theorem sharpens this toHere $k\mathrm{mod}p\notin L$, so in particular $s<p$. Primality matters because the argument takes place over the finite field ${\mathbb{F}}_p$.

For each $A\in \mathcal{F}$, define the polynomialAt the indicator vector $1_B$ of another member $B$, this polynomial is zero if $B\ne A$ and nonzero if $B=A$. Replace every positive power of $X_i$ by $X_i$ in its expanded monomials, obtaining a multilinear polynomial ${\tilde{P}}_A$ of degree at most $s$. This multilinear reduction on the Boolean cube preserves values at every zero-one vector.

The resulting polynomials are linearly independent. Indeed, if ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at $1_B$ leaves $c_B{\tilde{P}}_B(1_B)=0$; the nonzero diagonal value forces $c_B=0$ for every $B$. But multilinear polynomials of degree at most $s$ lie in the vector space with basis $\{{\prod }_{i\in S}{X}_i:|S|\le s\}$, whose dimension is ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The bound on the dimension of a vector space gives the general modular intersection bound for a set family. This is the polynomial method in combinatorics: the intersection conditions produce an evaluation matrix with nonzero diagonal and zero off-diagonal entries.

To prove the sharper uniform bound, we first establish injectivity of inclusion between adjacent set layers. Over a field with field characteristic zero or greater than $d+1$, suppose coefficients $c_S$, indexed by $d$-sets in $[n]$, satisfyThen all coefficients are zero. For $d=0$ this is immediate. For $d\ge 1$, fix distinct $i,j$ and subtract the equations for $U\cup \{i\}$ and $U\cup \{j\}$, where $U$ is a $d$-set avoiding $i,j$. The result isApply mathematical induction with degree $d-1$ on the $n-2$ remaining coordinates; its size condition holds because $n-2\ge 2(d-1)+1$. This forces $c_{S\cup \{i\}}=c_{S\cup \{j\}}$ for every such $S$. Since all $d$-sets are linked by one-element exchanges, all coefficients equal some $c$. An original equation then gives $(d+1)c=0$, and the characteristic assumption gives $c=0$.

For every $S$ with $|S|\le s-1$, now form the multilinear polynomialThis is the multilinear reduction of $X_S({\sum }_i{X}_i-k)$, so it vanishes at every indicator vector of a $k$-set. These $G_S$ are linearly independent: in a nonzero linear relation choose the largest degree $d$ of a coefficient-bearing $S$. The degree-$(d+1)$ terms have coefficients ${\sum }_{S\subset T,|S|=d}{c}_S$. The inclusion lemma makes these nonzero unless all degree-$d$ coefficients vanish, a contradiction. It applies because $d\le s-1$, $p>s$, and $n\ge 2s$.

The $G_S$ are also independent jointly with the ${\tilde{P}}_A$. Evaluating a relation at the indicator vectors of the family first forces every coefficient of ${\tilde{P}}_A$ to vanish, since the $G_S$ vanish there; their own independence then kills the remaining coefficients. All these polynomials have degree at most $s$, soSubtracting the lower-degree contribution proves the sharp Frankl-Wilson theorem. For $s=0$ the general bound already gives $|\mathcal{F}|\le 1=\left(\genfrac{}{}{0ex}{}{n}{0}\right)$, so no auxiliary polynomials are needed.

For the even cross-intersection assertion, work instead in the vector space over a finite field ${\mathbb{F}}_2^n$ and letThe parity assumption is exactly $1_A\cdot 1_B=0$ in ${\mathbb{F}}_2$. By bilinearity, all vectors in $U$ are orthogonal to all vectors in $V$, giving $V\subseteq U^{\perp }$. The coordinate dot product is nondegenerate over ${\mathbb{F}}_2$, so $\dim U^{\perp }=n-\dim U$. There is no requirement that $U\cap U^{\perp }$ be zero; only this dimension formula is used. Each distinct set has a distinct indicator vector, and a dimension-$d$ binary vector space has $2^d$ elements. Therefore the even cross-intersection bound isThis is the even cross-intersection bound, including empty families, for which the product is zero.

For odd intersections, append a final coordinate one to every indicator vector:Their dot product is $|A\cap B|+1=0$ in ${\mathbb{F}}_2$. Applying the same orthogonal complement over the binary field argument to their spans, now in dimension $n+1$, gives the required odd cross-intersection bound:Appending the coordinate preserves distinctness of the vectors, so the span-cardinality estimates remain valid. This proves the odd cross-intersection bound directly by reducing the odd condition to an even one in a larger vector space.

If a regular graph has $c>1$ connected components, the indicator vector of each component is a $\Delta$-eigenvector. They are linearly independent, and the Laplacian argument shows that every such eigenvector is constant on each component. Therefore its multiplicity is exactly $c$, in particular greater than one.

The definition saysEquality of sets is reflexive, symmetric, and transitive, so $\sim$ is an equivalence relation. Its classes are indexed by all subsets of $\{1,\dots ,n\}$, and every subset occurs as the support of its zero-one indicator vector. The number of classes is therefore

Let $H=M-\delta J$ be the centered biadjacency matrix of an equal-part biregular graph, and put $s=\Vert H{\Vert }_{\mathrm{op}}$. For subsets $A,B$ of the two parts, their edge discrepancy is $1_A^{\mathsf{T}}H{1}_B$. The Cauchy-Schwarz inequality proves the displayed bound. If the part size is $n$, centering the two indicator vectors improves it to $sn\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. The centered four-cycle identity for a biregular graph shows that $t_4(G)\le {\delta }^4(1+c^4)$ implies $s\le c\delta n$ for $c\ge 0$.