Historical context

List coloring was introduced independently by Vizing [26] and by Erdős, Rubin, and Taylor [15]. Dvořák and Postle introduced correspondence coloring in their 2015 preprint, published as [13], to allow the identification of colors to vary from edge to edge. This flexibility was central to their application to list coloring planar graphs. An arbitrary correspondence assignment need not admit globally consistent color names, so a list-coloring argument that uses independence across such names requires additional work.

An early step toward logarithmic coloring bounds imposed a stronger restriction on short cycles. Kim [19] proved \(\chi_{\mathrm{list}}(G)\le(1+o(1))\Delta/\log\Delta\) for graphs of girth at least five. Johansson subsequently obtained the list-coloring bounds \(O(\Delta/\log\Delta)\) for triangle-free graphs and \(O_r(\Delta\log\log\Delta/\log\Delta)\) for \(K_r\)-free graphs. His triangle-free argument is presented by Molloy and Reed [21]; the extended version of Bansal, Gupta, and Guruganesh [6] develops his recursive probability modifications and entropy estimates. Molloy [20] obtained the triangle-free list bound with leading constant \(1+o(1)\) and gave a new proof of the clique-free bound, with explicit dependence on \(r\).

Bernshteyn [8] extended Johansson’s triangle-free bound to correspondence coloring, and later extended Molloy’s asymptotic triangle-free bound and the clique-free bound to that setting [9]. In particular, the previous general upper bound for fixed \(r\ge4\) was \[\chi_{\mathrm{DP}}(G) =O_r\!\left(\frac{\Delta\log\log\Delta}{\log\Delta}\right).\] Davies, Kang, Pirot, and Sereni [11] developed a framework based on local occupancy in the hard-core model and improved the leading constants. Przybyło [23] also obtained bounds under clique exclusion in the graph whose vertices are list entries and whose edges are forbidden pairs, while retaining the maximum degree of the underlying graph as the degree parameter. These results retain the \(\log\log\Delta\) factor for a general fixed forbidden clique.

Other families of forbidden subgraphs admit the sharper order. Alon, Krivelevich, and Sudakov [2] proved that a graph whose neighborhoods each span at most \(\Delta^2/f\) edges, with \(2\le f\le\Delta^2\), has chromatic number \(O(\Delta/\log f)\). Vu [27] extended this local-sparsity bound to list coloring. Alon, Krivelevich, and Sudakov also deduced \(O_F(\Delta/\log\Delta)\) for every fixed almost bipartite forbidden graph \(F\), meaning that deleting at most one vertex from \(F\) leaves a bipartite graph. Anderson, Bernshteyn, and Dhawan [3, 4] proved correspondence-coloring bounds with leading constants \(1+o(1)\) for bipartite forbidden graphs and \(4+o(1)\) for almost bipartite forbidden graphs. Their more general theorems assume that the graph of forbidden pairs excludes \(F\) and use its maximum degree in place of \(\Delta(G)\).

More recently, Dhawan, Janzer, and Methuku [12] proved \(O_t(\Delta/\log\Delta)\) for ordinary coloring of \(K_{t,t,t}\)-free graphs, and hence for every fixed three-colorable forbidden graph. They also obtained the independence bound \((1-o(1))n\log d/d\) in terms of the average degree \(d\). Their coloring theorem concerns ordinary coloring; it does not supply a list or correspondence bound. Theorem 1 removes the \(\log\log\Delta\) factor for correspondence coloring with any fixed forbidden clique \(K_r\), \(r\ge4\).

The structural part of our argument is related to the independence problem. Ajtai, Erdős, Komlós, and Szemerédi [1] asked for a lower bound of order \(n\log d/d\) for \(K_r\)-free graphs of average degree \(d\). Shearer [24, 25] obtained the asymptotic triangle-free bound and a clique-free bound with a \(\log\log d\) loss. The companion manuscript A logarithmic independence bound for clique-free graphs [22] proves the logarithmic bound and develops the weighted multipliers, neighborhood walks, and vertex splitting used here. The recursive use of clique-free neighborhoods has a precedent in [1]; entropy increments controlling distances between walk distributions have a precedent in [7]. We adapt these ingredients to a local adjustment statement that also bounds how many entries from each list an operation affects. We establish the required weighted and dual estimates directly.

