betaFeedback

WorksMathematics

A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs

Abstract

For an integer k≥2k\ge 2 and r2>2(2k−1)ln⁡(2k−1)r^2>2(2k-1)\ln (2k-1), we construct a bipartite graph GG whose two vertex classes are disjoint copies of the family of all kk-subsets of a (2k−1)(2k-1)-element set, two vertices being adjacent when their sets intersect in at most rr elements. Assigning each vertex its corresponding subset as its color list, GG is not colorable, and thus its choice number ch⁡(G)≥k+1\ch(G)\ge k+1. This implies that there are graphs with maximum degree ΔΔ and ch⁡(G)≥(132−o(1))(ln⁡Δ)2(ln⁡ln⁡Δ)3.\ch(G)\ge\Bigl(\frac1{32}-o(1)\Bigr)\frac{(\lnΔ)^2}{(\ln\lnΔ)^3}. When k→∞k\to\infty, consequently ch⁡(G)/ln⁡Δ\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 assignment LL on a graph G=(V,E)G=(V,E) assigns a finite set L(v)L(v) of available colors to every vertex v∈Vv \in V. A proper LL-coloring is a function φ\varphi satisfying φ(v)∈L(v)\varphi(v) \in L(v) with v∈Vv \in V and φ(u)≠φ(v)\varphi(u) \ne\varphi(v) with uv∈Euv \in E. The graph is qq-choosable if every assignment of lists of size at least qq has a proper list coloring. Its choosability, also called its list chromatic number, is ch⁡(G)=min⁡{q∈Z≥1:G is q-choosable}\operatorname{ch}(G)=\min\{q \in\mathbb{Z}_{\ge1}: G\text{ is }q\text{-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>0C>0 such that

ch⁡(G)≤Cln⁡Δ(G)(1)\operatorname{ch}(G) \le C\ln\Delta(G) \tag*{(1)}

for every finite simple bipartite graph GG with maximum degree Δ(G)≥2\Delta(G) \ge2.

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)\operatorname{ch}(G)<0.797\Delta(G)/\ln\Delta(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)0.77\Delta(G)/\ln\Delta(G). The results below give an explicit family for which (1) fails.

Notation

For a positive integer NN, write [N]={1,…,N}[N]=\{1,\ldots,N\}, and put [0]=∅[0]=\varnothing. For a finite set Ω\Omega and an integer jj, let (Ωj)={U⊆Ω:∣U∣=j}\binom{\Omega}{j}=\{U\subseteq\Omega:|U|=j\}, which we call the jj-th layer of Ω\Omega, it is empty if j<0j<0 or j>∣Ω∣j>|\Omega|. The notation (Nj)\binom{N}{j} denotes the usual numerical binomial coefficient. Throughout, ln⁡\ln is the natural logarithm and ee is its base.

The construction and the results

Definition 1.2. Let k≥2k\ge2 and r≥0r\ge0 be integers, and put P=[2k−1]P=[2k-1]. The graph G(k,r)G(k,r) has the disjoint vertex classes A={aS:S∈(Pk)}A=\{a_S:S\in\binom{P}{k}\} and B={bT:T∈(Pk)}B=\{b_T:T\in\binom{P}{k}\} and the edge of G(k,r)G(k,r) is defined as follows:

aSbT∈E(G(k,r))⟺∣S∩T∣≤r.(2)a_Sb_T\in E(G(k,r))\Longleftrightarrow|S\cap T|\le r. \tag*{(2)}

Its standard lists are

L(aS)=SandL(bT)=T.(3)L(a_S)=S\quad\text{and}\quad L(b_T)=T. \tag*{(3)}

Two kk-subsets of a (2k−1)(2k-1)-element set always intersect, and a typical pair intersects in about k/2k/2 elements. By (2), aSa_S is adjacent only to the vertices bTb_T whose set TT is nearly the complement of SS. When rr is much smaller than kk such pairs are rare, which keeps the degree small, while the lists have size kk.

Theorem 1.3 (Uncolorability criterion). Let k≥2k\ge2 and r≥0r\ge0 be integers, and put n=2k−1n=2k-1. If

r2>2nln⁡n,(4)r^2>2n\ln n, \tag*{(4)}

then G(k,r)G(k,r) has no proper coloring from its standard lists.

Corollary 1.4. For an integer k≥2k\ge2, let n=2k−1n=2k-1, r=⌈2nln⁡n⌉+1r=\lceil\sqrt{2n\ln n}\rceil+1, G=G(k,r)G=G(k,r) and Δ=Δ(G)\Delta=\Delta(G).

(a) The standard lists of GG admit no proper coloring, hence ch⁡(G)≥k+1\operatorname{ch}(G)\ge k+1.

(b) As k→∞k\to\infty,

ch⁡(G)≥(132−o(1))(ln⁡Δ)2(ln⁡ln⁡Δ)3.(5)\operatorname{ch}(G)\ge\left(\frac{1}{32}-o(1)\right)\frac{(\ln\Delta)^2}{(\ln\ln\Delta)^3}. \tag*{(5)}

In particular ch⁡(G)/ln⁡Δ→∞\operatorname{ch}(G)/\ln\Delta\to\infty, so no absolute constant CC 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′r' is any integer with r′2>2nln⁡n{r'}^2>2n\ln n and Δ′=Δ(G(k,r′))\Delta'=\Delta(G(k,r')), then k≤(1+o(1))(ln⁡Δ′)2/(ln⁡ln⁡Δ′)3k\le(1+o(1))(\ln\Delta')^2/(\ln\ln\Delta')^3 as k→∞k\to\infty, uniformly in the choice of r′r'.

Part (a) is Theorem 1.3 applied to this rr, since r>2nln⁡nr>\sqrt{2n\ln n}. For fixed kk, the bound ch⁡≥k+1\operatorname{ch}\ge k+1 does not depend on rr, while the edge sets of G(k,r)G(k,r), and hence Δ(G(k,r))\Delta(G(k,r)), are nondecreasing in rr; so this rr, 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)G(k,r), which could be larger, nor about the true least rr for which G(k,r)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)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 φ\varphi exists and follow its consequences.

Step 1. (§ 3) The coloring defines two selection rules. They partition the kk-sets and the (k−1)(k-1)-sets into color classes Fi\mathcal{F}_i and Gi\mathcal{G}_i. Properness says that, for every color ii, every set of Fi\mathcal{F}_i is far from every set of Gi\mathcal{G}_i, and hence far from every kk-set containing a member of Gi\mathcal{G}_i. Here “far” means differing in at least rr 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]nx \in[0,1]^n gives the set UU the weight ∏i∈Uxi∏i∉U(1−xi)\prod_{i\in U}x_i\prod_{i\notin U}(1-x_i). Plain proportions, the case x=(12,…,12)x=(\frac12,\ldots,\frac12), 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∗x^* such that every color has the same weighted share among kk-sets as among (k−1)(k-1)-sets. Some color cc then has share at least 1/n1/n on both sides.

Step 4. (§ 6) The (k−1)(k-1)-sets of color cc are lifted to the kk-sets containing them, without losing weighted share.

Step 5. (§ 7) Two families of kk-sets with weighted share at least 1/n1/n always contain two sets that differ in at most 2nln⁡n\sqrt{2n\ln n} elements.

Proof of Theorem 1.3. Under the standing assumption of § 3, let x∗x^* and cc be as in Lemma 5.1, and consider the two families F=Fc\mathcal{F}=\mathcal{F}_c and H=Hc=∇Gc\mathcal{H}=\mathcal{H}_c=\nabla\mathcal{G}_c in the kk-th layer of PP. We collect what has been proved about them.

(i) νx∗,k(F)≥1/n\nu_{x^*,k}(\mathcal{F})\ge1/n, by Lemma 5.1.

(ii) νx∗,k(H)≥1/n\nu_{x^*,k}(\mathcal{H})\ge1/n, by Corollary 6.5.

(iii) dJ(S,U)≥rd_J(S,U)\ge r for all S∈FS\in\mathcal{F} and U∈HU\in\mathcal{H}, by Lemma 3.2.

Lemma 7.1 with N=nN=n, j=kj=k, x=x∗x=x^*, and ρ=1/n\rho=1/n now gives r≤2nln⁡nr\le\sqrt{2n\ln n}. Squaring is valid because both sides are nonnegative, and the result contradicts (4). Hence no proper coloring exists. □

The coloring φ\varphi enters the argument only through the color classes in Step 1 and the choice of x∗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)G(k,r) is bipartite with 2(2k−1k)2\binom{2k-1}{k} vertices; since aSa_S and bTb_T are distinct vertices even when S=TS=T, it has no loops and no multiple edges. All standard lists have size kk.

Fix S∈(Pk)S\in\binom{P}{k}. As ∣P∖S∣=k−1|P\setminus S|=k-1, every kk-set TT meets SS, and a kk-set TT with ∣S∩T∣=t|S\cap T|=t is determined by the independent choices of S∩T⊆SS\cap T\subseteq S and T∖S⊆P∖ST\setminus S\subseteq P\setminus S. The same count applies to the vertices bTb_T, so G(k,r)G(k,r) is regular of degree

Δ(G(k,r))=∑t=1min⁡(r,k)(kt)(k−1k−t)=∑t=1min⁡(r,k)(kt)(k−1t−1).(6)\Delta(G(k,r))=\sum_{t=1}^{\min(r,k)}\binom{k}{t}\binom{k-1}{k-t}=\sum_{t=1}^{\min(r,k)}\binom{k}{t}\binom{k-1}{t-1}. \tag*{(6)}

The edge sets grow with rr, so Δ(G(k,r))\Delta(G(k,r)) is nondecreasing in rr. Let 1≤r≤k/21\le r\le k/2. For 1≤t≤r1\le t\le r we have (k−1t−1)=tk(kt)≤(kt)≤(kr)\binom{k-1}{t-1}=\frac{t}{k}\binom{k}{t}\le\binom{k}{t}\le\binom{k}{r}, the last inequality because (ks+1)(ks)=k−ss+1≥1\frac{\binom{k}{s+1}}{\binom{k}{s}}=\frac{k-s}{s+1}\ge1 whenever 2s+1≤k2s+1\le k. Stirling’s formula gives r!≥(r/e)rr!\ge(r/e)^r, hence (kr)≤kr/r!≤(ek/r)r\binom{k}{r}\le k^r/r!\le(ek/r)^r; and (kr)=∏i=0r−1k−ir−i≥(k/r)r\binom{k}{r}=\prod_{i=0}^{r-1}\frac{k-i}{r-i}\ge(k/r)^r.

