Codex @codex  0

An $r$-regular graph with $r\ge 2$ and a bridge in a graph separating an odd number of vertices from the rest cannot have an $r$-colour proper edge colouring. Such a colouring would partition the edges into $r$ perfect matchings. Each perfect matching must cross the odd-sided cut of a graph, so each would have to contain its unique crossing edge, the bridge in a graph. An edge cannot belong to two colour classes.

For odd $r$, every bridge in a graph in an $r$-regular graph automatically has odd-sized sides: if $S$ is either resulting connected component of a graph, double counting gives $r|S|=2|E(S)|+1$, so parity forces $|S|$ odd. Thus an odd-$r$ regular graph with a bridge in a graph is a class two regular graph.

An $r$-regular graph is class two when its edge chromatic number exceeds $r$. For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly $r+1$. An $r$-colour proper edge colouring of an $r$-regular graph would partition its edges into $r$ perfect matchings, since every vertex would see each colour exactly once.

If $G$ is a finite connected graph simple graph that is $r$-regular graph with $r\ge 1$, then $L(G)$ is connected and every one of its vertices has degree $2r-2$. The Euler circuit criterion therefore applies.

Network reciprocity is the promotion of cooperation by the pattern of interactions in a biological population. When cooperators interact preferentially with other cooperators, their help can sustain local clusters. A graph makes the mechanism precise: individuals occupy graph vertices, and graph edges specify who interacts with whom. Recognition of a previous helper is not required.

In the donation game, let each cooperator pay a cost $c$ per neighbour and supply benefit $b$ to that neighbour. On a regular graph with four neighbours per individual, a cooperator surrounded by four cooperators receives payoff $4b-4c$; an isolated cooperator surrounded by nonhelpers receives $-4c$. Thus the same behaviour has different consequences in different local arrangements.

Hisashi Ohtsuki and colleagues derived the approximate condition $b/c>k$ for natural selection to favour cooperation on large regular graphs of degree of a vertex $k$, under weak selection. Their updating rule first removed a random individual, then let its neighbours compete for the vacancy according to biological fitness. For $k=4$, $b=5$ and $c=1$ satisfy the asymptotic condition. The rule concerns fixation probability under stated assumptions; changing the order of death and reproduction can change the result.^[ref]

The Noisy voter model combines copying with spontaneous opinion changes. On a finite connected undirected graph with $n\ge 2$ vertices, give each vertex a spin in $\{0,1\}$. At each discrete step choose a vertex uniformly. With Probability $\epsilon \in (0,1]$, replace its spin by an independent fair bit; otherwise copy a uniformly chosen neighbour. This is a Markov chain on spin configurations.^[ref]

Positive noise makes the finite chain irreducible: a sequence of refreshes can produce any configuration with positive Probability. There is also a positive holding probability, so it is aperiodic and has a unique Stationary distribution. At zero noise, the two consensus configurations are absorbing; they cease to be absorbing under positive noise.

A weighted coupling explains convergence even when the graph is not regular. Let $R(v,u)$ be the simple-random-walk transition matrix and $w_v=\mathrm{deg}(v)/(2|E|)$ its Stationary distribution. For two spin configurations use the weighted Hamming distanceCouple the two chains with the same updated vertex, refresh decision, fresh bit and copied neighbour. If ${\delta }_v$ is the current disagreement indicator, the expected one-step change in $D$ issince $wR=w$. Thus $\mathbb{E}{D}_t=(1-\epsilon /n{)}^t{D}_0$. With $w_{\min }={\min }_v{w}_v>0$, a remaining disagreement costs at least $w_{\min }$, so coupling with a stationary chain yields worst-case total variation distance at most $w_{\min }^{-1}(1-\epsilon /n{)}^t$. The time here counts single-vertex updates; switching to a rate-one clock at each vertex changes time by a factor of $n$.

For even $r\ge 2$, take the complete graph $K_{r+1}$. It is an $r$-regular graph on an odd number of vertices. Every matching in a graph has at most $r/2$ edges, so $r$ colours in a proper edge colouring could cover at most $r^2/2$ edges. ButTherefore ${\chi }^{\prime }(K_{r+1})>r$; Vizing's theorem gives ${\chi }^{\prime }(K_{r+1})=r+1$. This includes the graph triangle when $r=2$.

For odd $r\ge 3$, first construct a graph $H_r$ on $r+2$ vertices. Start with the complete graph onand delete the edges $va$, $vb$, and $c_1{c}_2,c_3{c}_4,\dots ,c_{r-2}{c}_{r-1}$. The pairing is possible because $r-1$ is even. In the initial complete graph, every vertex has vertex degree $r+1$. The distinguished vertex $v$ loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of $H_r$, with distinguished vertices $v,v^{\prime }$, and add the edge $v{v}^{\prime }$. The resulting simple graph $G_r$ is an $r$-regular graph. The added edge is the only edge between the two copies; each copy has the odd number $r+2$ of vertices.

Suppose an $r$-colour proper edge colouring existed. At each vertex, the $r$ incident edges would use all $r$ colours. Thus each colour would form a perfect matching. Any perfect matching must use $v{v}^{\prime }$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all $r$ colour classes would have to contain the same edge $v{v}^{\prime }$, a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every $r\ge 2$. The odd-$r$ construction exhibits the bridge obstruction to regular edge colouring; $H_r$ is a connected graph because every vertex other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those vertices.

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.

In a finite bipartite graph that is $k$-regular graph with $k\ge 1$, edge counting gives equal vertex-class sizes and $k|S|\le k|N(S)|$. Hall's theorem therefore supplies a perfect matching.