The remaining probabilistic ingredients also have established antecedents. We use the simultaneous coupling bound presented by Angel and Spinka [5], with its finite-state proof included. Concentration for sums in which each independent input affects only a bounded number of summands is the setting of Gavinsky, Lovett, Saks, and Srinivasan [17]. We derive the weighted form needed here from Finner’s generalized Hölder inequality [16] and Hoeffding’s exponential-moment bound [18]. The Lovász local lemma [14] then makes the local round estimates hold simultaneously.

The proof and its main ingredients

The proof constructs a partial coloring in small random rounds. At an uncolored vertex \(v\), each available entry \(i\in L(v)\) carries a nonnegative weight \(w_i\). Its total weight \(W_v=\sum_{i\in L(v)}w_i\) must remain bounded below, while the individual weights remain small. These two conditions guarantee many available entries. The round colors enough neighbors to make the remaining degree decrease faster than this supply of entries.

Let \(H\) be the graph whose vertices are the positive-weight entries and whose edges are the forbidden pairs in the matchings. The lists partition \(V(H)\) into independent sets. Every vertex of \(H\) has at most one neighbor in each part, and every clique of \(H\) projects to a clique in \(G\). Thus \(H\) is \(K_r\)-free. This graph allows us to work directly with the correspondences, without identifying entries from different lists.

A round independently activates each entry with probability proportional to its weight. An activated entry can be chosen if none of its neighbors in \(H\) activates. Choosing it removes all conflicting entries from the remaining lists. The potential controlling the loss of weight has three terms: an entropy relative to the initial weights, a linear penalty for lost total weight, and the incident edge mass \[D_v=\sum_{i\in L(v)}\sum_{j\in N_H(i)}w_iw_j.\] The last term measures the amount of conflicting weight around \(v\). Deleting newly colored neighbors decreases it and pays for the cost of the round.

Conventions

Neighborhoods are open; graph-distance balls include their centers. An edge or triangle has weight equal to the product of its vertex weights. Unless indicated otherwise, sums over edges and triangles are unordered. A graph homomorphism is injective on directed edges if distinct ordered adjacent pairs have distinct images. It may identify vertices that do not occur in the same directed edge. Constants implicit in \(O_r(\cdot)\) and sufficiently large thresholds may depend on \(r\), but not on the graph, lists, or matchings. Auxiliary graphs may be empty.

Dual prices and dyadic levels

A bound on total triangle mass would not guarantee the individual vertex inequalities in (5). To retain those constraints, assign prices \(x_i\ge0\) to the first inequalities in (5), and prices \(w_i y_i\ge0\) to the incidence budgets in the second inequalities. It suffices to prove that \[ \sum_i x_i g_i+\sum_{i\in J}w_i y_i\ge0 \qquad\text{for every allowed operation $(g,J)$} \tag{6}\] implies \[ \sum_i x_i t_i\le B\sum_i x_i d_i +\Lambda^4\sum_i w_i y_i. \tag{7}\] The support price in (6) includes every vertex of the listed support, even when its multiplier equals \(1\).

To justify the reduction, let \(n=|V(H)|\) and let \(\mathcal C\) be the cone in \(\mathbb R^{2n}\) generated by the operation columns \((g,\mathbf1_J)\) and the nonnegative orthant. These columns form a compact set: there are finitely many possible supports, each multiplier cube is compact, and \(f\) is continuous on \([0,U]\). Moreover, the sum of the last \(n\) coordinates of every column is at least \(1\). In any convergent sequence of elements of \(\mathcal C\), the last-coordinate sums therefore bound the total coefficients of the operation columns. Their combined contributions belong to a fixed multiple of the compact convex hull of the columns and zero. A subsequence of those contributions converges; the residual vectors then converge in the nonnegative orthant. This proves that \(\mathcal C\) is closed.