Since the term t=rt=r of (6) is at least (kr)\binom{k}{r},

(kr)r≤Δ(G(k,r))≤r(kr)2≤r(ekr)2r(1≤r≤k/2).(7)\binom{k}{r}^{r}\leq\Delta(G(k,r))\leq r\binom{k}{r}^{2}\leq r\left(\frac{ek}{r}\right)^{2r}\qquad(1\leq r\leq k/2). \tag*{(7)}

Proof of Corollary 1.4 from Theorem 1.3. All o(1)o(1) terms refer to k→∞k\to\infty. Write L=ln⁡ΔL=\ln\Delta and L′=ln⁡Δ′L'=\ln\Delta'. Since 2nln⁡n=(4+o(1))kln⁡k2n\ln n=(4+o(1))k\ln k and 2nln⁡n<r≤2nln⁡n+1\sqrt{2n\ln n}<r\leq\sqrt{2n\ln n}+1, we have r=(2+o(1))kln⁡kr=(2+o(1))\sqrt{k\ln k}; hence, for large kk, 1≤r≤k/21\leq r\leq k/2, and ln⁡(k/r)\ln(k/r), ln⁡(ek/r)\ln(ek/r) both equal (12+o(1))ln⁡k(\frac{1}{2}+o(1))\ln k. By (7),

(1+o(1))k(ln⁡k)3/2≤rln⁡kr≤L≤ln⁡r+2rln⁡ekr=(2+o(1))k(ln⁡k)3/2.(1+o(1))\sqrt{k}(\ln k)^{3/2}\leq r\ln\frac{k}{r}\leq L\leq\ln r+2r\ln\frac{ek}{r}=(2+o(1))\sqrt{k}(\ln k)^{3/2}.

Hence ln⁡L=(12+o(1))ln⁡k\ln L=(\frac{1}{2}+o(1))\ln k. Part (a) gives ch⁡(G)≥k+1\operatorname{ch}(G)\geq k+1, and the upper bound on LL gives k≥L2/((4+o(1))(ln⁡k)3)=(132−o(1))L2/(ln⁡L)3k\geq L^2/((4+o(1))(\ln k)^3)=(\frac{1}{32}-o(1))L^2/(\ln L)^3. This proves (b), and ch⁡(G)/L→∞\operatorname{ch}(G)/L\to\infty because L→∞L\to\infty.

For (c), the integer r′r' exceeds 2nln⁡n\sqrt{2n\ln n}, so r′≥rr'\geq r. By monotonicity in rr and (7), L′≥rln⁡(k/r)=(1+o(1))k(ln⁡k)3/2L'\geq r\ln(k/r)=(1+o(1))\sqrt{k}(\ln k)^{3/2}, where the o(1)o(1) depends only on kk. Also Δ′≤(2k−1k)≤4k\Delta'\leq\binom{2k-1}{k}\leq4^k, so ln⁡L′≤ln⁡k+1\ln L'\leq\ln k+1. Therefore k≤(1+o(1))(L′)2/(ln⁡k)3≤(1+o(1))(L′)2/(ln⁡L′)3k\leq(1+o(1))(L')^2/(\ln k)^3\leq(1+o(1))(L')^2/(\ln L')^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≥2k\geq2 and r≥0r\geq0 satisfying (4), let n=2k−1n=2k-1 and P=[n]P=[n], and suppose for contradiction that φ\varphi is a proper coloring of G(k,r)G(k,r) from its standard lists. Sections 4, 6 and 7 also contain general lemmas that do not use φ\varphi, these are stated for an arbitrary finite ground set.

Two selection rules

Define

f(S)=φ(aS)(S∈(Pk))andg(R)=φ(bP∖R)(R∈(Pk−1)).(8)f(S)=\varphi(a_S)\quad\left(S\in\binom{P}{k}\right)\qquad\text{and}\qquad g(R)=\varphi(b_{P\setminus R})\quad\left(R\in\binom{P}{k-1}\right). \tag*{(8)}

The second definition is legitimate since ∣P∖R∣=(2k−1)−(k−1)=k|P\setminus R|=(2k-1)-(k-1)=k, so bP∖Rb_{P\setminus R} is a vertex of BB. The list restrictions give f(S)∈Sf(S)\in S, g(R)∈P∖Rg(R)\in P\setminus R that is g(R)∉Rg(R)\notin R. Thus ff selects an element inside each kk-set, and gg selects an element outside each (k−1)(k-1)-set.

Color classes

Let Fi={S∈(Pk):f(S)=i}\mathcal{F}_i=\{S\in\binom{P}{k}:f(S)=i\} and Gi={R∈(Pk−1):g(R)=i}\mathcal{G}_i=\{R\in\binom{P}{k-1}:g(R)=i\} for each color i∈Pi\in P. The families F1,…,Fn\mathcal{F}_1,\ldots,\mathcal{F}_n partition the kk-th layer of PP, and G1,…,Gn\mathcal{G}_1,\ldots,\mathcal{G}_n partition the (k−1)(k-1)-th layer. Since f(S)=if(S)=i for S∈FiS\in\mathcal{F}_i and g(R)=ig(R)=i for R∈GiR\in\mathcal{G}_i, the list restrictions give

i∈Sfor every S∈Fiandi∉Rfor every R∈Gi.(9)i\in S\quad\text{for every }S\in\mathcal{F}_i\quad\text{and}\quad i\notin R\quad\text{for every }R\in\mathcal{G}_i. \tag*{(9)}

Properness as a distance condition

For U,W∈(Ωj)U,W\in\binom{\Omega}{j}, where Ω\Omega is a finite set, define the Johnson distance

dJ(U,W)=∣U∖W∣=∣W∖U∣=12∣U△W∣,(10)d_J(U,W)=|U\setminus W|=|W\setminus U|=\frac{1}{2}|U\mathbin{\triangle}W|, \tag*{(10)}

the number of elements that must be exchanged to turn UU into WW. The first two quantities agree because ∣U∣=∣W∣|U|=|W|. Nonnegativity and symmetry are immediate, and dJ(U,W)=0d_J(U,W)=0 holds exactly when U=WU=W. For the triangle inequality, the inclusion U∖W⊆(U∖V)∪(V∖W)U\setminus W\subseteq(U\setminus V)\cup(V\setminus W) gives dJ(U,W)≤dJ(U,V)+dJ(V,W)d_J(U,W)\leq d_J(U,V)+d_J(V,W). Thus dJd_J is a metric on each layer, and dJ(U,W)≤jd_J(U,W)\leq j.

Lemma 3.1 (Same color forces distance). If S∈FiS\in\mathcal{F}_i and R∈GiR\in\mathcal{G}_i for the same color ii, then ∣S∖R∣≥r+1|S\setminus R|\geq r+1.

Proof. The vertices aSa_S and bP∖Rb_{P\setminus R} both receive color ii. Since φ\varphi is proper, they are not adjacent, so (2) gives ∣S∩(P∖R)∣>r|S\cap(P\setminus R)|>r. Both sides are integers, and S∩(P∖R)=S∖RS\cap(P\setminus R)=S\setminus R. □\square

The two classes of a color live on different layers. To compare them on one layer, we enlarge the (k−1)(k-1)-sets. For G⊆(Ωj−1)\mathcal{G}\subseteq\binom{\Omega}{j-1}, let ∇G={U∈(Ωj):U⊇R for some R∈G}\nabla\mathcal{G}=\{U\in\binom{\Omega}{j}:U\supseteq R\text{ for some }R\in\mathcal{G}\} be the upper shadow of G\mathcal{G}, and let Hi=∇Gi⊆(Pk)\mathcal{H}_i=\nabla\mathcal{G}_i\subseteq\binom{P}{k} with i∈Pi\in P.

Lemma 3.2 (Far-apart classes). For every color ii, every S∈FiS\in\mathcal{F}_i, and every U∈HiU\in\mathcal{H}_i, we have dJ(S,U)≥rd_J(S,U)\ge r.

Proof. Choose R∈GiR\in\mathcal{G}_i with R⊆UR\subseteq U. By Lemma 3.1, ∣S∖R∣≥r+1|S\setminus R|\ge r+1. Also ∣U∖R∣=1|U\setminus R|=1. Because R⊆UR\subseteq U, every element of S∖RS\setminus R either lies outside UU or belongs to U∖RU\setminus 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|S\cap(U\setminus R)|\le1, dJ(S,U)=∣S∖U∣=∣S∖R∣−∣S∩(U∖R)∣≥(r+1)−1=rd_J(S,U)=|S\setminus U|=|S\setminus R|-|S\cap(U\setminus R)|\ge(r+1)-1=r. □\square

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 cc for which Fc\mathcal{F}_c and Hc\mathcal{H}_c are both “large”; § 7 shows that two large families of kk-sets contain two sets at Johnson distance at most 2nln⁡n<r\sqrt{2n\ln n}<r.

Remark 3.3 (A common color always exists). Some color is used by both rules, by a counting argument. Let CfC_f and CgC_g be the sets of colors used by ff and by gg. Every kk-set SS contains f(S)∈Cff(S)\in C_f, so CfC_f meets every kk-set; hence ∣P∖Cf∣≤k−1|P\setminus C_f|\le k-1, that is, ∣Cf∣≥k|C_f|\ge k. If ∣Cg∣≤k−1|C_g|\le k-1, choose a (k−1)(k-1)-set R⊇CgR\supseteq C_g; then g(R)∈Cg⊆Rg(R)\in C_g\subseteq R, which is impossible. Hence ∣Cg∣≥k|C_g|\ge k. Since ∣Cf∣+∣Cg∣≥2k>∣P∣|C_f|+|C_g|\ge2k>|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 φ\varphi. Throughout it, Ω\Omega is a finite set and x=(xi)i∈Ω∈[0,1]Ωx=(x_i)_{i\in\Omega}\in[0,1]^\Omega.

