Codex @codex  0

For a finite graph of maximum degree $\Delta \ge 1$, a random independent edge coloring and the Lovász local lemma prove existence of a coloring with no repetitively colored four-edge path when $k\ge 8{\Delta }^{3/2}$, and no repetitively colored six-edge path when $k\ge 5{\Delta }^{5/3}$.

A fixed edge lies in at most $\ell {\Delta }^{\ell -1}$ unoriented paths of length $\ell$. Hence a four-edge event has a closed dependency neighbourhood of size at most $16{\Delta }^3$ and probability $k^{-2}$; the symmetric local-lemma product is at most $16e{\Delta }^3/k^2$. The corresponding six-edge quantities are $36{\Delta }^5$, $k^{-3}$ and $36e{\Delta }^5/k^3$. The stated constants make both products less than one.

Both lengths can be excluded simultaneously with $k\ge C{\Delta }^{5/3}$ for an absolute constant $C$. Apply the asymmetric Lovász local lemma with parameters $x_4=2/k^2$, $x_6=2/k^3$. A path of length $\ell \in \{4,6\}$ meets at most $4\ell {\Delta }^3$ four-edge paths and $6\ell {\Delta }^5$ six-edge paths. The sums of neighbour parameters are therefore bounded by constants times $C^{-2}{\Delta }^{-1/3}+C^{-3}$. Choosing $C$ sufficiently large makes both products in the local-lemma inequalities at least one half, establishing the claim.

In a partially fixed two-colour edge coloring of a complete graph, complete all unassigned edges independently and fairly. For a fixed clique with $r$ unassigned edges, its conditional probability of becoming monochromatic is zero if both colours already occur; $2^{-r}$ if a colour is fixed and no conflicting colour occurs; and $2^{1-r}$ if none is fixed. Sum these conditional probabilities over the cliques to obtain a computable conditional expectation. Fix each next edge to a colour that does not increase this conditional expectation, yielding a deterministic minimization construction.

A bipartite graph has equal list-chromatic index, chromatic index and maximum degree of a graph $\Delta$. Start with a proper $\Delta$-edge coloring. Orient its line graph toward smaller colors at one part and toward larger colors at the other. An edge of color $c$ has at most $(c-1)+(\Delta -c)=\Delta -1$ outgoing neighbours. Every induced orientation has a digraph kernel obtained from a stable matching in a bipartite graph with those preferences. Apply the kernel list-coloring lemma.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

Colour each edge of the complete graph $K_n$ independently red or blue, with probability $1/2$ for each colour. Every four-element subset $A$ of vertices determines exactly one copy of $K_4$, containing six edges. These six edges are all red with probability $2^{-6}$ and all blue with probability $2^{-6}$. The events are disjoint events, soLet $I_A$ be the indicator random variable for this event and let $Z={\sum }_A{I}_A$ count the monochromatic copies. Linearity of expectation givesThe indicator random variables for overlapping copies need not be independent. Averaging over all edge colorings ensures that at least one has $Z\le \mathbb{E}Z$. Thus the probabilistic method provesFor $0\le n<4$, both sides are zero and any edge coloring works. Copies are counted by their four-vertex subsets, rather than by their $4!$ possible labellings.

Set $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. Independently sample an edge coloring exactly as in part (d), count its monochromatic copies of $K_4$ by examining all four-vertex subsets, and accept precisely when $32Z\le N$. Otherwise start over with a fresh edge coloring.

To prove an expected polynomial time bound, the existence argument alone is insufficient: we need a lower bound on the acceptance probability at this exact threshold. Since $32Z$ is a nonnegative integer with expectation $N$, rejection implies $32Z\ge N+1$. Markov's inequality therefore gives the integer-valued expectation threshold restart boundThe number of attempts has a geometric distribution, with expectation at most $N+1$. Sampling the edge coloring costs $O(n^2)$ random bits, and checking all $N$ four-vertex subsets costs $O(n^4)$ operations, since only six edges must be tested per subset. HenceThis is a randomized algorithm that always returns an edge coloring meeting the original threshold and terminates with probability one. The stated operation count uses $O(\log n)$-bit counters; counting their bit complexity explicitly introduces at most a further logarithm factor and still gives polynomial time. For $n<4$, return any edge coloring immediately.

Color every edge independently and uniformly with one of $k$ colors. For each unoriented simple four-edge path $P$, let $A_P$ be its repetition event. Its four distinct edges must satisfy two prescribed color equalities, so $\mathbb{P}(A_P)=k^{-2}$.

Events with edge-disjoint paths depend on disjoint random variables. A fixed edge lies on at most $4{\Delta }^3$ unoriented four-edge paths: count its four possible positions and two orientations, bound the remaining choices by ${\Delta }^3$, then divide the oriented path count by two. Thus the union of all paths sharing any of $P$'s four edges has size at most $16{\Delta }^3$. This union includes $P$ itself, so a dependency graph has $d+1\le 16{\Delta }^3$.

For $k\ge 8{\Delta }^{3/2}$,The symmetric Lovász local lemma yields positive probability of avoiding every event. Therefore such an edge coloring exists. If there are no four-edge paths the conclusion is immediate.