Membership of \((Bd-t,\Lambda^4\mathbf1)\) in \(\mathcal C\) is exactly the existence of the finite family in (5). If this target were outside the cone, separation would give a linear functional nonnegative on \(\mathcal C\) and negative at the target. Since \(\mathcal C\) contains the nonnegative orthant, the coefficients of that functional are nonnegative. Because \(w_i>0\), they may be written as \((x_i,w_i y_i)_i\). They would satisfy (6) and violate (7), proving the reduction.

Fix nonnegative prices satisfying (6). Applying that inequality to the drop at \(i\) and dividing by \(w_i\) gives \[ \sum_{u\in N_H(i)}x_u w_u \le(\Lambda-s_i)x_i+y_i\le\Lambda x_i+y_i. \tag{8}\] Call a vertex \(i\) good if \(x_i>y_i\), and bad otherwise. A triangle \(\{i,u,z\}\) contributes \(2(x_i+x_u+x_z)w_iw_uw_z\) to \(\sum_v x_vt_v\). For a fixed bad vertex \(i\), the sum of these contributions over triangles containing \(i\) is at most \[2w_i\left(x_i s_i^2+ s_i\sum_{u\in N_H(i)}x_u w_u\right) \le O(\Lambda^2)w_i y_i,\] by (8) and \(s_i\le\Lambda\). Summing over bad vertices, with possible overcounting, yields \[ \sum_{\substack{\{i,u,z\}\text{ triangle of }H\\ \{i,u,z\}\text{ contains a bad vertex}}} 2(x_i+x_u+x_z)w_iw_uw_z \le O(\Lambda^2)\sum_i w_i y_i. \tag{9}\] The remaining triangles have only good vertices. Their edge budget is \[ M_x=\sum_i x_i d_i =\sum_{iu\in E(H)}(x_i+x_u)w_iw_u, \tag{10}\] where the edge sum is unordered.

Good vertices have positive prices. Consider all dyadic numbers \(b=2^j\), \(j\in\mathbb Z\), such that \([b,2b)\) contains the price of a good vertex. There are only finitely many such levels. At level \(b\), call a good vertex low if \(x_i<b\), middle if \(b\le x_i<2b\), and high if \(x_i\ge2b\). Let \(H_b\) be the graph on good vertices obtained from \(H\) by deleting edges with two low endpoints or two high endpoints. Rescale the weights to \[ q_i= \begin{cases} w_i x_i/b,&i\text{ high},\\ w_i,&i\text{ low or middle}. \end{cases} \tag{11}\] The weights \(q\) and all three classifications refer to the level under consideration.

A triangle of good vertices survives at exactly one level: the level whose interval contains its median price. At that level it has at most one low and at most one high vertex, and hence at least one middle vertex. At every other level, two vertices are low or two are high, and the edge between them is deleted. The rescaling pays for the largest price even when it is much larger than the median: if \(x_i<b\le x_u<2b\le x_z\), then \[bq_iq_uq_z=x_z w_iw_uw_z.\] If a retained triangle has no high vertex, all three prices are less than \(2b\). If it has a high vertex, its \(q\)-weight incorporates that largest price divided by \(b\). In either case its contribution satisfies \[2(x_i+x_u+x_z)w_iw_uw_z\le12bq_iq_uq_z.\] Define \[ T_0=\sum_b b \sum_{\{i,u,z\}\text{ triangle of }H_b}q_iq_uq_z. \tag{12}\] We have proved \[ \sum_i x_i t_i\le12T_0+O(\Lambda^2)\sum_i w_i y_i. \tag{13}\] Consequently, a bound \(T_0=O_r(M_x)\) will imply (7) once \(B\) and the lower threshold on \(\Lambda\) are chosen.