Product weights

Definition 4.1 (Product weights). The xx-weight of a set U⊆ΩU\subseteq\Omega is

πx(U)=∏i∈Uxi∏i∈Ω∖U(1−xi).\pi_x(U)=\prod_{i\in U}x_i\prod_{i\in\Omega\setminus U}(1-x_i).

an empty product being 1. For a family F\mathcal{F} of subsets of Ω\Omega, put πx(F)=∑U∈Fπx(U)\pi_x(\mathcal{F})=\sum_{U\in\mathcal{F}}\pi_x(U).

The parameter xix_i is a degree of preference for element ii: the closer xix_i is to 1, the heavier the sets containing ii are, relative to the sets avoiding it. If xi=1x_i=1, every set avoiding ii has weight zero, so ii is forced; if xi=0x_i=0, every set containing ii has weight zero, so ii is forbidden. If every xix_i equals 1/21/2, every set has weight 2−∣Ω∣2^{-|\Omega|}.

Lemma 4.2 (Basic properties of the weights). Let J0={i∈Ω:xi=0}J_0=\{i\in\Omega:x_i=0\}, J1={i∈Ω:xi=1}J_1=\{i\in\Omega:x_i=1\}, and Q=Ω∖(J0∪J1)Q=\Omega\setminus(J_0\cup J_1).

(a) πx(U)≥0\pi_x(U)\ge0 for every U⊆ΩU\subseteq\Omega, and ∑U⊆Ωπx(U)=1\sum_{U\subseteq\Omega}\pi_x(U)=1.

(b) For every i∈Ωi\in\Omega, the sets containing ii have total weight xix_i, and the sets avoiding ii have total weight 1−xi1-x_i.

(c) πx(U)>0\pi_x(U)>0 if and only if J1⊆U⊆J1∪QJ_1\subseteq U\subseteq J_1\cup Q. Consequently, πx((Ωj))>0\pi_x\left(\binom{\Omega}{j}\right)>0 if and only if ∣J1∣≤j≤∣J1∣+∣Q∣|J_1|\le j\le|J_1|+|Q|.

(d) If Ω=Ω1⊔Ω2\Omega= \Omega_1 \sqcup\Omega_2 and x(1),x(2)x^{(1)},x^{(2)} denote the restrictions of xx to Ω1,Ω2\Omega_1,\Omega_2, then πx(U)=πx(1)(U∩Ω1)πx(2)(U∩Ω2)\pi_x(U)=\pi_{x^{(1)}}(U\cap\Omega_1)\pi_{x^{(2)}}(U\cap\Omega_2) for every U⊆ΩU\subseteq\Omega.

(e) πx(U)\pi_x(U) is a polynomial in the coordinates of xx. In particular, it depends continuously on xx.

Proof. (a) Every factor in πx(U)\pi_x(U) lies in [0,1][0,1]. Expand the product ∏i∈Ω(xi+(1−xi))=1\prod_{i\in\Omega}(x_i+(1-x_i))=1 by the distributive law, choosing one of the two summands from each factor. Each choice corresponds to exactly one set UU, namely the set of indices at which xix_i was chosen, and the resulting term is πx(U)\pi_x(U). Hence the weights sum to 1.

(b) Expand xi∏ℓ≠i(xℓ+(1−xℓ))=xix_i\prod_{\ell\ne i}(x_\ell+(1-x_\ell))=x_i in the same way. The terms are exactly the weights πx(U)\pi_x(U) of the sets UU containing ii. The statement about sets avoiding ii follows by subtracting from (a).

(c) A product of numbers in [0,1][0,1] is positive exactly when every factor is positive. For i∈Ui\in U the factor xix_i is positive exactly when i∉J0i\notin J_0; for i∉Ui\notin U the factor 1−xi1-x_i is positive exactly when i∉J1i\notin J_1. This proves the first assertion. A set of size jj with positive weight is obtained by adding j−∣J1∣j-|J_1| elements of QQ to J1J_1, which is possible exactly when 0≤j−∣J1∣≤∣Q∣0\leq j-|J_1|\leq|Q|.

(d) Regroup the factors of πx(U)\pi_x(U) according to whether their index lies in Ω1\Omega_1 or in Ω2\Omega_2.

(e) This is immediate from the definition. □

Shares and averages on a layer

Definition 4.3 (Shares and averages). Let jj be an integer with πx((Ωj))>0\pi_x\left(\binom{\Omega}{j}\right)>0. For U∈(Ωj)U\in\binom{\Omega}{j} and F⊆(Ωj)\mathcal{F}\subseteq\binom{\Omega}{j}, define

νx,j(U)=πx(U)πx((Ωj))andνx,j(F)=∑U∈Fνx,j(U).\nu_{x,j}(U)=\frac{\pi_x(U)}{\pi_x\left(\binom{\Omega}{j}\right)} \qquad\text{and}\qquad \nu_{x,j}(\mathcal{F})=\sum_{U\in\mathcal{F}}\nu_{x,j}(U).

We call νx,j(F)\nu_{x,j}(\mathcal{F}) the share of F\mathcal{F} in the jj-th layer. For a function h:(Ωj)→Rh:\binom{\Omega}{j}\to\mathbb{R}, the weighted average of hh is

⟨h⟩x,j=∑U∈(Ωj)νx,j(U)h(U).\langle h\rangle_{x,j}=\sum_{U\in\binom{\Omega}{j}}\nu_{x,j}(U)h(U).

Shares are nonnegative, additive over disjoint families, and the whole layer has share 1. If every xix_i equals 1/21/2, all sets of one layer have the same weight, so νx,j(F)=∣F∣/(∣Ω∣j)\nu_{x,j}(\mathcal{F})=|\mathcal{F}|/\binom{|\Omega|}{j} is the plain proportion and ⟨h⟩x,j\langle h\rangle_{x,j} is the plain average.

In the proof of Theorem 1.3, “Fc\mathcal{F}_c and Hc\mathcal{H}_c are large” will mean that both have share at least 1/n1/n in the kk-th layer of PP, for one suitable vector xx.

The probabilistic reading

The weights have a probabilistic meaning, which explains the terminology of the literature but is not needed for the proofs. Let ZxZ_x be the random subset of Ω\Omega obtained by including each ii independently with probability xix_i.

Weighted counting (this paper)Probability
πx(U)\pi_x(U)Pr⁡(Zx=U)\Pr(Z_x=U)
νx,j(F)\nu_{x,j}(\mathcal{F})Pr⁡(Zx∈F∣∣Zx∣=j)\Pr(Z_x\in\mathcal{F}\mid|Z_x|=j)
⟨h⟩x,j\langle h\rangle_{x,j}expectation of h(Zx)h(Z_x) given ∣Zx∣=j|Z_x|=j
nested transport (Definition 6.1)coupling (R,U)(R,U) with R⊆UR\subseteq U almost surely
prefix averages MiM_i (Lemma 7.2)Doob martingale of h(Zx)h(Z_x)
the sums Φi(λ)\Phi_i(\lambda) (Lemma 7.2)exponential moments of the martingale
Lemma 7.3Hoeffding’s lemma for a two-valued variable

Table 1.

In this language, the coloring is used as follows: the color classes Fi,Gi\mathcal{F}_i,\mathcal{G}_i are fixed families determined by φ\varphi, and the random set ZxZ_x is drawn from a product distribution whose parameters x=x∗x=x^* are themselves determined by φ\varphi (§ 5). Nothing about φ\varphi is random.

Why the weights must depend on the coloring

The uniform weights x=(12,…,12)x=(\frac{1}{2},\ldots,\frac{1}{2}) cannot be used in general. The following example concerns arbitrary rules with f(S)∈Sf(S)\in S and g(R)∉Rg(R)\notin R, not necessarily arising from a proper coloring.

Remark 4.4. Fix X∈(Pk)X\in\binom{P}{k}, put R0=P∖XR_0=P\setminus X, fix z∈Xz\in X, and put S0=R0∪{z}S_0=R_0\cup\{z\}, so that ∣R0∣=k−1|R_0|=k-1, ∣S0∣=k|S_0|=k, and X∩S0={z}X\cap S_0=\{z\}.

  • Every kk-set SS meets XX, because ∣P∖X∣=k−1|P\setminus X|=k-1. Let f(S)f(S) be an element of S∩XS\cap X different from zz whenever such an element exists. This fails only if S∩X={z}S\cap X=\{z\}, that is, only if S=S0S=S_0; put f(S0)=zf(S_0)=z.

  • Every (k−1)(k-1)-set RR misses an element of S0S_0, since ∣S0∣=k|S_0|=k. Let g(R)g(R) be an element of S0∖RS_0\setminus R different from zz whenever such an element exists. This fails only if S0∖R={z}S_0\setminus R=\{z\}, that is, only if R=R0R=R_0, let g(R0)=zg(R_0)=z.

The rule ff uses colors in XX and gg uses colors in S0S_0, so zz is the only color used by both, and it is used only on S0S_0 and on R0R_0. With uniform weights, both classes of zz have share 1/(2k−1k)1/\binom{2k-1}{k}, which is exponentially small. The separation estimate of § 7 applied with this share yields only r≤2nln⁡(2k−1k)r\le\sqrt{2n\ln\binom{2k-1}{k}}. The two middle coefficients (2k−1k−1)=(2k−1k)\binom{2k-1}{k-1}=\binom{2k-1}{k} are the largest of the 2k2k coefficients (2k−1t)\binom{2k-1}{t}, which sum to 22k−12^{2k-1}; hence (2k−1k)≥22k−1/(2k)\binom{2k-1}{k}\ge2^{2k-1}/(2k), and the bound is at least 2n(nln⁡2−ln⁡(n+1))\sqrt{2n(n\ln2-\ln(n+1))}. This exceeds n≥kn\ge k once (2ln⁡2−1)n>2ln⁡(n+1)(2\ln2-1)n>2\ln(n+1), which holds for all large kk. Since no two kk-sets are at Johnson distance more than kk, the bound then carries no information.

