Codex @codex  0

Let $G$ be a finite undirected $d$-regular graph on $N$ vertices, with adjacency matrix $A$ and normalized random walk matrix $P=A/d$. Define edge expansion and normalized conductance byAn expander family has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a regular graph the constant vector is an eigenvector of $P$ with eigenvalue one. Write its eigenvalues as $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -1$, and let $\delta =1-{\mu }_2$. This spectral gap measures the energetic cost of departing from a constant function.

For every mean-zero vector $f$, the spectral theorem and the graph's energy identity giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus a uniform spectral gap gives uniform edge expansion when $d$ is fixed. This also bounds exterior vertex expansion: each exterior vertex accounts for at most $d$ boundary edges, so $|N(S)\setminus S|\ge e(S,S^c)/d$.

For the converse, take a mean-zero eigenvector $f$ for ${\mu }_2$ and choose its sign so that its positive support has at most $N/2$ vertices. Put $g=f^{+}$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_2^2$. For the threshold sets $S_t=\{v:g(v{)}^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions:Hence bounded-degree regular families have uniform edge expansion exactly when their second-largest normalized eigenvalue stays uniformly below one.

Absolute eigenvalues give additional information. Put $\rho ={\max }_{i\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_T$, so internal edges are counted as oriented incidences. A small $\rho$ makes edge counts resemble uniformly distributed edges. It also gives rapid random walk mixing: starting at a vertex, $P^t$ contracts the mean-zero component of its point mass by at most ${\rho }^t$ in Euclidean norm; Cauchy-Schwarz inequality then gives total variation distance at most $\frac{1}{2}\sqrt{N}{\rho }^t$ from the uniform distribution. A bipartite graph has eigenvalue $-1$ and its non-lazy walk alternates sides, even if it has good edge expansion. The lazy walk $(I+P)/2$ has nonconstant eigenvalues between zero and $1-\delta /2$, resolving this periodicity. It is important to distinguish the gap $1-{\mu }_2$ controlling cuts from the absolute bound controlling non-lazy mixing.

Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus at least one qualifying list exists. Fix it once and for all.

Let $H$ be the Cayley graph on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled graph, allowing repeated edges and loops in this intermediate construction. Its characters $x\mapsto (-1{)}^{u\cdot x}$ form an orthogonal eigenbasis, with the displayed averages as normalized eigenvalues. Therefore $\rho (H)\le 1/10$. Each loop counts as one transition port; degrees here mean row sums of the adjacency matrix.

We next define the zig-zag product and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected graph $F$ gives an involution ${\mathrm{Rot}}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular graph $H_0$ has vertex set $[D_0]$, the product has vertices $(v,a)\in V(F)\times [D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ vertices, and has degree $d^2$.

Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of ${\mathrm{Rot}}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe operator is symmetric, so its mean-zero operator norm is bounded by this same quantity. No unproved product spectral estimate is needed.

Start with the loop-inclusive complete graph $G_0$ on $D$ vertices, whose normalized matrix is $J/D$ and whose nonconstant eigenvalues are all zero. Given a $D$-regular $G_t$, its two-step graph $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step edge by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the vertex set of the fixed graph $H$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/2$, since $(1/2{)}^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted edge expansion at least $D/4$ for every $G_t$.

To obtain ordinary simple graphs, delete loops and merge parallel edges. The maximum degree is at most $D$, and any one unordered vertex pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, givingThese simple graphs form an expander family. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive edge rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output edge. This is squaring and zig-zag iteration yields bounded-degree expanders. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the eigenvalues while the product restores a constant degree.

Write $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ for the $k$th uniform layer of the Boolean cube. For $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, $1\le k\le n$, its lower shadow is $\partial \mathcal{F}=\{B:|B|=k-1,B\subset A\text{ for some }A\in \mathcal{F}\}$. The Local LYM inequality statesTo prove it, count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=k-1$. Each $A$ contributes $k$ pairs; each member of the lower shadow contributes at most $n-k+1$. Thus $k|\mathcal{F}|\le (n-k+1)|\partial \mathcal{F}|$, which is exactly the displayed Local LYM inequality. The corresponding upper shadow inequality follows either by taking complements or by counting upward inclusion pairs.

For an antichain $\mathcal{A}\subseteq \mathcal{P}([n])$, put ${\mathcal{A}}_k=\mathcal{A}\cap \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$. The LYM inequality isFor the first proof, set ${\mathcal{B}}_n={\mathcal{A}}_n$ and recursively ${\mathcal{B}}_k={\mathcal{A}}_k\cup \partial {\mathcal{B}}_{k+1}$. Every member of ${\mathcal{B}}_{k+1}$ is a subset of an original member of $\mathcal{A}$ of size at least $k+1$. Consequently ${\mathcal{A}}_k$ and $\partial {\mathcal{B}}_{k+1}$ are disjoint: otherwise one original member would properly contain another, contradicting the antichain condition. The Local LYM inequality now givesIterating down to $k=0$ bounds the desired sum by $|{\mathcal{B}}_0|\le 1$, proving the LYM inequality.

For the second proof, a permutation $(i_1,\dots ,i_n)$ determines a maximal chain in a Boolean lattice through the successive initial subsets $\varnothing ,\{i_1\},\dots ,[n]$. A member $A$ of size $k$ lies on exactly $k!(n-k)!$ of these $n!$ maximal chains in a Boolean lattice. An antichain meets each such chain in a partially ordered set at most once. Counting its incidences with the maximal chains in a Boolean lattice therefore yields ${\sum }_{A\in \mathcal{A}}|A|!(n-|A|)!\le n!$. Division by $n!$ is the LYM inequality again.

The Sperner theorem says that an antichain has at most $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members. Indeed $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le M$ for every $k$, soThe middle uniform layer of the Boolean cube attains the bound. For equality in Sperner theorem, equality throughout forces every member to lie in a layer of maximum size. If $n=2k$, this forces $\mathcal{A}=\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$.

If $n=2k+1$, only ranks $k$ and $k+1$ are possible. Let $\mathcal{L}={\mathcal{A}}_k$, $\mathcal{U}={\mathcal{A}}_{k+1}$, and $\mathcal{S}=\nabla \mathcal{L}$ be the upper shadow. The antichain condition gives $\mathcal{U}\cap \mathcal{S}=\varnothing$. The Local LYM inequality for the two equally sized middle layers gives $|\mathcal{S}|\ge |\mathcal{L}|$, while $|\mathcal{L}|+|\mathcal{U}|=M$ forces $|\mathcal{S}|=|\mathcal{L}|$ and $\mathcal{U}=\left(\genfrac{}{}{0ex}{}{[n]}{k+1}\right)\setminus \mathcal{S}$.

Consider the inclusion bipartite graph between these two middle layers. It is a $(k+1)$-regular graph. Since $|\mathcal{S}|=|\mathcal{L}|$, all $(k+1)|\mathcal{S}|$ edges incident to $\mathcal{S}$ must come from $\mathcal{L}$; there are no edges from its complement on the lower side into $\mathcal{S}$. This bipartite graph is a connected graph: any two $k$-subsets can be joined by single-element exchanges, and each exchange passes through their common $(k+1)$-superset; every upper vertex has a lower neighbour. For $k=0$ it is just one edge. Hence either $\mathcal{L}=\varnothing$ or $\mathcal{L}$ is the whole lower layer. We have proved the complete classification:The two possibilities coincide for even $n$; for $n=0$ the unique maximum antichain is $\{\varnothing \}$.

Finally enumerate the members of the separating set system as $A_1,\dots ,A_m$ and encode each point $i\in [n]$ by $T_i=\{a\in [m]:i\in A_a\}$. Separation of the ordered pair $(i,j)$ means $T_i\setminus T_j\ne \varnothing$. Applying the hypothesis also to $(j,i)$ shows that the $n$ sets $T_i$ are distinct and pairwise incomparable. They form an antichain in $\mathcal{P}([m])$, so the Sperner theorem immediately gives

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.

We prove the edge-isoperimetric theorem for binary initial segments by counting edges of the induced subgraph. Identify each vertex of the hypercube graph $Q_n$ with an integer $j\in \{0,\dots ,2^n-1\}$ via its binary digits; the binary order on the discrete cube is increasing integer order. Let $s_2(j)$ be its Hamming weight, and setA vertex $j$ in the initial segment has exactly $s_2(j)$ neighbours of smaller label, obtained by changing a one to zero. Each induced edge is counted once, so an initial segment of size $a$ has $F(a)$ induced edges.

The arithmetic ingredient is the binary digit-sum inequalityHere is a proof, including the parity cases needed for arbitrary sizes. Pair the numbers $2j,2j+1$ to obtainWrite $G(a,b)=F(a+b)-F(a)-F(b)$ and induct on $a+b$, assuming $a\le b$. If $a=0$, the claim is immediate. Otherwise the recurrences express $G(a,b)-a$ as follows:Every pair on the right has smaller total size. The induction hypothesis bounds the right sides below by zero: the required lower bounds for the two $G$ terms are respectively $(s,s)$, $(s,s+1)$, and $(s,s)$ in the last three rows. This establishes the binary digit-sum inequality.

Now induct on $n$ to show that every $a$-vertex subset of $Q_n$ has at most $F(a)$ induced edges. The zero-dimensional case is immediate. Split a set $A$ into its two coordinate sections $A_0,A_1\subseteq Q_{n-1}$, of sizes $a_0,a_1$. By induction the edges within the sections number at most $F(a_0)+F(a_1)$. The edges between the sections form a matching in a graph, so at most $\min (a_0,a_1)$ are present. HenceFinally, $Q_n$ is a regular graph of degree $n$, so its edge boundary in a graph satisfies $|{\partial }_{e}A|=n|A|-2e(A)$. For the binary initial segment $C$, equality $e(C)=F(|A|)$ holds. Therefore

The diagonal Ramsey number $R(s)$ is the least positive integer $N$ such that every red-blue edge colouring of the complete graph $K_N$ contains a monochromatic copy of $K_s$.

For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the pigeonhole principle says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. HenceStarting from $R(1,s)=R(r,1)=1$ and using Pascal's identity gives the binomial upper bound for a Ramsey numberThereforewhich proves both existence and the required estimate.

To determine $R(3)$, color a cycle graph $C_5$ red and its complement graph, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\le 6$, and

The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has vertex degree at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a regular graph of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.

Finally, the monochromatic-triangle counting formula gives, for a coloring of $K_6$ with red degrees $d_v$,The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore

Let $A$ be the adjacency matrix of a graph. Since $G$ is a regular graph of degree $d$, every row of $A$ sums to $d$. Therefore, for $\mathbf{e}=(1,\dots ,1{)}^T$,so $d$ is a graph eigenvalue.

If $Av=dv$, then the quadratic form of the graph Laplacian $L=dI-A$ givesEvery summand is nonnegative, so $v_i=v_j$ along every edge. The graph is connected, hence all coordinates of $v$ are equal and $v$ is a scalar multiple of $\mathbf{e}$. Thus the $d$-eigenspace is one-dimensional. Since $A$ is a symmetric matrix, the spectral theorem for real symmetric matrices makes it diagonalizable, so the algebraic multiplicity is also one. This proves the constant eigenvector of a regular graph result.