To obtain that bound, we express the dual prices in the rescaled weights. For good vertices and original edges between them, set \[ \alpha_i=\frac{x_iw_i}{bq_i},\qquad \beta_i=\frac{y_iw_i}{bq_i},\qquad \kappa_{iu}=\frac{(x_i+x_u)w_iw_u}{bq_iq_u}. \tag{14}\] They satisfy \[ 0\le\beta_i<\alpha_i\le2,\qquad 0<\kappa_{iu}\le4,\qquad \kappa_{iu}\ge1\quad(iu\in E(H_b)). \tag{15}\] Indeed, \(\alpha_i=1\) at high vertices and \(\alpha_i=x_i/b\) at the others. If exactly one endpoint of an edge is high, then \(\kappa_{iu}\) is \(1\) plus the ratio of the other price to the high price. If both endpoints are high it is \(b/x_i+b/x_u\), and if neither is high it is \((x_i+x_u)/b\). A retained edge of the last type has a middle endpoint, proving its lower bound.

For a multiplier operation supported on good vertices, division of (6) by \(b\) gives \[ \begin{split} 0\le{}&\sum_{i\text{ good}}\alpha_i q_i f(m_i) +\sum_{\substack{iu\in E(H)\\i,u\text{ good}}} \kappa_{iu}q_iq_u(m_i-1)(m_u-1)\\ &+\sum_{i\in J}\beta_iq_i. \end{split} \tag{16}\] The edge sum here still uses the original edges of \(H\), including edges absent from \(H_b\).

The rescaling also preserves a uniform neighborhood bound: \[ \sum_{u\in N_{H_b}(i)}q_u\le e^{\ell_0}=8\Lambda. \tag{17}\] For a high vertex, all retained neighbors have their original weights, so the sum is at most \(\Lambda\). For a non-high vertex \(i\), the high neighbors have total \(q\)-weight at most \[\frac1b\sum_{u\in N_H(i)}x_uw_u \le\frac{\Lambda x_i+y_i}{b}<2(\Lambda+1),\] by (8) and goodness. The other neighbors contribute at most \(\Lambda\), proving (17).

Sparse multipliers and local edge mass

The normalized dual inequality controls the mass of edges between two nearby sets. To see this, we will increase the weights on one set and set the weights on the other to zero. The cross edges then have negative quadratic contribution. The following construction keeps the positive contribution inside the first set small. Its recursive passage to neighborhoods excluding a smaller clique is the sparse-subgraph device of Ajtai, Erdős, Komlós, and Szemerédi [1]. The mean-one weighted construction and the resulting cross estimate adapt [22]; we give the proofs with the locality and participation conditions needed here.

For sets \(S,D\) in a graph with weights \(q\), write \[q(S)=\sum_{i\in S}q_i,\qquad e_q(S,D)=\sum_{i\in S}\sum_{u\in D\cap N(i)}q_iq_u.\] This is a directed edge sum: an edge with both endpoints in \(S\cap D\) is counted twice. We specify the graph by a subscript when needed.

The triangle argument will replace vertices by copies and delete some edges. The next observation ensures that the local estimate remains available after these changes. A homomorphism \(p:F\to H_b\) is injective on directed edges if the map \((u,v)\mapsto(p(u),p(v))\) is injective on all ordered adjacent pairs of \(F\). Vertices may have several preimages, but each original directed edge has at most one preimage.

We have derived the local edge estimate solely from the dual condition and have shown that it survives the graph modifications needed below. The remaining assertion is the following triangle bound.

Section 3 proves the proposition by repeatedly reducing neighborhood weights while retaining a controlled fraction of the triangle mass. In view of (13), this completes the dual inequality and Lemma 3. The constants are chosen in this order: the sparse multiplier construction determines \(A\) and \(C_1\); the triangle bound then determines \(B\); and finally \(\Lambda_r\) is increased so that the \(O(\Lambda^2)\sum_iw_i y_i\) term is at most \(\Lambda^4\sum_iw_i y_i\).