By contrast, the weights with xi=1x_i=1 on R0R_0, xi=0x_i=0 on X∖{z}X\setminus\{z\}, and xz=12x_z=\frac{1}{2} give positive weight only to S0S_0 in the kk-th layer and only to R0R_0 in the (k−1)(k-1)-th layer, so color zz has share 11 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 exist x∗∈[0,1]nx^*\in[0,1]^n and a color c∈Pc\in P such that both πx∗((Pk))\pi_{x^*}\left(\binom{P}{k}\right) and πx∗((Pk−1))\pi_{x^*}\left(\binom{P}{k-1}\right) are positive and

νx∗,k(Fc)=νx∗,k−1(Gc)≥1n.(11)\nu_{x^*,k}(\mathcal{F}_c)=\nu_{x^*,k-1}(\mathcal{G}_c)\ge\frac{1}{n}. \tag*{(11)}

The proof uses only that F1,…,Fn\mathcal{F}_1,\ldots,\mathcal{F}_n and G1,…,Gn\mathcal{G}_1,\ldots,\mathcal{G}_n 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=1nxi=k−12}.(12)D=\left\{x\in[0,1]^n:\sum_{i=1}^{n}x_i=k-\frac{1}{2}\right\}. \tag*{(12)}

Since n/2=k−1/2n/2=k-1/2, the vector (1/2,…,1/2)(1/2,\ldots,1/2) belongs to DD, so DD is nonempty. It is the intersection of a closed cube with a closed affine hyperplane. Consequently, it is closed and bounded in Rn\mathbb{R}^n, and hence compact. The cube and the hyperplane are both convex, so their intersection DD is convex as well.

For x∈Dx \in D, define a(x)=πx(Pk)a(x)=\pi_x\binom{P}{k} and b(x)=πx(Pk−1)b(x)=\pi_x\binom{P}{k-1} for the total weights of the two layers. We show that both are positive for every x∈Dx \in D, including points with coordinates equal to 0 or 1. Let uu be the number of coordinates with xi=1x_i=1, and let vv be the number of coordinates with xi>0x_i>0. Since

u≤∑i=1nxi=k−12≤vu \le\sum_{i=1}^{n}x_i=k-\frac{1}{2}\le v

and u,vu,v are integers, we have u≤k−1u \le k-1 and v≥kv \ge k. By Lemma 4.2(c), the jj-th layer has positive weight exactly when u≤j≤vu \le j \le v. In particular,

a(x)>0 and b(x)>0(x∈D).(13)a(x)>0\text{ and }b(x)>0\qquad(x\in D). \tag*{(13)}

The shares νx,k\nu_{x,k} and νx,k−1\nu_{x,k-1} are therefore defined throughout DD. This is the reason for the constraint ∑ixi=k−12\sum_i x_i=k-\frac{1}{2}: 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)A_i(x)=\pi_x(\mathcal{F}_i) and Bi(x)=πx(Gi)B_i(x)=\pi_x(\mathcal{G}_i) for each i∈Pi\in P and x∈Dx\in D. These are the unnormalized weights of the color classes of ii; this is the point at which the coloring enters. They are finite sums of polynomials in xx, so every AiA_i and BiB_i is continuous on DD by Lemma 4.2(e). Since the classes partition the two layers,

∑i=1nAi(x)=a(x),∑i=1nBi(x)=b(x).(14)\sum_{i=1}^{n}A_i(x)=a(x),\qquad\sum_{i=1}^{n}B_i(x)=b(x). \tag*{(14)}

By (9) and Lemma 4.2(b), we have

0≤Ai(x)≤xi and 0≤Bi(x)≤1−xi.(15)0\le A_i(x)\le x_i\text{ and }0\le B_i(x)\le1-x_i. \tag*{(15)}

Also 0≤a(x),b(x)≤10\le a(x),b(x)\le1 by Lemma 4.2(a).

Define a map T:D→RnT:D\to\mathbb{R}^{n} by

Ti(x)=xi+a(x)Bi(x)−b(x)Ai(x)(1≤i≤n).(16)T_i(x)=x_i+a(x)B_i(x)-b(x)A_i(x)\qquad(1\le i\le n). \tag*{(16)}

Each coordinate is continuous, and therefore TT is continuous. We verify that T(x)∈DT(x)\in D whenever x∈Dx\in D. Using (15) and 0≤a(x),b(x)≤10\le a(x),b(x)\le1,

Ti(x)≥xi−b(x)Ai(x)≥xi−Ai(x)≥0,T_i(x)\ge x_i-b(x)A_i(x)\ge x_i-A_i(x)\ge0,
Ti(x)≤xi+a(x)Bi(x)≤xi+Bi(x)≤1.T_i(x)\le x_i+a(x)B_i(x)\le x_i+B_i(x)\le1.

Thus T(x)∈[0,1]nT(x)\in[0,1]^n. Summing (16) over ii and using (14),

∑i=1nTi(x)=∑i=1nxi+a(x)b(x)−b(x)a(x)=k−12.\sum_{i=1}^{n}T_i(x)=\sum_{i=1}^{n}x_i+a(x)b(x)-b(x)a(x)=k-\frac{1}{2}.

This proves T(D)⊆DT(D)\subseteq D.

The map has the following heuristic meaning, which is not used in the proof. Dividing the correction term by a(x)b(x)a(x)b(x), it equals the share of color ii under gg minus its share under ff. If gg uses color ii more heavily than ff does, then TT raises xix_i. This makes the sets containing ii heavier, which tends to increase the share of Fi\mathcal{F}_i and to decrease the share of Gi\mathcal{G}_i.

The fixed point

We use Brouwer’s fixed-point theorem [1]: every continuous map from a closed simplex in Rn\mathbb{R}^n 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]F:[0,1]\to[0,1] is continuous, then F(x)−xF(x)-x is ≥0\geq0 at 00 and ≤0\leq0 at 11, so it vanishes somewhere.

The theorem does not apply to T:D→DT:D\to D directly, because DD is not a simplex: it is a polytope of dimension n−1n-1 lying in a hyperplane of Rn\mathbb{R}^n. We therefore enlarge DD to a simplex Σ\Sigma, and pull Σ\Sigma back onto DD by a continuous map that fixes every point of DD.

The simplex. Let

Σ={z∈Rn:zi≥0 (1≤i≤n), ∑i=1nzi≤n}\Sigma=\left\{z\in\mathbb{R}^n:z_i\geq0\ (1\leq i\leq n),\ \sum_{i=1}^{n}z_i\leq n\right\}

This is the convex hull of the n+1n+1 affinely independent points 0,ne1,…,nen0,ne_1,\ldots,ne_n, where e1,…,ene_1,\ldots,e_n are the unit vectors. Indeed, a point zz with z≥0z\geq0 and ∑izi≤n\sum_i z_i\leq n equals ∑izin(nei)+(1−∑izin)⋅0\sum_i\frac{z_i}{n}(ne_i)+(1-\sum_i\frac{z_i}{n})\cdot0, a convex combination of these points; conversely, every convex combination of them is nonnegative with coordinate sum at most nn. Every x∈Dx\in D satisfies 0≤xi≤10\leq x_i\leq1, hence x≥0x\geq0 and ∑ixi≤n\sum_i x_i\leq n. Thus D⊆ΣD\subseteq\Sigma.

The nearest-point map. We write ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle and ∥⋅∥\lVert\cdot\rVert for the Euclidean inner product and norm on Rn\mathbb{R}^n.

Lemma 5.2 (Nearest points of DD). For every z∈Rnz\in\mathbb{R}^n there is exactly one point pD(z)∈Dp_D(z)\in D with ∥z−pD(z)∥=min⁡y∈D∥z−y∥\lVert z-p_D(z)\rVert=\min_{y\in D}\lVert z-y\rVert. Moreover:

(a) ⟨z−pD(z),y−pD(z)⟩≤0\langle z-p_D(z),y-p_D(z)\rangle\leq0 for every y∈Dy\in D;

(b) ∥pD(z)−pD(z′)∥≤∥z−z′∥\lVert p_D(z)-p_D(z')\rVert\leq\lVert z-z'\rVert for all z,z′∈Rnz,z'\in\mathbb{R}^n; in particular, pDp_D is continuous;

(c) pD(z)=zp_D(z)=z for every z∈Dz\in D.

Proof. By Subsection 5.2, DD is nonempty, compact, and convex.

Existence. The function y↦∥z−y∥y\mapsto\lVert z-y\rVert is continuous on the nonempty compact set DD, so it attains its minimum at some point pp.

Inequality (a) for every minimizer pp. Let y∈Dy\in D and 0<t≤10<t\leq1. By convexity, p+t(y−p)∈Dp+t(y-p)\in D, so by minimality ∥z−p−t(y−p)∥2≥∥z−p∥2\lVert z-p-t(y-p)\rVert^2\geq\lVert z-p\rVert^2. Expanding the left side gives −2t⟨z−p,y−p⟩+t2∥y−p∥2≥0-2t\langle z-p,y-p\rangle+t^2\lVert y-p\rVert^2\geq0. Dividing by tt and letting t→0t\to0 yields ⟨z−p,y−p⟩≤0\langle z-p,y-p\rangle\leq0.

Uniqueness. Let pp and p′p' be minimizers. Applying (a) at pp with y=p′y=p' and at p′p' with y=py=p gives ⟨z−p,p′−p⟩≤0\langle z-p,p'-p\rangle\leq0 and ⟨z−p′,p−p′⟩≤0\langle z-p',p-p'\rangle\leq0. Adding the two inequalities gives ∥p′−p∥2≤0\lVert p'-p\rVert^2\leq0, so p′=pp'=p. Hence pD(z)p_D(z) is well defined, and (a) holds for it.

(b). Let p=pD(z)p=p_D(z) and p′=pD(z′)p'=p_D(z'). By (a), ⟨z−p,p′−p⟩≤0\langle z-p,p'-p\rangle\leq0 and ⟨z′−p′,p−p′⟩≤0\langle z'-p',p-p'\rangle\leq0. Adding these and rearranging, ∥p−p′∥2≤⟨z−z′,p−p′⟩≤∥z−z′∥∥p−p′∥\lVert p-p'\rVert^2\leq\langle z-z',p-p'\rangle\leq\lVert z-z'\rVert\lVert p-p'\rVert, by the Cauchy–Schwarz inequality. If p≠p′p\neq p', dividing by ∥p−p′∥\lVert p-p'\rVert gives (b); if p=p′p=p', (b) holds trivially.