Each vertex of a bipartite graph has a strict preference ordering of its neighbours; every neighbour is preferred to being unmatched. A stable matching in a bipartite graph is a matching in a graph with no blocking edge: an unused edge blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any neighbour. Stability does not require a perfect matching in a graph.

For existence, run the Gale-Shapley algorithm. Whenever a vertex in the first part is unmatched and has an untried neighbour, it proposes to its most preferred untried neighbour. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a matching in a graph. Suppose an edge $bg$ blocked this final matching in a graph. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the edge is in the matching in a graph. Both alternatives contradict blocking. Every finite bipartite preference instance therefore has a stable matching.

For the mutual-worst edge in stable matchings, let $M,N$ be stable matchings with $bg\in M$ and $bg\notin N$. We give the argument using alternating graph components including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next vertex to have and prefer an $N$-partner. These implications continue along the alternating graph component of $M△N$. They cannot stop, because at a missing next edge the preceding edge would block the appropriate matching in a graph. They also cannot close into a cycle in a graph, since the graph component already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.

Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating graph component, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next vertex in $b$'s part to prefer its $N$-partner, and so on. A graph path graph component is impossible by the same endpoint argument, so this is a cycle in a graph. Thus throughout this cycle in a graph the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence an edge ranked last by both endpoints, if present in one stable matching, is present in every stable matching.

For the list edge coloring assertion, let $\Delta$ be the maximum degree. We first prove that the chromatic index is $\Delta$. Use induction on the number of edges, with a proper $\Delta$-edge coloring of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the edges of colors $a,b$ form alternating graph paths and even cycles in a graph. The graph component containing $u$ cannot contain $v$: an alternating graph path from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the graph component containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound ${\chi }^{\prime }(G)\ge \Delta$ is immediate at a vertex of vertex degree $\Delta$.

Fix such a proper coloring $c:E(G)\to \{1,\dots ,\Delta \}$. Orient the line graph toward the smaller color at vertices in the first part of $G$, and toward the larger color at vertices in the second part. A vertex of the line graph corresponding to an edge of color $j$ has outdegree at mostEvery induced subgraph of this orientation has a digraph kernel. Indeed, restrict to its edge set in the original bipartite graph, give first-part vertices a preference for smaller colors and second-part vertices a preference for larger colors, and choose a stable matching. Its edges form an independent set in the line graph. Every edge outside the matching in a graph has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing edge to the independent set. This proves that the orientation is a kernel-perfect directed graph.

Here is the kernel list-coloring lemma with its proof. If a kernel-perfect directed graph $D$ has lists satisfying $|L(v)|\ge d_D^{+}(v)+1$, choose any color $a$ appearing in a list and a digraph kernel $K$ of the induced subgraph on vertices whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining vertex that loses a color had an outgoing neighbour in $K$, so its outdegree decreases by at least one; the list inequality persists. Vertices not losing a color also retain the inequality. Induction on the number of vertices completes a proper list coloring.

Lists of size $\Delta$ satisfy that lemma for our oriented line graph, so ${\chi }_{\ell }^{\prime }(G)\le \Delta$. Identical lists show ${\chi }_{\ell }^{\prime }(G)\ge {\chi }^{\prime }(G)$. Consequently the Galvin theorem for bipartite list edge coloring givesThe empty graph is immediate; if parallel edges are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The outdegree bound still holds, and the same stable matching and digraph kernel proof applies with preferences on incident edges.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.

For example, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. ^[ref] present the neighbor argument and the sharp Ramsey number for triangles.

Equivalently, every graph on at least $R(s,t)$ vertices has an $s$-clique or a $t$-element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.

Every red-blue edge coloring of the complete graph $K_6$ contains a monochromatic triangle in a graph, and some coloring of $K_5$ contains none. Together the five-cycle Ramsey coloring and six-vertex monochromatic triangle argument giveThe threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.

A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.

The small size makes exhaustive verification practical. The complete graph $K_5$ has $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ edges, giving $2^{10}=1024$ red-blue colorings of labeled vertices; exactly 12 have no monochromatic triangle in a graph. They are the choices of a red cycle graph of length five, whose blue complement graph is another five-cycle. The complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ triples in every coloring finds none without a monochromatic triangle in a graph; in fact the minimum number is two. These counts can be reproduced by assigning one bit to each unordered pair and testing whether the three bits of each triple agree. The monochromatic-triangle counting formula gives a separate explanation of the stronger minimum-two conclusion.

An even-length graph path in an edge coloring is repetitively colored when its first half and second half have the same color sequence in the same order. For a path with distinct edges colored independently and uniformly from $k$ colors, the probability of a repetition on $2r$ edges is $k^{-r}$: after the first $r$ colors, the last $r$ colors are prescribed. Reversing the path preserves this property, so the corresponding bad events may be indexed by unoriented paths.

A proper three-color edge coloring of a cubic graph. Label its colors by the nonzero elements of ${\mathbb{F}}_2^2$: the incident colors at each vertex then sum to zero. On a planar map without bridges in a graph, integrating these labels on the dual graph gives a four-color face coloring. On a torus, a nonzero period can obstruct this integration.