Removing triangles of small total mass

Let \(F_b\) denote the current graph at level \(b\), initially \(H_b\), and put \[T=\sum_b b\sum_{\{a,u,v\}\text{ a triangle of }F_b}q_aq_uq_v.\] Thus initially \(T=T_0\). A triangle of \(F_b\) projects to a triangle of \(H_b\) with three distinct vertices and hence has a middle vertex. We shall use the following bound at every stage: \[ \sum_b b\sum_{\substack{a\in V(F_b)\\a\text{ middle}}} q_a q\bigl(N_{F_b}(a)\bigr)\le 2M_x. \tag{21}\] Indeed, for an edge \(au\) the quantity \(bq_aq_u\) is at most the contribution of its image edge to \(M_x\), since the coefficient \(\kappa\) on that image is at least one. An original vertex is middle at exactly one level, and a directed edge at that level has at most one preimage. Each original edge can consequently be charged at most once from each endpoint.

Suppose that all current neighborhood weights are at most \(e^\ell\), where \(32\le\ell\le\ell_0\). First delete, at every level, the vertices whose inherited prices satisfy \(x_i/b<\ell^{-4}\). To bound the triangle mass lost, fix a middle vertex \(a\) before these deletions, let \(D=N_{F_b}(a)\), and let \(S\) be the set of vertices of \(D\) being deleted. The set \(S\cup D=D\) lies in a ball of radius one and has at most one vertex in each part. Also \(q(S),q(D)\le e^\ell\), while \(\alpha_i,\beta_i\le\ell^{-4}\) on \(S\). Applying (19) with \(h=\ell\) gives \[e_q(S,D)\le C_1\bigl(\ell^{-3}q(D)+e^{-3\ell}\bigr).\] In fact \(e_q(S,D)=O_r(q(D)/\ell^2)\): when \(q(D)>\ell^{-2}\) the exponential term is absorbed by \(q(D)/\ell^2\); when \(q(D)\le\ell^{-2}\), use instead \(e_q(S,D)\le q(D)^2\). A deleted triangle has a middle vertex, which is not itself deleted, and an edge from \(S\) to \(D\) in that middle vertex’s neighborhood. Multiplying by \(bq_a\) and summing therefore bounds the loss in \(T\) by \(O_r(M_x/\ell^2)\), using (21).

After these deletions, the total edge mass over the levels satisfies \[ \sum_b b\sum_{uv\in E(F_b)}q_uq_v \le O(\log\ell)M_x. \tag{22}\] To see this, write \(x_{\min}\) for the smaller of the two prices on an original edge. If that edge has a preimage at level \(b\), then \[b\ell^{-4}\le x_{\min}<2b.\] The first inequality follows from the deletion rule, and the second from the absence of edges with two high endpoints. There are only \(O(\log\ell)\) dyadic choices for \(b\). At each such level, the edge has at most one preimage, whose mass \(bq_uq_v\) is at most the original edge’s contribution to \(M_x\).

Next delete an edge whenever the weight of its current common neighborhood is less than \(\ell^{-1}\), continuing until no such edge remains. Deleting \(uv\) destroys triangle mass at most \(bq_uq_v/\ell\). Thus (22) bounds this further loss by \(O((\log\ell)M_x/\ell)\). Discard isolated vertices as well.

Fix a nonempty level graph \(F=F_b\) after these operations. All neighborhoods in the next two subsections are in \(F\). Set \[ \begin{aligned} S_u&=q(N(u))\in[\ell^{-1},e^\ell],\\ c_{uv}&=q(N(u)\cap N(v))\ge\ell^{-1} &&(uv\in E(F)),\\ h_u&=\sum_{v\in N(u)}q_vc_{uv}\ge S_u/\ell. \end{aligned} \tag{23}\] The lower bound on \(S_u\) follows because \(u\) has a neighbor and every edge has common-neighborhood weight at least \(\ell^{-1}\).