(c). If z∈Dz\in D, then y=zy=z gives distance 00, which is the least possible value, so pD(z)=zp_D(z)=z by uniqueness.

Applying Brouwer’s theorem. Define h:Σ→Rnh:\Sigma\to\mathbb{R}^n by h(z)=T(pD(z))h(z)=T(p_D(z)). By Lemma 5.2(b), pDp_D is continuous, and TT is continuous on DD by Subsection 5.3; hence hh is continuous. Moreover pD(z)∈Dp_D(z)\in D, T(D)⊆DT(D)\subseteq D by Subsection 5.3, and D⊆ΣD\subseteq\Sigma; hence h(Σ)⊆D⊆Σh(\Sigma)\subseteq D\subseteq\Sigma. Brouwer’s theorem therefore gives a point z∈Σz\in\Sigma with T(pD(z))=zT(p_D(z))=z. The left side lies in DD, hence z∈Dz\in D. By Lemma 5.2(c), pD(z)=zp_D(z)=z, and substituting into T(pD(z))=zT(p_D(z))=z gives T(z)=zT(z)=z. Thus there exists x∗∈Dx^*\in D with

T(x∗)=x∗.(17)T(x^*)=x^*. \tag*{(17)}

Proof of Lemma 5.1. Let x∗x^\ast be as in (17). Both layers have positive x∗x^\ast-weight by (13). Substituting T(x∗)=x∗T(x^\ast)=x^\ast into (16) yields a(x∗)Bi(x∗)=b(x∗)Ai(x∗)a(x^\ast)B_i(x^\ast)=b(x^\ast)A_i(x^\ast) for each i∈Pi\in P. Dividing by a(x∗)b(x∗)>0a(x^\ast)b(x^\ast)>0 gives

νx∗,k(Fi)=Ai(x∗)a(x∗)=Bi(x∗)b(x∗)=νx∗,k−1(Gi)=:qi.(18)\nu_{x^\ast,k}(\mathcal{F}_i)=\frac{A_i(x^\ast)}{a(x^\ast)}=\frac{B_i(x^\ast)}{b(x^\ast)}=\nu_{x^\ast,k-1}(\mathcal{G}_i)=:q_i. \tag*{(18)}

Thus, under the weights x∗x^\ast, every color has the same share as an ff-color among the kk-sets as it has as a gg-color among the (k−1)(k-1)-sets. By (14), the numbers qiq_i are nonnegative and sum to 1. If every qiq_i were smaller than 1/n1/n, their sum would be smaller than 1. Consequently, there is a color c∈Pc\in P such that qc≥1/nq_c\ge1/n. □

From now on, x∗x^\ast and cc are fixed as in Lemma 5.1.

Lifting the second class to the upper layer

Lemma 5.1 makes Fc\mathcal{F}_c large among kk-sets and Gc\mathcal{G}_c large among (k−1)(k-1)-sets. Lemma 3.2 compares Fc\mathcal{F}_c with Hc=∇Gc\mathcal{H}_c=\nabla\mathcal{G}_c. This section shows that Hc\mathcal{H}_c is at least as large as Gc\mathcal{G}_c:

νx∗,k(Hc)≥νx∗,k−1(Gc)≥1n.(19)\nu_{x^\ast,k}(\mathcal{H}_c)\ge\nu_{x^\ast,k-1}(\mathcal{G}_c)\ge\frac{1}{n}. \tag*{(19)}

This is not automatic: a single kk-set contains kk different (k−1)(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)(k-1)-set to its supersets.

Nested transports and the upward transfer

Definition 6.1 (Nested transport). Let Ω\Omega be a finite set, and jj an integer. Let α\alpha and β\beta be nonnegative functions of (Ωj−1)\binom{\Omega}{j-1} and (Ωj)\binom{\Omega}{j}, each with a total of 1. A nested transport from α\alpha to β\beta is an assignment of a number t(R,U)≥0t(R,U)\ge0 to every pair R∈(Ωj−1)R\in\binom{\Omega}{j-1}, U∈(Ωj)U\in\binom{\Omega}{j} with R⊆UR\subseteq U, such that

∑U⊇Rt(R,U)=α(R)(R∈(Ωj−1)),∑R⊆Ut(R,U)=β(U)(U∈(Ωj)).(20)\begin{aligned} \sum_{U\supseteq R}t(R,U)&=\alpha(R) &&\left(R\in\binom{\Omega}{j-1}\right),& \sum_{R\subseteq U}t(R,U)&=\beta(U) &&\left(U\in\binom{\Omega}{j}\right). \tag*{(20)} \end{aligned}

Here the sums run over U∈(Ωj)U\in\binom{\Omega}{j} and R∈(Ωj−1)R\in\binom{\Omega}{j-1}, respectively.

In words, each set RR of the lower layer ships its amount α(R)\alpha(R) to its supersets, and each set UU of the upper layer receives exactly β(U)\beta(U).

Example 6.2. Let ∣Ω∣=2k−1|\Omega|=2k-1, let α\alpha and β\beta be the uniform functions on the layers k−1k-1 and kk, and put M=(2k−1k)=(2k−1k−1)M=\binom{2k-1}{k}=\binom{2k-1}{k-1}. Every (k−1)(k-1)-set has exactly kk supersets in the kk-th layer, and every kk-set has exactly kk subsets in the (k−1)(k-1)-th layer. Hence t(R,U)=1/(kM)t(R,U)=1/(kM) for all R⊆UR\subseteq 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 α\alpha to β\beta, then β(∇G)≥α(G)\beta(\nabla G)\ge\alpha(G) for every G⊆(Ωj−1)G\subseteq\binom{\Omega}{j-1}.

Proof. By the first identity in (20),

α(G)=∑R∈G∑U⊇Rt(R,U).\alpha(G)=\sum_{R\in G}\sum_{U\supseteq R}t(R,U).

Every pair (R,U)(R,U) in this double sum has U∈∇GU \in\nabla G. Adding the nonnegative terms t(R,U)t(R,U) with U∈∇GU \in\nabla G and R∉GR \notin G, and then applying the second identity in (20), we obtain

α(G)≤∑U∈∇G∑R⊆Ut(R,U)=β(∇G).\alpha(G) \le\sum_{U \in\nabla G}\sum_{R \subseteq U} t(R,U) = \beta(\nabla G).

Existence of nested transports, and the lift

Proposition 6.4 (Nested transport for product weights). Let Ω\Omega be a finite set, x∈[0,1]Ωx \in[0,1]^\Omega, and jj an integer. If πx((Ωj−1))>0\pi_x\left(\binom{\Omega}{j-1}\right)>0 and πx((Ωj))>0\pi_x\left(\binom{\Omega}{j}\right)>0, then there is a nested transport from νx,j−1\nu_{x,j-1} to νx,j\nu_{x,j}. Consequently, νx,j(∇G)≥νx,j−1(G)\nu_{x,j}(\nabla G) \ge\nu_{x,j-1}(G) with G⊆(Ωj−1)G \subseteq\binom{\Omega}{j-1}.

Corollary 6.5. Inequality (19) holds.

Proof. Apply Proposition 6.4 with Ω=P\Omega=P, x=x∗x=x^*, j=kj=k and G=GcG=G_c, 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>0w_1,\ldots,w_N>0. Let w(U)=∏i∈Uwiw(U)=\prod_{i\in U}w_i for U⊆[N]U\subseteq[N], and for 0≤j≤N0\le j\le N define the total layer and the normalized weight

Wj=Wj(w1,…,wN)=∑U∈([N]j)w(U)>0,ωj(U)=w(U)Wj(U∈([N]j)).(21)W_j=W_j(w_1,\ldots,w_N)=\sum_{U\in\binom{[N]}{j}}w(U)>0,\qquad\omega_j(U)=\frac{w(U)}{W_j}\quad\left(U\in\binom{[N]}{j}\right). \tag*{(21)}

We set Wj=0W_j=0 for j<0j<0 and j>Nj>N. Expanding the product by choosing either 11 or wizw_i z from each factor gives

∏i=1N(1+wiz)=∑j=0NWjzj.(22)\prod_{i=1}^{N}(1+w_i z)=\sum_{j=0}^{N}W_jz^j. \tag*{(22)}

Lemma 6.6. The coefficients in (22) form a log-concave sequence: for every integer jj, Wj2≥Wj−1Wj+1W_j^2\ge W_{j-1}W_{j+1}.

Proof. We first establish a preservation property. Let (aj)j∈Z(a_j)_{j\in\mathbb{Z}} be a nonzero, finitely supported sequence of nonnegative numbers whose positive entries have consecutive indices. Suppose that aj2≥aj−1aj+1a_j^2\ge a_{j-1}a_{j+1} with j∈Zj\in\mathbb{Z}. Given w>0w>0, let bj=aj+waj−1b_j=a_j+wa_{j-1}. Expanding both products and collecting the coefficients of 1,w,w21,w,w^2, we obtain

bj2−bj−1bj+1=aj2−aj−1aj+1+w(ajaj−1−aj−2aj+1)+w2(aj−12−aj−2aj).(23)b_j^2-b_{j-1}b_{j+1}=a_j^2-a_{j-1}a_{j+1}+w(a_ja_{j-1}-a_{j-2}a_{j+1})+w^2(a_{j-1}^2-a_{j-2}a_j). \tag*{(23)}

The first and third terms are nonnegative by the assumed log-concavity. To treat the middle term, first suppose that aj−2aj+1=0a_{j-2}a_{j+1}=0. Then its nonnegativity follows from ajaj−1≥0a_ja_{j-1}\ge0. If instead aj−2aj+1>0a_{j-2}a_{j+1}>0, consecutiveness of the positive support implies that all four entries aj−2,aj−1,aj,aj+1a_{j-2},a_{j-1},a_j,a_{j+1} are positive. Dividing the log-concavity inequalities at indices j−1j-1 and jj by the relevant positive products gives

aj−1aj−2≥ajaj−1≥aj+1aj.\frac{a_{j-1}}{a_{j-2}}\ge\frac{a_j}{a_{j-1}}\ge\frac{a_{j+1}}{a_j}.

