For an integer k≥2 and r2>2(2k−1)ln(2k−1), we construct a bipartite graph G whose two vertex classes are disjoint copies of the family of all k-subsets of a (2k−1)-element set, two vertices being adjacent when their sets intersect in at most r elements. Assigning each vertex its corresponding subset as its color list, G is not colorable, and thus its choice number ch(G)≥k+1. This implies that there are graphs with maximum degree Δ and ch(G)≥(321−o(1))(lnlnΔ)3(lnΔ)2. When k→∞, consequently ch(G)/lnΔ tends to infinity, which disproves the Alon–Krivelevich conjecture. In order to show the uncolorability, we use tools from probability (conditional product measure, nested coupling, and Doob martingale), which we write in an elementary language of weighted counting, and topology (Brouwer fixed-point theorem).
Introduction
List coloring and the Alon–Krivelevich conjecture
All graphs in this paper are finite and simple. A list assignmentL on a graph G=(V,E) assigns a finite set L(v) of available colors to every vertex v∈V. A proper L-coloring is a function φ satisfying φ(v)∈L(v) with v∈V and φ(u)=φ(v) with uv∈E. The graph is q-choosable if every assignment of lists of size at least q has a proper list coloring. Its choosability, also called its list chromatic number, is ch(G)=min{q∈Z≥1:G is q-choosable}.
Although the ordinary chromatic number of a bipartite graph is at most two, its choosability can be arbitrarily large. Alon and Krivelevich [2 Conjecture 5.1] made the following conjecture.
Conjecture 1.1 (Alon and Krivelevich [2]). There exists an absolute constant C>0 such that
ch(G)≤ClnΔ(G)(1)
for every finite simple bipartite graph G with maximum degree Δ(G)≥2.
Bradshaw, Mohar, and Stacho [3 Theorem 1.2] proved that every bipartite graph of sufficiently large maximum degree satisfies ch(G)<0.797Δ(G)/lnΔ(G). The authors and Ninh [5] extended the Bradshaw–Mohar–Stacho framework to list coloring of near-bipartite graphs and obtained the bound 0.77Δ(G)/lnΔ(G). The results below give an explicit family for which (1) fails.
Notation
For a positive integer N, write [N]={1,…,N}, and put [0]=∅. For a finite set Ω and an integer j, let (jΩ)={U⊆Ω:∣U∣=j}, which we call the j-th layer of Ω, it is empty if j<0 or j>∣Ω∣. The notation (jN) denotes the usual numerical binomial coefficient. Throughout, ln is the natural logarithm and e is its base.
The construction and the results
Definition 1.2. Let k≥2 and r≥0 be integers, and put P=[2k−1]. The graph G(k,r) has the disjoint vertex classes A={aS:S∈(kP)} and B={bT:T∈(kP)} and the edge of G(k,r) is defined as follows:
aSbT∈E(G(k,r))⟺∣S∩T∣≤r.(2)
Its standard lists are
L(aS)=SandL(bT)=T.(3)
Two k-subsets of a (2k−1)-element set always intersect, and a typical pair intersects in about k/2 elements. By (2), aS is adjacent only to the vertices bT whose set T is nearly the complement of S. When r is much smaller than k such pairs are rare, which keeps the degree small, while the lists have size k.
Theorem 1.3 (Uncolorability criterion). Let k≥2 and r≥0 be integers, and put n=2k−1. If
r2>2nlnn,(4)
then G(k,r) has no proper coloring from its standard lists.
Corollary 1.4. For an integer k≥2, let n=2k−1, r=⌈2nlnn⌉+1, G=G(k,r) and Δ=Δ(G).
(a) The standard lists of G admit no proper coloring, hence ch(G)≥k+1.
(b) As k→∞,
ch(G)≥(321−o(1))(lnlnΔ)3(lnΔ)2.(5)
In particular ch(G)/lnΔ→∞, so no absolute constant C makes (1) valid for all finite simple bipartite graphs.
(c) The order in (5) is the limit of Theorem 1.3 for these graphs: if r′ is any integer with r′2>2nlnn and Δ′=Δ(G(k,r′)), then k≤(1+o(1))(lnΔ′)2/(lnlnΔ′)3 as k→∞, uniformly in the choice of r′.
Part (a) is Theorem 1.3 applied to this r, since r>2nlnn. For fixed k, the bound ch≥k+1 does not depend on r, while the edge sets of G(k,r), and hence Δ(G(k,r)), are nondecreasing in r; so this r, the least integer satisfying (4), is the best choice for this method. Part (c) concerns only the lower bound produced by Theorem 1.3; it says nothing about the true choosability of G(k,r), which could be larger, nor about the true least r for which G(k,r) is uncolorable from its standard lists.
Organization and an outline of the proof
Section 2 establishes the properties of G(k,r) other than uncolorability: it is a finite simple bipartite regular graph, and its degree is computed exactly and bounded. It then derives Corollary 1.4 from Theorem 1.3.
Sections 3–7 prove Theorem 1.3 by contradiction. We assume that a proper coloring φ exists and follow its consequences.
Step 1. (§ 3) The coloring defines two selection rules. They partition the k-sets and the (k−1)-sets into color classes Fi and Gi. Properness says that, for every color i, every set of Fi is far from every set of Gi, and hence far from every k-set containing a member of Gi. Here “far” means differing in at least r elements.
Step 2. (§ 4) To turn “far apart” into a contradiction, we must know that some color has large classes on both sides. We measure families of sets by weighted proportions: a vector x∈[0,1]n gives the set U the weight ∏i∈Uxi∏i∈/U(1−xi). Plain proportions, the case x=(21,…,21), are not enough, because a coloring can make the shared colors rare.
Step 3. (§ 5) We choose the weights from the coloring: a fixed-point argument yields x∗ such that every color has the same weighted share among k-sets as among (k−1)-sets. Some color c then has share at least 1/n on both sides.
Step 4. (§ 6) The (k−1)-sets of color c are lifted to the k-sets containing them, without losing weighted share.
Step 5. (§ 7) Two families of k-sets with weighted share at least 1/n always contain two sets that differ in at most 2nlnn elements.
Proof ofTheorem 1.3. Under the standing assumption of § 3, let x∗ and c be as in Lemma 5.1, and consider the two families F=Fc and H=Hc=∇Gc in the k-th layer of P. We collect what has been proved about them.
(iii) dJ(S,U)≥r for all S∈F and U∈H, by Lemma 3.2.
Lemma 7.1 with N=n, j=k, x=x∗, and ρ=1/n now gives r≤2nlnn. Squaring is valid because both sides are nonnegative, and the result contradicts (4). Hence no proper coloring exists. □
The coloring φ enters the argument only through the color classes in Step 1 and the choice of x∗ in Step 3. Everything proved in § 4, § 6 and § 7 is a general fact about weights on the subsets of a finite set. The only external ingredient is Brouwer’s fixed-point theorem, used in Step 3.
The construction and its properties
The graph G(k,r) is bipartite with 2(k2k−1) vertices; since aS and bT are distinct vertices even when S=T, it has no loops and no multiple edges. All standard lists have size k.
Fix S∈(kP). As ∣P∖S∣=k−1, every k-set T meets S, and a k-set T with ∣S∩T∣=t is determined by the independent choices of S∩T⊆S and T∖S⊆P∖S. The same count applies to the vertices bT, so G(k,r) is regular of degree
The edge sets grow with r, so Δ(G(k,r)) is nondecreasing in r. Let 1≤r≤k/2. For 1≤t≤r we have (t−1k−1)=kt(tk)≤(tk)≤(rk), the last inequality because (sk)(s+1k)=s+1k−s≥1 whenever 2s+1≤k. Stirling’s formula gives r!≥(r/e)r, hence (rk)≤kr/r!≤(ek/r)r; and (rk)=∏i=0r−1r−ik−i≥(k/r)r.
Proof of Corollary 1.4 from Theorem 1.3. All o(1) terms refer to k→∞. Write L=lnΔ and L′=lnΔ′. Since 2nlnn=(4+o(1))klnk and 2nlnn<r≤2nlnn+1, we have r=(2+o(1))klnk; hence, for large k, 1≤r≤k/2, and ln(k/r), ln(ek/r) both equal (21+o(1))lnk. By (7),
Hence lnL=(21+o(1))lnk. Part (a) gives ch(G)≥k+1, and the upper bound on L gives k≥L2/((4+o(1))(lnk)3)=(321−o(1))L2/(lnL)3. This proves (b), and ch(G)/L→∞ because L→∞.
For (c), the integer r′ exceeds 2nlnn, so r′≥r. By monotonicity in r and (7), L′≥rln(k/r)=(1+o(1))k(lnk)3/2, where the o(1) depends only on k. Also Δ′≤(k2k−1)≤4k, so lnL′≤lnk+1. Therefore k≤(1+o(1))(L′)2/(lnk)3≤(1+o(1))(L′)2/(lnL′)3. □
It remains to prove Theorem 1.3, this occupies Sections 3–7.
From a proper coloring to far-apart color classes
The standing assumption
Throughout Sections 3–7, fix integers k≥2 and r≥0 satisfying (4), let n=2k−1 and P=[n], and suppose for contradiction that φ is a proper coloring of G(k,r) from its standard lists. Sections 4, 6 and 7 also contain general lemmas that do not use φ, these are stated for an arbitrary finite ground set.
The second definition is legitimate since ∣P∖R∣=(2k−1)−(k−1)=k, so bP∖R is a vertex of B. The list restrictions give f(S)∈S, g(R)∈P∖R that is g(R)∈/R. Thus f selects an element inside each k-set, and g selects an element outside each (k−1)-set.
Color classes
Let Fi={S∈(kP):f(S)=i} and Gi={R∈(k−1P):g(R)=i} for each color i∈P. The families F1,…,Fn partition the k-th layer of P, and G1,…,Gn partition the (k−1)-th layer. Since f(S)=i for S∈Fi and g(R)=i for R∈Gi, the list restrictions give
i∈Sfor every S∈Fiandi∈/Rfor every R∈Gi.(9)
Properness as a distance condition
For U,W∈(jΩ), where Ω is a finite set, define the Johnson distance
dJ(U,W)=∣U∖W∣=∣W∖U∣=21∣U△W∣,(10)
the number of elements that must be exchanged to turn U into W. The first two quantities agree because ∣U∣=∣W∣. Nonnegativity and symmetry are immediate, and dJ(U,W)=0 holds exactly when U=W. For the triangle inequality, the inclusion U∖W⊆(U∖V)∪(V∖W) gives dJ(U,W)≤dJ(U,V)+dJ(V,W). Thus dJ is a metric on each layer, and dJ(U,W)≤j.
Lemma 3.1 (Same color forces distance). If S∈Fi and R∈Gi for the same color i, then ∣S∖R∣≥r+1.
Proof. The vertices aS and bP∖R both receive color i. Since φ is proper, they are not adjacent, so (2) gives ∣S∩(P∖R)∣>r. Both sides are integers, and S∩(P∖R)=S∖R. □
The two classes of a color live on different layers. To compare them on one layer, we enlarge the (k−1)-sets. For G⊆(j−1Ω), let ∇G={U∈(jΩ):U⊇R for some R∈G} be the upper shadow of G, and let Hi=∇Gi⊆(kP) with i∈P.
Lemma 3.2 (Far-apart classes). For every color i, every S∈Fi, and every U∈Hi, we have dJ(S,U)≥r.
Proof. Choose R∈Gi with R⊆U. By Lemma 3.1, ∣S∖R∣≥r+1. Also ∣U∖R∣=1. Because R⊆U, every element of S∖R either lies outside U or belongs to U∖R, and these two possibilities are disjoint: S\setminus R=(S\setminus U)\mathbin{\mathaccent\cdot\cup}(S\cap(U\setminus R)). Taking cardinalities and using ∣S∩(U∖R)∣≤1, dJ(S,U)=∣S∖U∣=∣S∖R∣−∣S∩(U∖R)∣≥(r+1)−1=r. □
What remains to be shown
Lemma 3.2 is the only consequence of properness used below. To contradict it, it suffices to find one color c for which Fc and Hc are both “large”; § 7 shows that two large families of k-sets contain two sets at Johnson distance at most 2nlnn<r.
Remark 3.3 (A common color always exists). Some color is used by both rules, by a counting argument. Let Cf and Cg be the sets of colors used by f and by g. Every k-set S contains f(S)∈Cf, so Cf meets every k-set; hence ∣P∖Cf∣≤k−1, that is, ∣Cf∣≥k. If ∣Cg∣≤k−1, choose a (k−1)-set R⊇Cg; then g(R)∈Cg⊆R, which is impossible. Hence ∣Cg∣≥k. Since ∣Cf∣+∣Cg∣≥2k>∣P∣, the two sets share a color. This argument gives no information about the sizes of the corresponding classes, which is what the rest of the proof provides.
Measuring families of sets by weights
This section is independent of φ. Throughout it, Ω is a finite set and x=(xi)i∈Ω∈[0,1]Ω.
Product weights
Definition 4.1 (Product weights). The x-weight of a set U⊆Ω is
πx(U)=i∈U∏xii∈Ω∖U∏(1−xi).
an empty product being 1. For a family F of subsets of Ω, put πx(F)=∑U∈Fπx(U).
The parameter xi is a degree of preference for element i: the closer xi is to 1, the heavier the sets containing i are, relative to the sets avoiding it. If xi=1, every set avoiding i has weight zero, so i is forced; if xi=0, every set containing i has weight zero, so i is forbidden. If every xi equals 1/2, every set has weight 2−∣Ω∣.
Lemma 4.2 (Basic properties of the weights). Let J0={i∈Ω:xi=0}, J1={i∈Ω:xi=1}, and Q=Ω∖(J0∪J1).
(a) πx(U)≥0 for every U⊆Ω, and ∑U⊆Ωπx(U)=1.
(b) For every i∈Ω, the sets containing i have total weight xi, and the sets avoiding i have total weight 1−xi.
(c) πx(U)>0 if and only if J1⊆U⊆J1∪Q. Consequently, πx((jΩ))>0 if and only if ∣J1∣≤j≤∣J1∣+∣Q∣.
(d) If Ω=Ω1⊔Ω2 and x(1),x(2) denote the restrictions of x to Ω1,Ω2, then πx(U)=πx(1)(U∩Ω1)πx(2)(U∩Ω2) for every U⊆Ω.
(e) πx(U) is a polynomial in the coordinates of x. In particular, it depends continuously on x.
Proof. (a) Every factor in πx(U) lies in [0,1]. Expand the product ∏i∈Ω(xi+(1−xi))=1 by the distributive law, choosing one of the two summands from each factor. Each choice corresponds to exactly one set U, namely the set of indices at which xi was chosen, and the resulting term is πx(U). Hence the weights sum to 1.
(b) Expand xi∏ℓ=i(xℓ+(1−xℓ))=xi in the same way. The terms are exactly the weights πx(U) of the sets U containing i. The statement about sets avoiding i follows by subtracting from (a).
(c) A product of numbers in [0,1] is positive exactly when every factor is positive. For i∈U the factor xi is positive exactly when i∈/J0; for i∈/U the factor 1−xi is positive exactly when i∈/J1. This proves the first assertion. A set of size j with positive weight is obtained by adding j−∣J1∣ elements of Q to J1, which is possible exactly when 0≤j−∣J1∣≤∣Q∣.
(d) Regroup the factors of πx(U) according to whether their index lies in Ω1 or in Ω2.
(e) This is immediate from the definition. □
Shares and averages on a layer
Definition 4.3 (Shares and averages). Let j be an integer with πx((jΩ))>0. For U∈(jΩ) and F⊆(jΩ), define
We call νx,j(F) the share of F in the j-th layer. For a function h:(jΩ)→R, the weighted average of h is
⟨h⟩x,j=U∈(jΩ)∑νx,j(U)h(U).
Shares are nonnegative, additive over disjoint families, and the whole layer has share 1. If every xi equals 1/2, all sets of one layer have the same weight, so νx,j(F)=∣F∣/(j∣Ω∣) is the plain proportion and ⟨h⟩x,j is the plain average.
In the proof of Theorem 1.3, “Fc and Hc are large” will mean that both have share at least 1/n in the k-th layer of P, for one suitable vector x.
The probabilistic reading
The weights have a probabilistic meaning, which explains the terminology of the literature but is not needed for the proofs. Let Zx be the random subset of Ω obtained by including each i independently with probability xi.
In this language, the coloring is used as follows: the color classes Fi,Gi are fixed families determined by φ, and the random set Zx is drawn from a product distribution whose parameters x=x∗ are themselves determined by φ (§ 5). Nothing about φ is random.
Why the weights must depend on the coloring
The uniform weights x=(21,…,21) cannot be used in general. The following example concerns arbitrary rules with f(S)∈S and g(R)∈/R, not necessarily arising from a proper coloring.
Remark 4.4. Fix X∈(kP), put R0=P∖X, fix z∈X, and put S0=R0∪{z}, so that ∣R0∣=k−1, ∣S0∣=k, and X∩S0={z}.
Every k-set S meets X, because ∣P∖X∣=k−1. Let f(S) be an element of S∩X different from z whenever such an element exists. This fails only if S∩X={z}, that is, only if S=S0; put f(S0)=z.
Every (k−1)-set R misses an element of S0, since ∣S0∣=k. Let g(R) be an element of S0∖R different from z whenever such an element exists. This fails only if S0∖R={z}, that is, only if R=R0, let g(R0)=z.
The rule f uses colors in X and g uses colors in S0, so z is the only color used by both, and it is used only on S0 and on R0. With uniform weights, both classes of z have share 1/(k2k−1), which is exponentially small. The separation estimate of § 7 applied with this share yields only r≤2nln(k2k−1). The two middle coefficients (k−12k−1)=(k2k−1) are the largest of the 2k coefficients (t2k−1), which sum to 22k−1; hence (k2k−1)≥22k−1/(2k), and the bound is at least 2n(nln2−ln(n+1)). This exceeds n≥k once (2ln2−1)n>2ln(n+1), which holds for all large k. Since no two k-sets are at Johnson distance more than k, the bound then carries no information.
By contrast, the weights with xi=1 on R0, xi=0 on X∖{z}, and xz=21 give positive weight only to S0 in the k-th layer and only to R0 in the (k−1)-th layer, so color z has share 1 on both sides. § 5 finds such adapted weights for every coloring.
Choosing the weights from the coloring
We return to the standing assumption. This section is where the coloring determines the weights.
Statement
Lemma 5.1 (Balanced weights). There existx∗∈[0,1]nand a colorc∈Psuch that bothπx∗((kP))andπx∗((k−1P))are positive and
νx∗,k(Fc)=νx∗,k−1(Gc)≥n1.(11)
The proof uses only that F1,…,Fn and G1,…,Gn partition the two layers and satisfy (9). It occupies the rest of this section.
The set of admissible weights
Define
D={x∈[0,1]n:i=1∑nxi=k−21}.(12)
Since n/2=k−1/2, the vector (1/2,…,1/2) belongs to D, so D is nonempty. It is the intersection of a closed cube with a closed affine hyperplane. Consequently, it is closed and bounded in Rn, and hence compact. The cube and the hyperplane are both convex, so their intersection D is convex as well.
For x∈D, define a(x)=πx(kP) and b(x)=πx(k−1P) for the total weights of the two layers. We show that both are positive for every x∈D, including points with coordinates equal to 0 or 1. Let u be the number of coordinates with xi=1, and let v be the number of coordinates with xi>0. Since
u≤i=1∑nxi=k−21≤v
and u,v are integers, we have u≤k−1 and v≥k. By Lemma 4.2(c), the j-th layer has positive weight exactly when u≤j≤v. In particular,
a(x)>0 and b(x)>0(x∈D).(13)
The shares νx,k and νx,k−1 are therefore defined throughout D. This is the reason for the constraint ∑ixi=k−21: it places the “typical size” of a set halfway between the two layers that matter.
A continuous self-map built from the coloring
Let Ai(x)=πx(Fi) and Bi(x)=πx(Gi) for each i∈P and x∈D. These are the unnormalized weights of the color classes of i; this is the point at which the coloring enters. They are finite sums of polynomials in x, so every Ai and Bi is continuous on D by Lemma 4.2(e). Since the classes partition the two layers,
Each coordinate is continuous, and therefore T is continuous. We verify that T(x)∈D whenever x∈D. Using (15) and 0≤a(x),b(x)≤1,
Ti(x)≥xi−b(x)Ai(x)≥xi−Ai(x)≥0,
Ti(x)≤xi+a(x)Bi(x)≤xi+Bi(x)≤1.
Thus T(x)∈[0,1]n. Summing (16) over i and using (14),
i=1∑nTi(x)=i=1∑nxi+a(x)b(x)−b(x)a(x)=k−21.
This proves T(D)⊆D.
The map has the following heuristic meaning, which is not used in the proof. Dividing the correction term by a(x)b(x), it equals the share of color i under g minus its share under f. If g uses color i more heavily than f does, then T raises xi. This makes the sets containing i heavier, which tends to increase the share of Fi and to decrease the share of Gi.
The fixed point
We use Brouwer’s fixed-point theorem [1]: every continuous map from a closed simplex in Rn to itself has a fixed point. Here a closed simplex is the convex hull of finitely many affinely independent points. In dimension one the theorem is the intermediate value theorem: if F:[0,1]→[0,1] is continuous, then F(x)−x is ≥0 at 0 and ≤0 at 1, so it vanishes somewhere.
The theorem does not apply to T:D→D directly, because D is not a simplex: it is a polytope of dimension n−1 lying in a hyperplane of Rn. We therefore enlarge D to a simplex Σ, and pull Σ back onto D by a continuous map that fixes every point of D.
The simplex. Let
Σ={z∈Rn:zi≥0(1≤i≤n),i=1∑nzi≤n}
This is the convex hull of the n+1 affinely independent points 0,ne1,…,nen, where e1,…,en are the unit vectors. Indeed, a point z with z≥0 and ∑izi≤n equals ∑inzi(nei)+(1−∑inzi)⋅0, a convex combination of these points; conversely, every convex combination of them is nonnegative with coordinate sum at most n. Every x∈D satisfies 0≤xi≤1, hence x≥0 and ∑ixi≤n. Thus D⊆Σ.
The nearest-point map. We write ⟨⋅,⋅⟩ and ∥⋅∥ for the Euclidean inner product and norm on Rn.
Lemma 5.2 (Nearest points of D). For every z∈Rn there is exactly one point pD(z)∈D with ∥z−pD(z)∥=miny∈D∥z−y∥. Moreover:
(a) ⟨z−pD(z),y−pD(z)⟩≤0 for every y∈D;
(b) ∥pD(z)−pD(z′)∥≤∥z−z′∥ for all z,z′∈Rn; in particular, pD is continuous;
(c) pD(z)=z for every z∈D.
Proof. By Subsection 5.2, D is nonempty, compact, and convex.
Existence. The function y↦∥z−y∥ is continuous on the nonempty compact set D, so it attains its minimum at some point p.
Inequality (a) for every minimizer p. Let y∈D and 0<t≤1. By convexity, p+t(y−p)∈D, so by minimality ∥z−p−t(y−p)∥2≥∥z−p∥2. Expanding the left side gives −2t⟨z−p,y−p⟩+t2∥y−p∥2≥0. Dividing by t and letting t→0 yields ⟨z−p,y−p⟩≤0.
Uniqueness. Let p and p′ be minimizers. Applying (a) at p with y=p′ and at p′ with y=p gives ⟨z−p,p′−p⟩≤0 and ⟨z−p′,p−p′⟩≤0. Adding the two inequalities gives ∥p′−p∥2≤0, so p′=p. Hence pD(z) is well defined, and (a) holds for it.
(b). Let p=pD(z) and p′=pD(z′). By (a), ⟨z−p,p′−p⟩≤0 and ⟨z′−p′,p−p′⟩≤0. Adding these and rearranging, ∥p−p′∥2≤⟨z−z′,p−p′⟩≤∥z−z′∥∥p−p′∥, by the Cauchy–Schwarz inequality. If p=p′, dividing by ∥p−p′∥ gives (b); if p=p′, (b) holds trivially.
(c). If z∈D, then y=z gives distance 0, which is the least possible value, so pD(z)=z by uniqueness.
Applying Brouwer’s theorem. Define h:Σ→Rn by h(z)=T(pD(z)). By Lemma 5.2(b), pD is continuous, and T is continuous on D by Subsection 5.3; hence h is continuous. Moreover pD(z)∈D, T(D)⊆D by Subsection 5.3, and D⊆Σ; hence h(Σ)⊆D⊆Σ. Brouwer’s theorem therefore gives a point z∈Σ with T(pD(z))=z. The left side lies in D, hence z∈D. By Lemma 5.2(c), pD(z)=z, and substituting into T(pD(z))=z gives T(z)=z. Thus there exists x∗∈D with
T(x∗)=x∗.(17)
Proof of Lemma 5.1. Let x∗ be as in (17). Both layers have positive x∗-weight by (13). Substituting T(x∗)=x∗ into (16) yields a(x∗)Bi(x∗)=b(x∗)Ai(x∗) for each i∈P. Dividing by a(x∗)b(x∗)>0 gives
Thus, under the weights x∗, every color has the same share as an f-color among the k-sets as it has as a g-color among the (k−1)-sets. By (14), the numbers qi are nonnegative and sum to 1. If every qi were smaller than 1/n, their sum would be smaller than 1. Consequently, there is a color c∈P such that qc≥1/n. □
From now on, x∗ and c are fixed as in Lemma 5.1.
Lifting the second class to the upper layer
Lemma 5.1 makes Fc large among k-sets and Gc large among (k−1)-sets. Lemma 3.2 compares Fc with Hc=∇Gc. This section shows that Hc is at least as large as Gc:
νx∗,k(Hc)≥νx∗,k−1(Gc)≥n1.(19)
This is not automatic: a single k-set contains k different (k−1)-sets, and with nonuniform weights a naive count can lose weight. The tool is a way of shipping the weight of each (k−1)-set to its supersets.
Nested transports and the upward transfer
Definition 6.1 (Nested transport). Let Ω be a finite set, and j an integer. Let α and β be nonnegative functions of (j−1Ω) and (jΩ), each with a total of 1. A nested transport from α to β is an assignment of a number t(R,U)≥0 to every pair R∈(j−1Ω), U∈(jΩ) with R⊆U, such that
Here the sums run over U∈(jΩ) and R∈(j−1Ω), respectively.
In words, each set R of the lower layer ships its amount α(R) to its supersets, and each set U of the upper layer receives exactly β(U).
Example 6.2. Let ∣Ω∣=2k−1, let α and β be the uniform functions on the layers k−1 and k, and put M=(k2k−1)=(k−12k−1). Every (k−1)-set has exactly k supersets in the k-th layer, and every k-set has exactly k subsets in the (k−1)-th layer. Hence t(R,U)=1/(kM) for all R⊆U is a nested transport. In general the weights are not uniform, and the construction below is needed.
Lemma 6.3 (Upward transfer). If there is a nested transport from α to β, then β(∇G)≥α(G) for every G⊆(j−1Ω).
Every pair (R,U) in this double sum has U∈∇G. Adding the nonnegative terms t(R,U) with U∈∇G and R∈/G, and then applying the second identity in (20), we obtain
α(G)≤U∈∇G∑R⊆U∑t(R,U)=β(∇G).
Existence of nested transports, and the lift
Proposition 6.4 (Nested transport for product weights). Let Ω be a finite set, x∈[0,1]Ω, and j an integer. If πx((j−1Ω))>0 and πx((jΩ))>0, then there is a nested transport from νx,j−1 to νx,j. Consequently, νx,j(∇G)≥νx,j−1(G) with G⊆(j−1Ω).
Proof. Apply Proposition 6.4 with Ω=P, x=x∗, j=k and G=Gc, both layers have positive weight according to Lemma 5.1. Then use (11). □
The proof of Proposition 6.4 occupies the rest of this section. Related statements belong to the theory of strong Rayleigh measures; see Pemantle and Peres [6]. We give direct proofs of precisely the statements required here and do not claim novelty for them.
Positive weights
Let w1,…,wN>0. Let w(U)=∏i∈Uwi for U⊆[N], and for 0≤j≤N define the total layer and the normalized weight
We set Wj=0 for j<0 and j>N. Expanding the product by choosing either 1 or wiz from each factor gives
i=1∏N(1+wiz)=j=0∑NWjzj.(22)
Lemma 6.6. The coefficients in (22) form a log-concave sequence: for every integer j, Wj2≥Wj−1Wj+1.
Proof. We first establish a preservation property. Let (aj)j∈Z be a nonzero, finitely supported sequence of nonnegative numbers whose positive entries have consecutive indices. Suppose that aj2≥aj−1aj+1 with j∈Z. Given w>0, let bj=aj+waj−1. Expanding both products and collecting the coefficients of 1,w,w2, we obtain
The first and third terms are nonnegative by the assumed log-concavity. To treat the middle term, first suppose that aj−2aj+1=0. Then its nonnegativity follows from ajaj−1≥0. If instead aj−2aj+1>0, consecutiveness of the positive support implies that all four entries aj−2,aj−1,aj,aj+1 are positive. Dividing the log-concavity inequalities at indices j−1 and j by the relevant positive products gives
aj−2aj−1≥aj−1aj≥ajaj+1.
Comparing the first and last ratios and multiplying by aj−2aj>0 yields aj−1aj≥aj−2aj+1. Thus every term on the right-hand side of (23) is nonnegative, and (bj) is log-concave. Moreover, if the positive support of (aj) is {ℓ,…,u}, the positive support of (bj) is exactly {ℓ,…,u+1}: the two shifted supports overlap or are consecutive, and w>0. Hence the support condition is preserved as well.
Start with a0=1 and aj=0 for j=0. This sequence is log-concave and has consecutive positive support. Successively multiply its generating polynomial by 1+w1z,…,1+wNz. Multiplication by 1+wz replaces the coefficient sequence (aj) by (aj+waj−1), so the preceding argument applies at every step. By (22), the final coefficient sequence is (Wj), proving the lemma. □
Lemma 6.7 (Nested transport for positive weights). For positive weights w1,…,wN and every 1≤j≤N, there is a nested transport from ωj−1 to ωj.
Proof. We argue by induction on N. For N=1, necessarily j=1; the layers are {∅} and {{1}}, both normalized weights equal 1, and t(∅,{1})=1 is a nested transport.
Suppose now that N≥2 and that the assertion holds for N−1 elements. Write Wt′ and ωt′ for the quantities (21) computed from w1,…,wN−1; thus Wt′>0 for 0≤t≤N−1 and Wt′=0 otherwise. Splitting the sets of size t according to whether they contain N gives
Wt=Wt′+wNWt−1′.(24)
For 0≤t≤N, let
pt=WtwNWt−1′(25)
be the share of the t-th layer of [N] occupied by sets containing N. Then p0=0 and pN=1, and 1−pt=Wt′/Wt by (24). Directly from the definitions,
Indeed, the right-hand side of (26) is (Wt′/Wt)(w(V)/Wt′)=w(V)/Wt, and that of (27) is (wNWt−1′/Wt)(w(V)/Wt−1′)=w(V∪{N})/Wt; all denominators are positive in the stated ranges.
We next show pj−1≤pj for 1≤j≤N. For j=1 this reads 0≤p1, and for j=N it reads pN−1≤1. For 2≤j≤N−1, subtraction over a common denominator yields
pj−pj−1=WjWj−1wN((Wj−1′)2−Wj−2′Wj′)≥0,
because the denominator is positive and the numerator is nonnegative by Lemma 6.6 applied to w1,…,wN−1. Fix 1≤j≤N. Every pair R⊆U with ∣R∣=j−1 and ∣U∣=j is of exactly one of the following three kinds, and we define t(R,U) accordingly.
(K1) N∈/U. Such pairs exist only if j≤N−1; then the induction hypothesis gives a nested transport t′ from ωj−1′ to ωj′ on [N−1], and we put t(R,U)=(1−pj)t′(R,U).
(K2) N∈/R and N∈U. Then U=R∪{N}, since U∖R has one element. Put t(R,U)=(pj−pj−1)ωj−1′(R).
(K3) N∈R. Write R=R′∪{N} and U=U′∪{N}, so R′⊆U′⊆[N−1] and ∣R′∣=j−2. Such pairs exist only if j≥2; then 1≤j−1≤N−1, so the induction hypothesis gives a nested transport t′′ from ωj−2′ to ωj−1′ on [N−1], and we put t(R,U)=pj−1t′′(R′,U′).
All these numbers are nonnegative because 0≤pj−1≤pj≤1.
Amount shipped by R with $N \notin R. The supersets of R are the sets U⊆[N−1] of kind (K1), together with R∪{N} of kind (K2). If j≤N−1, the first group ships (1−pj)ωj−1′(R) in total; if j=N, there is no such U, and 1−pN=0, so the same formula holds. Adding the amount of kind (K2) gives (1−pj)ωj−1′(R)+(pj−pj−1)ωj−1′(R)=(1−pj−1)ωj−1′(R)=ωj−1(R) by (26) with t=j−1.
Amount shipped by R=R′∪{N}. This requires j≥2. All supersets are of kind (K3), and the total is pj−1ωj−2′(R′)=ωj−1(R) by (27) with t=j−1.
Amount received by U with N∈/U. This requires j≤N−1. All subsets are of kind (K1), and the total is (1−pj)ωj′(U)=ωj(U) by (26) with t=j.
Amount received by U=U′∪{N}. The subsets of U in the (j−1)-th layer are U′, of kind (K2), and the sets R′∪{N} with R′⊆U′, of kind (K3). The total is (pj−pj−1)ωj−1′(U′)+pj−1ωj−1′(U′)=pjωj−1′(U′)=ωj(U) by (27) with t=j. When j=1 there are no sets of kind (K3), and the formula remains correct because p0=0.
Thus t satisfies (20), completing the induction. □
Forced and forbidden elements
Lemma 6.8 (Reduction to positive weights). Let Ω be a finite set and x∈[0,1]Ω. Let J0,J1,Q be as in Lemma 4.2, put u=∣J1∣, and give each i∈Q the positive weight wi=xi/(1−xi). If πx((jΩ))>0, then for every U∈(jΩ),
Summing over all V∈(j−uQ) gives πx((jΩ))=γWj−u, and dividing proves the formula. □
Proof of Proposition 6.4. With the notation of Lemma 6.8, Lemma 4.2(c) applied to both layers gives u≤j−1 and j≤u+∣Q∣, that is, 1≤j−u≤∣Q∣. In particular Q=∅. Label the elements of Q by 1,…,∣Q∣ and apply Lemma 6.7 to obtain a nested transport tQ from ωj−1−u to ωj−u on Q. Let t(J1∪V,J1∪V′)=tQ(V,V′) when V⊆V′⊆Q, and t(R,U)=0 for all other pairs R⊆U. Each pair receiving a possibly positive value satisfies J1∪V⊆J1∪V′. By Lemma 6.8, a set R of the form J1∪V ships ∑V′tQ(V,V′)=ωj−1−u(V)=νx,j−1(R), and every other set of the lower layer ships 0=νx,j−1(R). The amounts received are checked in the same way. The final inequality is Lemma 6.3. □
Two large families on one layer are close
By Lemma 5.1 and Corollary 6.5, the families Fc and Hc both have share at least 1/n in the k-th layer under the weights x∗. This section shows that two such families cannot be far apart. Its results are general facts about weights and do not use φ.
Statement
Lemma 7.1 (Separation of two families). Let Ω=[N] with N≥1, let x∈[0,1]N, let πx((j[N]))>0, and write ν=νx,j. Suppose that F,H⊆(j[N]), ν(F),ν(H)≥ρ and 0<ρ≤1. If r≥0 satisfies dJ(S,U)≥r for every S∈F and U∈H, then
r≤2Nln(1/ρ).(28)
The idea is an isoperimetric one. Let h(U) be the distance from U to F. A single exchange changes h by at most 1, and such a function is nearly constant on most of the layer (Lemma 7.2). Since h vanishes on the large family F, its average is small; since h≥r on the large family H, its average is large. Comparing the two gives (28).
Slowly changing functions
Sets at Johnson distance one differ by a single exchange: one element is removed and another is inserted. Conversely, if dJ(U,W)=q, enumerate the differences as U∖W={u1,…,uq} and W∖U={w1,…,wq}. Starting at U, replace us by ws for s=1,…,q. Each intermediate set has size j, each step is one exchange, and the final set is W. A real-valued function h on a layer is 1-Lipschitz if ∣h(U)−h(W)∣≤dJ(U,W) when U,W∈(j[N]). It suffices to check this inequality when dJ(U,W)=1: summing the resulting bounds along the exchange sequence above proves the general case.
Lemma 7.2 (Concentration on a layer). Let Ω=[N] with N≥1, let x∈[0,1]N, and let j be an integer with πx((j[N]))>0. Write ν=νx,j. If h:(j[N])→R is 1-Lipschitz and hˉ=⟨h⟩x,j, then, for every t≥0,
ν{U:h(U)≥hˉ+t}≤e−2t2/N,(29)
ν{U:h(U)≤hˉ−t}≤e−2t2/N.(30)
Proof of Lemma 7.1 from Lemma 7.2
Proof of Lemma 7.1. Because ν(F)>0, the family F is nonempty. Define its distance function on the entire layer by h(U)=minS∈FdJ(U,S). The minimum exists because F is finite. To verify the Lipschitz property, fix U,W and choose SW∈F with h(W)=dJ(W,SW). The triangle inequality gives h(U)≤dJ(U,SW)≤dJ(U,W)+dJ(W,SW)=dJ(U,W)+h(W). Interchanging U,W yields ∣h(U)−h(W)∣≤dJ(U,W). Thus h is 1-Lipschitz. It is also nonnegative, and h(U)=0 if and only if U∈F.
Let η=⟨h⟩x,j≥0 and τ=2Nln(1/ρ). Since h≥0, the families {U:h(U)=0} and {U:h(U)≤η−η} coincide. Apply (30) with t=η to obtain ρ≤ν(F)=ν{U:h(U)=0}≤e−2η2/N. Taking natural logarithms gives lnρ≤−2η2/N, or equivalently η2≤2Nln(1/ρ)=τ2. As both η and τ are nonnegative, we conclude that η≤τ.
If r≤η, then r≤τ≤2τ, which already proves the required bound. If r>η, the separation hypothesis implies h(U)≥r for every U∈H: every distance in the minimum defining h(U) is at least r. Applying (29) with the positive threshold t=r−η yields ρ≤ν(H)≤ν{U:h(U)≥r}≤e−2(r−η)2/N. Taking logarithms and using r−η>0 gives r−η≤τ. Combining this with η≤τ proves r≤η+τ≤2τ=2Nln(1/ρ).
This also covers ρ=1. Indeed, then τ=0 and the first estimate forces η=0. If r>0, the second estimate would give 1≤e−2r2/N<1, a contradiction. Hence r=0 in this boundary case, as asserted by (28).
A two-point inequality
The only analytic input of the concentration lemma is the following one-variable inequality.
Lemma 7.3 (A two-point inequality). For everyp∈[0,1]and every reals, pe(1−p)s+(1−p)e−ps≤es2/8.
Proof. Put D(s)=1−p+pes. This is positive for every s: if p<1 then 1−p>0, and if p=1 then D(s)=es. The left-hand side equals e−psD(s), hence its logarithm is γ(s)=−ps+lnD(s). We have γ(0)=ln1=0 and γ′(s)=−p+D(s)pes with γ′(0)=0. Differentiating once more and writing a=pes≥0 and b=1−p≥0, so that a+b=D(s)>0,
γ′′(s)=D(s)2pesD(s)−(pes)2=(a+b)2ab≤41,
where the last step is (a+b)2−4ab=(a−b)2≥0. Let H(s)=s2/8−γ(s). Then H(0)=H′(0)=0 and H′′(s)=1/4−γ′′(s)≥0. By the mean value theorem, H′ is nondecreasing, so H′≥0 on [0,∞) and H′≤0 on (−∞,0]. Applying the mean value theorem again, H is nondecreasing on [0,∞) and nonincreasing on (−∞,0], so H(s)≥H(0)=0 for every s. Exponentiating γ(s)≤s2/8 proves the lemma. □
Proof of the concentration lemma
The idea is to decide, one element at a time, whether it belongs to the set. Each decision changes the relevant weighted average by at most 1, and N such changes rarely add up to much more than N.
Proof of Lemma 7.2. Let S={U∈(j[N]):πx(U)>0}, so that ν(S)=1. For 0≤i≤N and U∈S, let Ci(U)={U′∈S:U′∩[i]=U∩[i]} be the class of U at level i, consisting of the sets of positive weight that agree with U on the first i elements. Since U∈Ci(U), we have ν(Ci(U))>0, and we may define the prefix average
Mi(U)=ν(Ci(U))1U′∈Ci(U)∑ν(U′)h(U′).
The classes at level i partition S, and Mi is constant on each of them. At level 0 there is a single class S, so M0(U)=hˉ; at level N every class is a single set, so MN(U)=h(U).
Fix 1≤i≤N and a class C at level i−1. Its members share the trace Y=U∩[i−1]; put q=∣Y∣ and let m be the value of Mi−1 on C. The class splits into C1={U∈C:i∈U} and C0={U∈C:i∈/U}, each of which is empty or a class at level i. Let u1 and u0 be the values of Mi on C1 and C0, when these are nonempty. Since the sum defining Mi−1 on C splits along C=C1⊔C0,
ν(C)m=ν(C1)u1+ν(C0)u0,(31)
where a term is omitted if its class is empty.
Step 1: one decision moves the average by at most one. Suppose that C1 and C0 are both nonempty. We claim that ∣u1−u0∣≤1.
Let Qi={i+1,…,N} and let y be the restriction of x to Qi. Fix ε∈{0,1} and put Z={i} if ε=1 and Z=∅ if ε=0. Every set in the j-th layer that agrees with Y on [i−1] and satisfies the ε-condition at i has the form Y∪Z∪V with V∈(j−q−εQi), and every such V gives such a set. By Lemma 4.2(d) with Ω=[i]⊔Qi, πx(Y∪Z∪V)=κεπy(V) and κε=πx∣[i](Y∪Z), where κε does not depend on V. Because Cε is nonempty, some such set has positive weight, so κε>0 and πy((Qj−q−εi))>0. The members of Cε are exactly the sets Y∪Z∪V with πy(V)>0. Dividing the last display by its sum over V shows that
Both layers j−q−1 and j−q of Qi have positive y-weight, so Proposition 6.4 gives a nested transport t from νy,j−q−1 to νy,j−q on Qi. Expanding u1 with the first identity in (20) and u0 with the second,
u1−u0=V⊆W∑t(V,W)(h(Y∪{i}∪V)−h(Y∪W)).
For each pair V⊆W, the sets Y∪{i}∪V and Y∪W differ by one exchange: i∈/Y∪W, and W∖V has exactly one element, hence (Y∪{i}∪V)∖(Y∪W)={i} and (Y∪W)∖(Y∪{i}∪V)=W∖V. Hence each bracket has absolute value at most 1. The numbers t(V,W) are nonnegative and sum to ∑Vνy,j−q−1(V)=1, so ∣u1−u0∣≤1.
Step 2: exponential sums. For real λ and 0≤i≤N, define
Φi(λ)=U∈S∑ν(U)eλ(Mi(U)−hˉ).
Then Φ0(λ)=1. We claim that Φi(λ)≤eλ2/8Φi−1(λ) for 1≤i≤N.
Group the sum according to the classes at level i−1. A class C as above contributes ν(C)eλ(m−hˉ) to Φi−1(λ) and ν(C1)eλ(u1−hˉ)+ν(C0)eλ(u0−hˉ) to Φi(λ), with a term omitted if its class is empty. If one of C1,C0 is empty, the other equals C, its value of Mi equals m by (31), and the two contributions coincide. Otherwise put p=ν(C1)/ν(C)∈(0,1) and δ=u1−u0. By (31), m=pu1+(1−p)u0, hence u1−m=(1−p)δ and u0−m=−pδ. The contribution to Φi(λ) is therefore
by Lemma 7.3 with s=λδ and by ∣δ∣≤1 from Step 1. Summing over all classes proves the claim.
Step 3: the tail bounds. Iterating Step 2 from i=N down to i=1 gives
U∈S∑ν(U)eλ(h(U)−hˉ)=ΦN(λ)≤eNλ2/8(λ∈R).(32)
Fix t>0 and λ>0. Every term of the sum in (32) is nonnegative, and each set U∈S with h(U)≥hˉ+t contributes at least ν(U)eλt. Sets outside S have share zero. Hence
ν({U:h(U)≥hˉ+t})≤e−λtΦN(λ)≤exp(−λt+8Nλ2).
Choosing λ=4t/N makes the exponent −4t2/N+2t2/N=−2t2/N, which proves (29). The function −h is also 1-Lipschitz, its weighted average is −hˉ, and {h≤hˉ−t}={−h≥−hˉ+t}; applying (29) to −h proves (30). When t=0, both bounds state that a share is at most 1. □
The proof never required 0<xi<1: forced and forbidden elements only make some classes have a single branch, and in that case Step 2 contributes the factor 1≤eλ2/8.
AI usage declaration
We used the gpt-6-astra model through xean [4], a harness for AI-assisted mathematical research, to find the counterexample and its proof. Claude Opus 5.5 was used to rewrite the article. All mathematical content has been independently verified by the authors, who take full responsibility for all results.
References
[1]L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71 (1911), 97–115.
[2]N. Alon and M. Krivelevich. The choice number of random bipartite graphs. Annals of Combinatorics, 2(4) (1998), 291–297. https://doi.org/10.1007/BF01608526. Author manuscript: https://www.math.tau.ac.il/~nogaa/PDFS/choiceb4.pdf.
[3]P. Bradshaw, B. Mohar, and L. Stacho. Bipartite graphs are (4/5 − ε)Δ/log Δ-choosable. arXiv:2409.01513v1, 2024. https://arxiv.org/html/2409.01513v1.
[4]X. Chao. xean. https://github.com/chaoxu/xean.
[5]J. Yu, A. Ninh, and G. Yu. An extension of the Bradshaw–Mohar–Stacho framework to list-coloring of near-bipartite graphs. Submitted.
[6]R. Pemantle and Y. Peres. Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures. Combinatorics, Probability and Computing, 23(1) (2014), 140–160. https://doi.org/10.1017/S0963548313000345.