We prove the lemma in the next two subsections. At a vertex \(u\), the construction will attach a label in \(N(u)\) to each incidence \((u,v)\); edges with the same label use the same copy of \(u\). A triangle survives only if its two labels agree at each corner. We first construct probability laws whose labels can usually agree, then impose a condition on the reverse transition probabilities to bound the weight at each copy.

Entropy bounds for walks in neighborhoods

Let \(t\) be the unordered triangle mass of \(F\). It is positive by (23). Choose an ordered triangle \((u,v,z)\) with probability \(q_uq_vq_z/(6t)\). The law of its first two vertices and the conditional law of its second vertex are \[ \mu(u,v)=\frac{q_uq_vc_{uv}}{6t},\qquad \pi_u(v)=\frac{q_vc_{uv}}{h_u}. \tag{25}\] In particular, the marginal law of \(u\) is \(q_uh_u/(6t)\), and \(\mu\) is symmetric in its two arguments.

On \(N(u)\) define the transition kernels \[ P_u(v,z)=\frac{\mathbf 1_{\{vz\in E(F)\}}q_z}{c_{uv}},\qquad Q_u=\frac{I+P_u}{2},\qquad K_u^{(j)}=P_uQ_u^j\quad(j\ge0). \tag{26}\] All denominators are positive. The kernel \(P_u\) is reversible with stationary law \(\pi_u\), since \[\pi_u(v)P_u(v,z)=\frac{q_vq_z\mathbf 1_{\{vz\in E(F)\}}}{h_u}\] is symmetric in \(v,z\). The same holds for \(Q_u\) and \(K_u^{(j)}\), which are polynomials in \(P_u\). Moreover, writing \(K_u^{(j)}=Q_u^jP_u\) and using \(c_{uv}\ge\ell^{-1}\) gives \[ K_u^{(j)}(v,z)\le\ell q_z. \tag{27}\]

The number of vertices in \(N(u)\) can be arbitrarily large even when its total weight is small. We therefore measure entropy relative to \(q\): for a probability row \(p\) on a finite set with positive weights \(q\), put \[\mathcal H_q(p)=\sum_{z:p(z)>0}p(z)\log\frac{q_z}{p(z)}.\] This quantity may be negative. Jensen’s inequality bounds it by \(\log q(\operatorname{supp}p)\). Define \[ H_j=\mathbb E_{(u,v)\sim\mu} \mathcal H_q\bigl(K_u^{(j)}(v,\cdot)\bigr), \qquad R=\lceil\ell\rceil. \tag{28}\] The density bound gives \(H_j\ge-\log\ell\). We will bound \(H_R\) by \(O_r(\log\ell)\), much less than the immediate bound \(H_R\le\ell\). Only \(O_r(\log\ell)\) entropy can then be gained over \(R\) steps, so some step has a small increment. That increment will control the distance between the label laws at a triangle corner.

Coupled labels and the split graph

Iteration and completion of the adjustment lemma

The random update and its expectation

Assume the hypotheses of Proposition 10; the case \(V(G')=\varnothing\) is immediate. Fix the operations and rates \(a_j\) given by Lemma 3 on \(H\), with listed supports \(J_j\). We use two families of mutually independent Bernoulli flags. For each entry \(z\in V(H)\) an activation flag is set with probability \(\tau w_z\); it touches every neighbor of \(z\) in \(H\), with designated multiplier zero there. For each operation \(j\) its flag is set with probability \(\tau a_j\) and touches \(J_j\). A multiplier operation has its prescribed multipliers \(m_i^{(j)}\) on \(J_j\), and a drop has designated multiplier zero on its singleton support. The probabilities are valid for large \(\Delta\): the nonempty support and rate bound of Lemma 3 give \(a_j\le\Lambda^4\).

For each \(i\in V(H)\) put \(\bar w_i=w_iY_i\). If exactly one set flag touches \(i\), let \(Y_i\) be its designated multiplier; if at least two set flags touch \(i\), let \(Y_i=0\). If no set flag touches \(i\), put \[ Y_i=1+\tau\left(s_i+\sum_{j\in\mathcal M}a_j(1-m_i^{(j)})\right), \tag{50}\] where \(\mathcal M\) indexes the multiplier operations and their multipliers are extended by \(1\) off the listed supports. Zero-weight entries stay at zero. The coefficient of \(\tau\) in (50) has absolute value at most \(\Lambda+\Lambda^4(1+U)\). The no-flag multiplier is therefore positive and is \(1+O(\tau\Delta^{o(1)})\).

An entry activates when its activation flag is set. An activating entry is successful if none of its neighbors in \(H\) activates. At every host with a successful entry, choose one such entry as its color, using any fixed order on that list to break ties. Successful entries cannot be adjacent in \(H\), and they were available before the round, so this extends the proper partial coloring. Every entry conflicting with a newly chosen color is touched by its activation flag and hence has provisional weight zero, whether or not other flags also touch it. Consequently, after newly colored vertices are removed, all remaining positive provisional weights are available. The set of hosts receiving a color depends only on activation flags, independently of the choices among successful entries.

Until that removal, a bar on any quantity in (46) means that it is calculated with the provisional weights on the entire start-of-round graph \(G'\). We may continue to use \(E(H)\) in these sums because zero weights remain zero. The compensation in (50) cancels the first-order mean loss from activations and multiplier operations. The following estimate shows how the adjustment lemma controls the remaining cost in the potential.

Concentration with bounded input participation

We next make the expectation bounds simultaneous at all vertices. The relevant concentration principle is a bounded-variable form of the generalized Hölder inequality of Finner [16] and the read-\(k\) concentration method of Gavinsky, Lovett, Saks, and Srinivasan [17]. We give the short proof, including the exponential-moment estimate of Hoeffding [18].

Apply Lemma 12 first to \(\bar W_v\) and to the non-edge part \(\bar F_v-\bar D_v\). Apart from an additive constant, each is a sum of at most \(k\le\Delta\) functions, one for each entry of \(L(v)\), of range length at most \(\Delta^{-0.99+o(1)}\). This follows from (45), (50), and \(U=\Delta^{o(1)}\); the logarithmic factors in the entropy term are absorbed in \(\Delta^{o(1)}\). This also covers arbitrarily small positive provisional weights: with \(0\log0=0\), \(\sup_{0\le z\le b}|z\log z|=b\log(1/b)\) for \(0<b<e^{-1}\). A multiplier flag occurs in at most \(P_0\) of these functions, by its support bound in a single part. A drop flag occurs in at most one, and an activation flag occurs in at most one because its activating entry has at most one neighbor in \(L(v)\). Thus \(p=P_0\) is valid. In particular, each requirement \[ \bar W_v\le\mathbb E\bar W_v+\zeta,\qquad \bar F_v-\bar D_v\le\mathbb E(\bar F_v-\bar D_v)+\zeta \tag{59}\] fails with probability at most \(\exp(-\Delta^{0.5})\) for large \(\Delta\): the exponent in (56) is at least \(\Delta^{0.68-o(1)}\).

For an edge \(vu\in E(G')\), the matching sum \(\bar D_{vu}\) has at most \(k\) terms, each of range length at most \(\Delta^{-1.98+o(1)}\). Every entry at either endpoint occurs in at most one term, so each flag occurs in at most \(2P_0\) terms. Applying Lemma 12 with \(p=2P_0\) shows that \[ |\bar D_{vu}-\mathbb E\bar D_{vu}|\le\Delta^{-1.25} \tag{60}\] fails with probability at most \(2\exp(-\Delta^{0.4})\). Here the exponent is at least \(\Delta^{0.46-o(1)}\). This separation into non-edge terms and individual matching sums is what permits the participation bound to apply; no independence among entries of a list is assumed.

For ordinary list coloring, operations can instead be chosen separately in each graph induced by one common color label. Sampling their flags independently makes contributions of distinct colors independent, so the corresponding concentration bound has \(p=1\). Arbitrary edge matchings provide no such common labels; the per-part support bound replaces that independence here.

Activations that produce colors

The expectation estimate allows a potential increase of order \(\tau D_v\). To offset it, we must show that enough neighbors receive colors, with their contributions measured both by \(D_{vu}\) and by \(1/\Delta\). Fix \(v\in V(G')\), and take one of the coefficient families \[ b_u=D_{vu}\quad(u\in N_{G'}(v)),\qquad\text{or}\qquad b_u=1/\Delta\quad(u\in N_{G'}(v)). \tag{61}\] In either case \(0\le b_u\le2K\Delta^{-0.99}\): for the first family, the matching property gives \(D_{vu}\le\Delta^{-0.99}W_v\). Let \(A_u\) indicate that some entry at \(u\) activates. These indicators are independent over the hosts \(u\), and \[ \mathbb P(A_u=1)\ge1-e^{-\tau W_u}\ge\tau K/4 \tag{62}\] for large \(\Delta\), since \(K/2\le W_u\le2K\). Lemma 12 with \(p=1\) and \(\sum_ub_u^2\le4K^2\Delta^{-0.98}\) gives \[ \sum_{u\in N_{G'}(v)}b_uA_u \ge\frac{\tau K}{4}\sum_{u\in N_{G'}(v)}b_u-\zeta \tag{63}\] except with probability at most \(\exp(-\Delta^{0.5})\). The next lemma bounds the loss caused by conflicting activations.

Together, (63) and Lemma 13 imply that, for either choice in (61), we may require \[ \sum_{\substack{u\in N_{G'}(v)\\u\text{ receives a color}}}b_u \ge\frac{\tau K}{4}\sum_{u\in N_{G'}(v)}b_u-2\zeta. \tag{67}\] Let \(E_v\) be the event that (59), (60) for an edge incident with \(v\), or (67) for one of the two coefficient families fails. A union bound gives, for all sufficiently large \(\Delta\), \[ \mathbb P(E_v)\le\exp(-\Delta^{0.005}). \tag{68}\]

Simultaneous bounds and restoration of the weight conditions

We use the Lovász local lemma [14] to avoid every \(E_v\). Assign each multiplier flag to the host of a chosen center of a radius-\(R_0\) ball in \(H\) containing its listed support. Assign activation and drop flags to the hosts of the activating and dropped entries, respectively. Every input determining \(E_v\) is assigned within distance \(R_0+3\) of \(v\) in \(G'\). Indeed, the host projection does not increase distances; the provisional weights on an incident matching use flags touching entries at its two hosts; and whether a neighbor of \(v\) receives a color is determined by activation flags at distance at most two from \(v\). Events at distance greater than \(2(R_0+3)\) therefore involve disjoint sets of independent inputs. A bound for the maximum degree of a dependency graph is \[ d=(\Delta+1)^{2R_0+10} \le\exp\bigl(O(\log\Delta\log\log\Delta)\bigr). \tag{69}\]

For completeness, the symmetric local lemma says that finitely many events of probability at most \(q\), with a dependency graph of maximum degree at most \(d\ge1\), can all be avoided if \(q\le1/(e(d+1))\). Put \(x=1/(d+1)\), so \(q\le x(1-x)^d\). Induction on the number of conditioned events shows that any event, conditioned on the avoidance of any set of the others, has probability at most \(x\). To make the induction step, split the conditioning set into nonneighbors and at most \(d\) neighbors of the event. Independence bounds the numerator after conditioning on the nonneighbors by \(q\), and the induction hypothesis bounds the probability of avoiding the neighbors, under that conditioning, below by \((1-x)^d\). The same induction ensures that all conditioning probabilities are positive. Multiplying these positive conditional avoidance probabilities proves joint avoidance. By (68) and (69), its hypothesis holds here for large \(\Delta\).