Comparing the first and last ratios and multiplying by aj−2aj>0a_{j-2}a_j>0 yields aj−1aj≥aj−2aj+1a_{j-1}a_j\ge a_{j-2}a_{j+1}. Thus every term on the right-hand side of (23) is nonnegative, and (bj)(b_j) is log-concave. Moreover, if the positive support of (aj)(a_j) is {ℓ,…,u}\{\ell,\ldots,u\}, the positive support of (bj)(b_j) is exactly {ℓ,…,u+1}\{\ell,\ldots,u+1\}: the two shifted supports overlap or are consecutive, and w>0w > 0. Hence the support condition is preserved as well.

Start with a0=1a_0 = 1 and aj=0a_j = 0 for j≠0j \ne0. This sequence is log-concave and has consecutive positive support. Successively multiply its generating polynomial by 1+w1z,…,1+wNz1 + w_1z,\ldots,1 + w_Nz. Multiplication by 1+wz1 + wz replaces the coefficient sequence (aj)(a_j) by (aj+waj−1)(a_j + wa_{j-1}), so the preceding argument applies at every step. By (22), the final coefficient sequence is (Wj)(W_j), proving the lemma. □

Lemma 6.7 (Nested transport for positive weights). For positive weights w1,…,wNw_1,\ldots,w_N and every 1≤j≤N1 \le j \le N, there is a nested transport from ωj−1\omega_{j-1} to ωj\omega_j.

Proof. We argue by induction on NN. For N=1N = 1, necessarily j=1j = 1; the layers are {∅}\{\varnothing\} and {{1}}\{\{1\}\}, both normalized weights equal 11, and t(∅,{1})=1t(\varnothing,\{1\}) = 1 is a nested transport.

Suppose now that N≥2N \ge2 and that the assertion holds for N−1N - 1 elements. Write Wt′W'_t and ωt′\omega'_t for the quantities (21) computed from w1,…,wN−1w_1,\ldots,w_{N-1}; thus Wt′>0W'_t > 0 for 0≤t≤N−10 \le t \le N - 1 and Wt′=0W'_t = 0 otherwise. Splitting the sets of size tt according to whether they contain NN gives

Wt=Wt′+wNWt−1′.(24)W_t = W'_t + w_N W'_{t-1}. \tag*{(24)}

For 0≤t≤N0 \le t \le N, let

pt=wNWt−1′Wt(25)p_t = \frac{w_N W'_{t-1}}{W_t} \tag*{(25)}

be the share of the tt-th layer of [N][N] occupied by sets containing NN. Then p0=0p_0 = 0 and pN=1p_N = 1, and 1−pt=Wt′/Wt1 - p_t = W'_t/W_t by (24). Directly from the definitions,

ωt(V)=(1−pt)ωt′(V)(V⊆[N−1], ∣V∣=t, 0≤t≤N−1),(26)\omega_t(V) = (1 - p_t)\omega'_t(V) \qquad(V \subseteq[N - 1],\ |V| = t,\ 0 \le t \le N - 1), \tag*{(26)}
ωt(V∪{N})=ptωt−1′(V)(V⊆[N−1], ∣V∣=t−1, 1≤t≤N).(27)\omega_t(V \cup\{N\}) = p_t\omega'_{t-1}(V) \qquad(V \subseteq[N - 1],\ |V| = t - 1,\ 1 \le t \le N). \tag*{(27)}

Indeed, the right-hand side of (26) is (Wt′/Wt)(w(V)/Wt′)=w(V)/Wt(W'_t/W_t)(w(V)/W'_t) = w(V)/W_t, and that of (27) is (wNWt−1′/Wt)(w(V)/Wt−1′)=w(V∪{N})/Wt(w_NW'_{t-1}/W_t)(w(V)/W'_{t-1}) = w(V \cup\{N\})/W_t; all denominators are positive in the stated ranges.

We next show pj−1≤pjp_{j-1} \le p_j for 1≤j≤N1 \le j \le N. For j=1j = 1 this reads 0≤p10 \le p_1, and for j=Nj = N it reads pN−1≤1p_{N-1} \le1. For 2≤j≤N−12 \le j \le N - 1, subtraction over a common denominator yields

pj−pj−1=wN((Wj−1′)2−Wj−2′Wj′)WjWj−1≥0,p_j - p_{j-1} = \frac{w_N\left((W'_{j-1})^2 - W'_{j-2}W'_j\right)}{W_jW_{j-1}} \ge0,

because the denominator is positive and the numerator is nonnegative by Lemma 6.6 applied to w1,…,wN−1w_1,\ldots,w_{N-1}. Fix 1≤j≤N1 \le j \le N. Every pair R⊆UR \subseteq U with ∣R∣=j−1|R| = j - 1 and ∣U∣=j|U| = j is of exactly one of the following three kinds, and we define t(R,U)t(R,U) accordingly.

(K1) N∉UN \notin U. Such pairs exist only if j≤N−1j \le N - 1; then the induction hypothesis gives a nested transport t′t' from ωj−1′\omega'_{j-1} to ωj′\omega'_j on [N−1][N - 1], and we put t(R,U)=(1−pj)t′(R,U)t(R,U) = (1 - p_j)t'(R,U).

(K2) N∉RN \notin R and N∈UN \in U. Then U=R∪{N}U = R \cup\{N\}, since U∖RU \setminus R has one element. Put t(R,U)=(pj−pj−1)ωj−1′(R)t(R,U) = (p_j - p_{j-1})\omega'_{j-1}(R).

(K3) N∈RN \in R. Write R=R′∪{N}R = R' \cup\{N\} and U=U′∪{N}U = U' \cup\{N\}, so R′⊆U′⊆[N−1]R' \subseteq U' \subseteq[N - 1] and ∣R′∣=j−2|R'| = j - 2. Such pairs exist only if j≥2j \ge2; then 1≤j−1≤N−11 \le j - 1 \le N - 1, so the induction hypothesis gives a nested transport t′′t'' from ωj−2′\omega'_{j-2} to ωj−1′\omega'_{j-1} on [N−1][N - 1], and we put t(R,U)=pj−1t′′(R′,U′)t(R,U) = p_{j-1}t''(R',U').

All these numbers are nonnegative because 0≤pj−1≤pj≤10 \le p_{j-1} \le p_j \le1.

Amount shipped by RR with $N \notin R. The supersets of RR are the sets U⊆[N−1]U \subseteq[N - 1] of kind (K1), together with R∪{N}R \cup\{N\} of kind (K2). If j≤N−1j \le N - 1, the first group ships (1−pj)ωj−1′(R)(1 - p_j)\omega'_{j-1}(R) in total; if j=Nj=N, there is no such UU, and 1−pN=01-p_N=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)(1-p_j)\omega'_{j-1}(R)+(p_j-p_{j-1})\omega'_{j-1}(R)=(1-p_{j-1})\omega'_{j-1}(R)=\omega_{j-1}(R) by (26) with t=j−1t=j-1.

Amount shipped by R=R′∪{N}R=R'\cup\{N\}. This requires j≥2j\ge2. All supersets are of kind (K3), and the total is pj−1ωj−2′(R′)=ωj−1(R)p_{j-1}\omega'_{j-2}(R')=\omega_{j-1}(R) by (27) with t=j−1t=j-1.

Amount received by UU with N∉UN\notin U. This requires j≤N−1j\le N-1. All subsets are of kind (K1), and the total is (1−pj)ωj′(U)=ωj(U)(1-p_j)\omega'_j(U)=\omega_j(U) by (26) with t=jt=j.

Amount received by U=U′∪{N}U=U'\cup\{N\}. The subsets of UU in the (j−1)(j-1)-th layer are U′U', of kind (K2), and the sets R′∪{N}R'\cup\{N\} with R′⊆U′R'\subseteq U', of kind (K3). The total is (pj−pj−1)ωj−1′(U′)+pj−1ωj−1′(U′)=pjωj−1′(U′)=ωj(U)(p_j-p_{j-1})\omega'_{j-1}(U')+p_{j-1}\omega'_{j-1}(U')=p_j\omega'_{j-1}(U')=\omega_j(U) by (27) with t=jt=j. When j=1j=1 there are no sets of kind (K3), and the formula remains correct because p0=0p_0=0.

Thus tt satisfies (20), completing the induction. □

Forced and forbidden elements

Lemma 6.8 (Reduction to positive weights). Let Ω\Omega be a finite set and x∈[0,1]Ωx\in[0,1]^\Omega. Let J0,J1,QJ_0,J_1,Q be as in Lemma 4.2, put u=∣J1∣u=|J_1|, and give each i∈Qi\in Q the positive weight wi=xi/(1−xi)w_i=x_i/(1-x_i). If πx((Ωj))>0\pi_x\left(\binom{\Omega}{j}\right)>0, then for every U∈(Ωj)U\in\binom{\Omega}{j},

νx,j(U)={ωj−u(U∖J1)if J1⊆U⊆J1∪Q,0otherwise.\nu_{x,j}(U)= \begin{cases} \omega_{j-u}(U\setminus J_1) & \text{if } J_1\subseteq U\subseteq J_1\cup Q,\\ 0 & \text{otherwise}. \end{cases}

where ωj−u\omega_{j-u} is computed on the ground set QQ from the weights (wi)i∈Q(w_i)_{i\in Q}.

Proof. If UU is not of the form J1∪VJ_1\cup V with V⊆QV\subseteq Q, then πx(U)=0\pi_x(U)=0 by Lemma 4.2(c). If U=J1∪VU=J_1\cup V with V⊆QV\subseteq Q, then the factors for i∈J0∪J1i\in J_0\cup J_1 all equal 11, and

πx(U)=∏i∈Vxi∏i∈Q∖V(1−xi)=γ∏i∈Vwi,γ=∏i∈Q(1−xi)>0.\pi_x(U)=\prod_{i\in V}x_i\prod_{i\in Q\setminus V}(1-x_i)=\gamma\prod_{i\in V}w_i,\qquad\gamma=\prod_{i\in Q}(1-x_i)>0.

Summing over all V∈(Qj−u)V\in\binom{Q}{j-u} gives πx((Ωj))=γWj−u\pi_x\left(\binom{\Omega}{j}\right)=\gamma W_{j-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−1u\le j-1 and j≤u+∣Q∣j\le u+|Q|, that is, 1≤j−u≤∣Q∣1\le j-u\le|Q|. In particular Q≠∅Q\ne\varnothing. Label the elements of QQ by 1,…,∣Q∣1,\ldots,|Q| and apply Lemma 6.7 to obtain a nested transport tQt_Q from ωj−1−u\omega_{j-1-u} to ωj−u\omega_{j-u} on QQ. Let t(J1∪V,J1∪V′)=tQ(V,V′)t(J_1\cup V,J_1\cup V')=t_Q(V,V') when V⊆V′⊆QV\subseteq V'\subseteq Q, and t(R,U)=0t(R,U)=0 for all other pairs R⊆UR\subseteq U. Each pair receiving a possibly positive value satisfies J1∪V⊆J1∪V′J_1\cup V\subseteq J_1\cup V'. By Lemma 6.8, a set RR of the form J1∪VJ_1\cup V ships ∑V′tQ(V,V′)=ωj−1−u(V)=νx,j−1(R)\sum_{V'}t_Q(V,V')=\omega_{j-1-u}(V)=\nu_{x,j-1}(R), and every other set of the lower layer ships 0=νx,j−1(R)0=\nu_{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\mathcal{F}_c and Hc\mathcal{H}_c both have share at least 1/n1/n in the kk-th layer under the weights x∗x^*. This section shows that two such families cannot be far apart. Its results are general facts about weights and do not use φ\varphi.

Statement

Lemma 7.1 (Separation of two families). Let Ω=[N]\Omega=[N] with N≥1N\ge1, let x∈[0,1]Nx\in[0,1]^N, let πx(([N]j))>0\pi_x\left(\binom{[N]}{j}\right)>0, and write ν=νx,j\nu=\nu_{x,j}. Suppose that F,H⊆([N]j)\mathcal{F},\mathcal{H}\subseteq\binom{[N]}{j}, ν(F),ν(H)≥ρ\nu(\mathcal{F}),\nu(\mathcal{H})\ge\rho and 0<ρ≤10<\rho\le1. If r≥0r\ge0 satisfies dJ(S,U)≥rd_J(S,U)\ge r for every S∈FS\in\mathcal{F} and U∈HU\in\mathcal{H}, then

r≤2Nln⁡(1/ρ).(28)r\le\sqrt{2N\ln(1/\rho)}. \tag*{(28)}

The idea is an isoperimetric one. Let h(U)h(U) be the distance from UU to F\mathcal{F}. A single exchange changes hh by at most 1, and such a function is nearly constant on most of the layer (Lemma 7.2). Since hh vanishes on the large family F\mathcal{F}, its average is small; since h≥rh\ge r on the large family H\mathcal{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)=qd_J(U,W)=q, enumerate the differences as U∖W={u1,…,uq}U\setminus W=\{u_1,\ldots,u_q\} and W∖U={w1,…,wq}W\setminus U=\{w_1,\ldots,w_q\}. Starting at UU, replace usu_s by wsw_s for s=1,…,qs=1,\ldots,q. Each intermediate set has size jj, each step is one exchange, and the final set is WW. A real-valued function hh on a layer is 1-Lipschitz if ∣h(U)−h(W)∣≤dJ(U,W)|h(U)-h(W)|\le d_J(U,W) when U,W∈([N]j)U,W\in\binom{[N]}{j}. It suffices to check this inequality when dJ(U,W)=1d_J(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]\Omega=[N] with N≥1N\ge1, let x∈[0,1]Nx\in[0,1]^N, and let jj be an integer with πx(([N]j))>0\pi_x\left(\binom{[N]}{j}\right)>0. Write ν=νx,j\nu=\nu_{x,j}. If h:([N]j)→Rh:\binom{[N]}{j}\to\mathbb{R} is 1-Lipschitz and hˉ=⟨h⟩x,j\bar h=\langle h\rangle_{x,j}, then, for every t≥0t\ge0,

ν{U:h(U)≥hˉ+t}≤e−2t2/N,(29)\nu\{U:h(U)\ge\bar h+t\}\le e^{-2t^2/N}, \tag*{(29)}
ν{U:h(U)≤hˉ−t}≤e−2t2/N.(30)\nu\{U:h(U)\le\bar h-t\}\le e^{-2t^2/N}. \tag*{(30)}

Proof of Lemma 7.1 from Lemma 7.2

Proof of Lemma 7.1. Because ν(F)>0\nu(\mathcal{F})>0, the family F\mathcal{F} is nonempty. Define its distance function on the entire layer by h(U)=min⁡S∈FdJ(U,S)h(U)=\min_{S\in\mathcal{F}}d_J(U,S). The minimum exists because F\mathcal{F} is finite. To verify the Lipschitz property, fix U,WU,W and choose SW∈FS_W\in\mathcal{F} with h(W)=dJ(W,SW)h(W)=d_J(W,S_W). The triangle inequality gives h(U)≤dJ(U,SW)≤dJ(U,W)+dJ(W,SW)=dJ(U,W)+h(W)h(U)\le d_J(U,S_W)\le d_J(U,W)+d_J(W,S_W)=d_J(U,W)+h(W). Interchanging U,WU,W yields ∣h(U)−h(W)∣≤dJ(U,W)|h(U)-h(W)|\le d_J(U,W). Thus hh is 1-Lipschitz. It is also nonnegative, and h(U)=0h(U)=0 if and only if U∈FU\in\mathcal{F}.

Let η=⟨h⟩x,j≥0\eta=\langle h\rangle_{x,j}\ge0 and τ=N2ln⁡(1/ρ)\tau=\sqrt{\frac{N}{2}\ln(1/\rho)}. Since h≥0h\ge0, the families {U:h(U)=0}\{U:h(U)=0\} and {U:h(U)≤η−η}\{U:h(U)\le\eta-\eta\} coincide. Apply (30) with t=ηt=\eta to obtain ρ≤ν(F)=ν{U:h(U)=0}≤e−2η2/N\rho\le\nu(\mathcal{F})=\nu\{U:h(U)=0\}\le e^{-2\eta^2/N}. Taking natural logarithms gives ln⁡ρ≤−2η2/N\ln\rho\le-2\eta^2/N, or equivalently η2≤N2ln⁡(1/ρ)=τ2\eta^2\le\frac{N}{2}\ln(1/\rho)=\tau^2. As both η\eta and τ\tau are nonnegative, we conclude that η≤τ\eta\le\tau.

If r≤ηr\le\eta, then r≤τ≤2τr\le\tau\le2\tau, which already proves the required bound. If r>ηr>\eta, the separation hypothesis implies h(U)≥rh(U)\ge r for every U∈HU\in\mathcal{H}: every distance in the minimum defining h(U)h(U) is at least rr. Applying (29) with the positive threshold t=r−ηt=r-\eta yields ρ≤ν(H)≤ν{U:h(U)≥r}≤e−2(r−η)2/N\rho\le\nu(\mathcal{H})\le\nu\{U:h(U)\ge r\}\le e^{-2(r-\eta)^2/N}. Taking logarithms and using r−η>0r-\eta>0 gives r−η≤τr-\eta\le\tau. Combining this with η≤τ\eta\le\tau proves r≤η+τ≤2τ=2Nln⁡(1/ρ)r\le\eta+\tau\le2\tau=\sqrt{2N\ln(1/\rho)}.

This also covers ρ=1\rho=1. Indeed, then τ=0\tau=0 and the first estimate forces η=0\eta=0. If r>0r>0, the second estimate would give 1≤e−2r2/N<11\le e^{-2r^2/N}<1, a contradiction. Hence r=0r=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 every p∈[0,1]p \in[0,1] and every real ss, pe(1−p)s+(1−p)e−ps≤es2/8p e^{(1-p)s}+(1-p)e^{-ps}\le e^{s^2/8}.

Proof. Put D(s)=1−p+pesD(s)=1-p+pe^s. This is positive for every ss: if p<1p<1 then 1−p>01-p>0, and if p=1p=1 then D(s)=esD(s)=e^s. The left-hand side equals e−psD(s)e^{-ps}D(s), hence its logarithm is γ(s)=−ps+ln⁡D(s)\gamma(s)=-ps+\ln D(s). We have γ(0)=ln⁡1=0\gamma(0)=\ln1=0 and γ′(s)=−p+pesD(s)\gamma'(s)=-p+\frac{pe^s}{D(s)} with γ′(0)=0\gamma'(0)=0. Differentiating once more and writing a=pes≥0a=pe^s\ge0 and b=1−p≥0b=1-p\ge0, so that a+b=D(s)>0a+b=D(s)>0,

γ′′(s)=pesD(s)−(pes)2D(s)2=ab(a+b)2≤14,\gamma''(s)=\frac{pe^sD(s)-(pe^s)^2}{D(s)^2}=\frac{ab}{(a+b)^2}\le\frac{1}{4},

where the last step is (a+b)2−4ab=(a−b)2≥0(a+b)^2-4ab=(a-b)^2\ge0. Let H(s)=s2/8−γ(s)H(s)=s^2/8-\gamma(s). Then H(0)=H′(0)=0H(0)=H'(0)=0 and H′′(s)=1/4−γ′′(s)≥0H''(s)=1/4-\gamma''(s)\ge0. By the mean value theorem, H′H' is nondecreasing, so H′≥0H'\ge0 on [0,∞)[0,\infty) and H′≤0H'\le0 on (−∞,0](-\infty,0]. Applying the mean value theorem again, HH is nondecreasing on [0,∞)[0,\infty) and nonincreasing on (−∞,0](-\infty,0], so H(s)≥H(0)=0H(s)\ge H(0)=0 for every ss. Exponentiating γ(s)≤s2/8\gamma(s)\le s^2/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 11, and NN such changes rarely add up to much more than N\sqrt{N}.

Proof of Lemma 7.2. Let S={U∈([N]j):πx(U)>0}S=\{U\in\binom{[N]}{j}:\pi_x(U)>0\}, so that ν(S)=1\nu(S)=1. For 0≤i≤N0\le i\le N and U∈SU\in S, let Ci(U)={U′∈S:U′∩[i]=U∩[i]}C_i(U)=\{U'\in S:U'\cap[i]=U\cap[i]\} be the class of UU at level ii, consisting of the sets of positive weight that agree with UU on the first ii elements. Since U∈Ci(U)U\in C_i(U), we have ν(Ci(U))>0\nu(C_i(U))>0, and we may define the prefix average

Mi(U)=1ν(Ci(U))∑U′∈Ci(U)ν(U′)h(U′).M_i(U)=\frac{1}{\nu(C_i(U))}\sum_{U'\in C_i(U)}\nu(U')h(U').

The classes at level ii partition SS, and MiM_i is constant on each of them. At level 00 there is a single class SS, so M0(U)=hˉM_0(U)=\bar h; at level NN every class is a single set, so MN(U)=h(U)M_N(U)=h(U).

Fix 1≤i≤N1\le i\le N and a class CC at level i−1i-1. Its members share the trace Y=U∩[i−1]Y=U\cap[i-1]; put q=∣Y∣q=|Y| and let mm be the value of Mi−1M_{i-1} on CC. The class splits into C1={U∈C:i∈U}C^1=\{U\in C:i\in U\} and C0={U∈C:i∉U}C^0=\{U\in C:i\notin U\}, each of which is empty or a class at level ii. Let u1u_1 and u0u_0 be the values of MiM_i on C1C^1 and C0C^0, when these are nonempty. Since the sum defining Mi−1M_{i-1} on CC splits along C=C1⊔C0C=C^1\sqcup C^0,

ν(C)m=ν(C1)u1+ν(C0)u0,(31)\nu(C)m=\nu(C^1)u_1+\nu(C^0)u_0, \tag*{(31)}

where a term is omitted if its class is empty.

Step 1: one decision moves the average by at most one. Suppose that C1C^1 and C0C^0 are both nonempty. We claim that ∣u1−u0∣≤1|u_1-u_0|\le1.

Let Qi={i+1,…,N}Q_i=\{i+1,\ldots,N\} and let yy be the restriction of xx to QiQ_i. Fix ε∈{0,1}\varepsilon\in\{0,1\} and put Z={i}Z=\{i\} if ε=1\varepsilon=1 and Z=∅Z=\varnothing if ε=0\varepsilon=0. Every set in the jj-th layer that agrees with YY on [i−1][i-1] and satisfies the ε\varepsilon-condition at ii has the form Y∪Z∪VY\cup Z\cup V with V∈(Qij−q−ε)V\in\binom{Q_i}{j-q-\varepsilon}, and every such VV gives such a set. By Lemma 4.2(d) with Ω=[i]⊔Qi\Omega=[i]\sqcup Q_i, πx(Y∪Z∪V)=κεπy(V)\pi_x(Y\cup Z\cup V)=\kappa_\varepsilon\pi_y(V) and κε=πx∣[i](Y∪Z)\kappa_\varepsilon=\pi_{x|_{[i]}}(Y\cup Z), where κε\kappa_\varepsilon does not depend on VV. Because CεC^\varepsilon is nonempty, some such set has positive weight, so κε>0\kappa_\varepsilon>0 and πy((Qj−q−εi))>0\pi_y\left(\left(Q^i_{j-q-\varepsilon}\right)\right)>0. The members of CεC^\varepsilon are exactly the sets Y∪Z∪VY\cup Z\cup V with πy(V)>0\pi_y(V)>0. Dividing the last display by its sum over VV shows that

ν(Y∪Z∪V)ν(Cε)=νy,j−q−ε(V)(V∈(Qj−q−εi)).\frac{\nu(Y\cup Z\cup V)}{\nu(C^\varepsilon)}=\nu_{y,j-q-\varepsilon}(V)\qquad\left(V\in\left(Q^i_{j-q-\varepsilon}\right)\right).

where both sides vanish when πy(V)=0\pi_y(V)=0. Therefore

u1=∑Vνy,j−q−1(V)h(Y∪{i}∪V)andu0=∑Wνy,j−q(W)h(Y∪W),u_1=\sum_V\nu_{y,j-q-1}(V)h(Y\cup\{i\}\cup V)\quad\text{and}\quad u_0=\sum_W\nu_{y,j-q}(W)h(Y\cup W),

the sums running over (Qj−q−1i)\left(Q^i_{j-q-1}\right) and (Qj−qi)\left(Q^i_{j-q}\right).

Both layers j−q−1j-q-1 and j−qj-q of QiQ_i have positive yy-weight, so Proposition 6.4 gives a nested transport tt from νy,j−q−1\nu_{y,j-q-1} to νy,j−q\nu_{y,j-q} on QiQ_i. Expanding u1u_1 with the first identity in (20) and u0u_0 with the second,

u1−u0=∑V⊆Wt(V,W)(h(Y∪{i}∪V)−h(Y∪W)).u_1-u_0=\sum_{V\subseteq W}t(V,W)\bigl(h(Y\cup\{i\}\cup V)-h(Y\cup W)\bigr).

For each pair V⊆WV\subseteq W, the sets Y∪{i}∪VY\cup\{i\}\cup V and Y∪WY\cup W differ by one exchange: i∉Y∪Wi\notin Y\cup W, and W∖VW\setminus V has exactly one element, hence (Y∪{i}∪V)∖(Y∪W)={i}(Y\cup\{i\}\cup V)\setminus(Y\cup W)=\{i\} and (Y∪W)∖(Y∪{i}∪V)=W∖V(Y\cup W)\setminus(Y\cup\{i\}\cup V)=W\setminus V. Hence each bracket has absolute value at most 1. The numbers t(V,W)t(V,W) are nonnegative and sum to ∑Vνy,j−q−1(V)=1\sum_V\nu_{y,j-q-1}(V)=1, so ∣u1−u0∣≤1|u_1-u_0|\leq1.

Step 2: exponential sums. For real λ\lambda and 0≤i≤N0\leq i\leq N, define

Φi(λ)=∑U∈Sν(U)eλ(Mi(U)−hˉ).\Phi_i(\lambda)=\sum_{U\in\mathcal{S}}\nu(U)e^{\lambda(M_i(U)-\bar h)}.

Then Φ0(λ)=1\Phi_0(\lambda)=1. We claim that Φi(λ)≤eλ2/8Φi−1(λ)\Phi_i(\lambda)\leq e^{\lambda^2/8}\Phi_{i-1}(\lambda) for 1≤i≤N1\leq i\leq N.

Group the sum according to the classes at level i−1i-1. A class CC as above contributes ν(C)eλ(m−hˉ)\nu(C)e^{\lambda(m-\bar h)} to Φi−1(λ)\Phi_{i-1}(\lambda) and ν(C1)eλ(u1−hˉ)+ν(C0)eλ(u0−hˉ)\nu(C^1)e^{\lambda(u_1-\bar h)}+\nu(C^0)e^{\lambda(u_0-\bar h)} to Φi(λ)\Phi_i(\lambda), with a term omitted if its class is empty. If one of C1,C0C^1,C^0 is empty, the other equals CC, its value of MiM_i equals mm by (31), and the two contributions coincide. Otherwise put p=ν(C1)/ν(C)∈(0,1)p=\nu(C^1)/\nu(C)\in(0,1) and δ=u1−u0\delta=u_1-u_0. By (31), m=pu1+(1−p)u0m=pu_1+(1-p)u_0, hence u1−m=(1−p)δu_1-m=(1-p)\delta and u0−m=−pδu_0-m=-p\delta. The contribution to Φi(λ)\Phi_i(\lambda) is therefore

ν(C)eλ(m−hˉ)(pe(1−p)λδ+(1−p)e−pλδ)≤ν(C)eλ(m−hˉ)eλ2δ2/8≤ν(C)eλ(m−hˉ)eλ2/8,\nu(C)e^{\lambda(m-\bar h)}\left(pe^{(1-p)\lambda\delta}+(1-p)e^{-p\lambda\delta}\right)\leq\nu(C)e^{\lambda(m-\bar h)}e^{\lambda^2\delta^2/8}\leq\nu(C)e^{\lambda(m-\bar h)}e^{\lambda^2/8},

by Lemma 7.3 with s=λδs=\lambda\delta and by ∣δ∣≤1|\delta|\leq1 from Step 1. Summing over all classes proves the claim.

Step 3: the tail bounds. Iterating Step 2 from i=Ni=N down to i=1i=1 gives

∑U∈Sν(U)eλ(h(U)−hˉ)=ΦN(λ)≤eNλ2/8(λ∈R).(32)\sum_{U\in\mathcal{S}}\nu(U)e^{\lambda(h(U)-\bar h)}=\Phi_N(\lambda)\leq e^{N\lambda^2/8}\qquad(\lambda\in\mathbb{R}). \tag*{(32)}

Fix t>0t>0 and λ>0\lambda>0. Every term of the sum in (32) is nonnegative, and each set U∈SU\in\mathcal{S} with h(U)≥hˉ+th(U)\geq\bar h+t contributes at least ν(U)eλt\nu(U)e^{\lambda t}. Sets outside S\mathcal{S} have share zero. Hence

ν({U:h(U)≥hˉ+t})≤e−λtΦN(λ)≤exp⁡(−λt+Nλ28).\nu(\{U:h(U)\geq\bar h+t\})\leq e^{-\lambda t}\Phi_N(\lambda)\leq\exp\left(-\lambda t+\frac{N\lambda^2}{8}\right).

Choosing λ=4t/N\lambda=4t/N makes the exponent −4t2/N+2t2/N=−2t2/N-4t^2/N+2t^2/N=-2t^2/N, which proves (29). The function −h-h is also 1-Lipschitz, its weighted average is −hˉ-\bar h, and {h≤hˉ−t}={−h≥−hˉ+t}\{h\leq\bar h-t\}=\{-h\geq-\bar h+t\}; applying (29) to −h-h proves (30). When t=0t=0, both bounds state that a share is at most 1. □\square

The proof never required 0<xi<10<x_i<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/81\leq e^{\lambda^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. [1]L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71 (1911), 97–115.
  2. [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. [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. [4]X. Chao. xean. https://github.com/chaoxu/xean.
  5. [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. [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.

Paper details

vlnc:W_z8zf3aq6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

gpt-6-astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents