betaFeedback

WorksMathematics

A locally sparse graph with superlinear Ramsey growth

Abstract

We construct a fixed finite bipartite graph GG such that every set of at least two vertices spans at most twice its cardinality minus three edges, while the ratio R(G,H)/e(H)R(G,H)/e(H) is unbounded as HH ranges over graphs without isolated vertices. For all sufficiently large mm, R(G,K2570m)>21144m−1R(G,K_{2^{570m}})>2^{1144m-1}. This gives a negative answer to Erdős problem 566. The construction uses a layered two-parent graph and a random subset of a Hamming cube. A conditional-entropy inequality excludes the fixed graph. A bound on the negative Krawtchouk spectrum and an independent-set encoding exclude large independent sets.

Introduction

For finite simple graphs GG and HH, let R(G,H)R(G,H) be the least integer nn such that every red-blue coloring of the edges of KnK_n contains a red copy of GG or a blue copy of HH. Copies are subgraphs. Write e(H)e(H) for the number of edges of HH.

Erdős, Faudree, Rousseau, and Schelp [3] call a graph GG Ramsey size-linear if there is a constant CGC_G such that

R(G,H)≤CGe(H)(1)R(G,H) \le C_G e(H) \tag*{(1)}

for every finite simple graph HH without isolated vertices. They asked whether the local condition

e(G[W])≤2∣W∣−3for every W⊆V(G) with ∣W∣≥2(2)e(G[W]) \le2|W| - 3 \qquad\text{for every } W \subseteq V(G) \text{ with } |W| \ge2 \tag*{(2)}

implies (1). This question is recorded as Erdős problem 566 [2]. The formulation using all subgraphs is equivalent to (2), because each subgraph is contained in the induced subgraph on its vertex set.

Theorem 1.1. There is a fixed finite bipartite, 2-degenerate graph GG satisfying (2) such that, for every sufficiently large positive integer mm,

R(G,K2570m)>21144m−1.(3)R(G,K_{2570m}) > 2^{1144m-1}. \tag*{(3)}

In particular,

R(G,K2570m)e(K2570m)>24m.(4)\frac{R(G,K_{2570m})}{e(K_{2570m})} > 2^{4m}. \tag*{(4)}

The graph GG has finitely many layers. Each vertex after the first layer represents a pair of vertices in the preceding layer and is joined to those two vertices. The layered construction, the entropy-potential approach, and the use of profiles to count child arrays originate in Chapter 10 of OpenAI [4]. We use a different entropy parameter and apply the construction inside a single randomly sampled cube. The independent-set encoding used later is the Kleitman–Winston method, for which [1 Section 3] gives an account. The specific estimates required here are proved below. We prove that one random vertex set simultaneously supports a GG-free short-distance graph and has small independence number. Coloring its complement blue then yields (1.3).

Entropy estimates

All entropies and logarithms denoted by log⁡2\log_2 use base two. Natural logarithms are denoted by ln⁡\ln.

Set

τ=43100,β=48575000,w=916,σ=−log⁡2w.(5)\tau= \frac{43}{100}, \qquad\beta= \frac{4857}{5000}, \qquad w = \frac{9}{16}, \qquad\sigma= -\log_2 w. \tag*{(5)}

The binary entropy function is

h(x)=−xlog⁡2x−(1−x)log⁡2(1−x),0≤x≤1,h(x) = -x\log_2 x - (1-x)\log_2(1-x), \qquad0 \le x \le1,

with the endpoint values defined by continuity. We shall use

.94268<h(.36)<.94270,.98581<h(.43)<.98582,.04464<h(.0049)<.04465.(6)\begin{aligned} .94268 &< h(.36) < .94270,\\ .98581 &< h(.43) < .98582,\\ .04464 &< h(.0049) < .04465. \tag*{(6)} \end{aligned}

These are strict rational bounds. Appendix A proves them from a logarithmic series with an explicit remainder.

Elementary entropy facts

For a finite random variable XX with probabilities pxp_x, write

H(X)=−∑xpxlog⁡2px.H(X) = -\sum_x p_x \log_2 p_x.

Conditional entropy is the average of the entropies of the conditional laws. The following elementary estimates also fix the conventions used at zero probabilities.

Lemma 2.1. For a,b∈[0,1]a,b \in[0,1],

∣h(a)−h(b)∣≤h(∣a−b∣).(7)|h(a)-h(b)| \le h(|a-b|). \tag*{(7)}

Moreover,

h(1+u2)≤1−u22ln⁡2(−1≤u≤1).(8)h\left(\frac{1+u}{2}\right) \le1-\frac{u^2}{2\ln2} \qquad(-1 \le u \le1). \tag*{(8)}

For integers n≥1n \ge1 and 0≤j≤n0 \le j \le n,

2nh(j/n)n+1≤(nj)≤2nh(j/n).(9)\frac{2^{n h(j/n)}}{n+1} \le\binom{n}{j} \le2^{n h(j/n)}. \tag*{(9)}

Proof. Couple Bernoulli variables AA and BB with means aa and bb so that P(A≠B)=∣a−b∣\mathbb{P}(A \ne B) = |a-b|. With D=1A≠BD = \mathbf{1}_{A\ne B}, each of AA and BB is determined by the other together with DD. The entropy chain rule gives H(A)≤H(B)+H(D)H(A) \le H(B) + H(D) and the reverse inequality with AA and BB interchanged. This proves (2.3).

For 0<x<10 < x < 1,

h′′(x)=−1x(1−x)ln⁡2≤−4ln⁡2.h''(x) = -\frac{1}{x(1-x)\ln2} \le-\frac{4}{\ln2}.

Integrating twice from x=1/2x = 1/2, where h(1/2)=1h(1/2) = 1 and h′(1/2)=0h'(1/2) = 0, proves (2.4). Continuity supplies the endpoints.

For 0<j<n0 < j < n, put q=j/nq = j/n. In the binomial distribution with parameters n,qn,q, the term at jj is maximal. Indeed, the ratio of the term at i+1i+1 to the term at ii is

n−ii+1jn−j.(10)\frac{n-i}{i+1}\frac{j}{n-j}. \tag*{(10)}

which is greater than one for i<ji<j and less than one for i≥ji\ge j. The maximal term is between 1/(n+1)1/(n+1) and 11. Substituting

(nj)qj(1−q)n−j=(nj)2−nh(q)\binom{n}{j}q^j(1-q)^{n-j}=\binom{n}{j}2^{-nh(q)}

gives (2.5). For j=0,nj=0,n, the inequalities follow directly. □\square

A two-parent inequality

Define

κ=12+12log⁡2(1+w)+14log⁡2w,θ=1+h(9/25)2.(11)\kappa=\frac{1}{2}+\frac{1}{2}\log_2(1+w)+\frac{1}{4}\log_2 w,\qquad\theta=\frac{1+h(9/25)}{2}. \tag*{(11)}

Lemma 2.2. Let X,YX,Y be independent Bernoulli variables with the same mean qq. Let ZZ be a binary random variable with arbitrary conditional law given (X,Y)(X,Y), and write v=EZv=\mathbb{E}Z and

d=P(X≠Z)+P(Y≠Z)2.d=\frac{\mathbb{P}(X\ne Z)+\mathbb{P}(Y\ne Z)}{2}.

Then

H(Z∣X,Y)≤κ+σd+h(v)−h(q)2.(12)H(Z\mid X,Y)\le\kappa+\sigma d+\frac{h(v)-h(q)}{2}. \tag*{(12)}

Furthermore,

κ+στ=θ<.97135<β.(13)\kappa+\sigma\tau=\theta<.97135<\beta. \tag*{(13)}

Proof. We first take 0<q,v<10<q,v<1. Put πz=P(Z=z)\pi_z=\mathbb{P}(Z=z) and

c(x,y,z)=1x≠z+1y≠z2.c(x,y,z)=\frac{\mathbf{1}_{x\ne z}+\mathbf{1}_{y\ne z}}{2}.

For a fixed parent pair (x,y)(x,y), apply the entropy bound associated with the positive weights

tz=πz wc(x,y,z).t_z=\sqrt{\pi_z}\,w^{c(x,y,z)}.

For any probability vector (pz)(p_z) and positive weights (tz)(t_z), this bound is

−∑zpzlog⁡2pz≤log⁡2(∑ztz)−∑zpzlog⁡2tz.-\sum_z p_z\log_2p_z\le\log_2\left(\sum_z t_z\right)-\sum_z p_z\log_2t_z.

To verify it, normalize tzt_z to a probability vector and use ln⁡t≤t−1\ln t\le t-1 to obtain nonnegativity of relative entropy. Averaging over (X,Y)(X,Y) therefore gives

H(Z∣X,Y)≤σd+12h(v)+Elog⁡2(∑ztz).(14)H(Z\mid X,Y)\le\sigma d+\frac{1}{2}h(v)+\mathbb{E}\log_2\left(\sum_z t_z\right). \tag*{(14)}

Let u=2q−1u=2q-1, b0=1−vb_0=\sqrt{1-v}, and b1=vb_1=\sqrt{v}. The probabilities of parent types 00, 11, and the two mixed types together are

a0=(1−u)24,a1=(1+u)24,a∗=1−u22.a_0=\frac{(1-u)^2}{4},\qquad a_1=\frac{(1+u)^2}{4},\qquad a_*=\frac{1-u^2}{2}.

It suffices by (2.9) to show that

F=12h(q)+a0log⁡2(b0+wb1)+a1log⁡2(wb0+b1)+ a∗log⁡2(w(b0+b1))≤κ.F=\frac{1}{2}h(q)+a_0\log_2(b_0+wb_1)+a_1\log_2(wb_0+b_1) +\ a_*\log_2\left(\sqrt{w}(b_0+b_1)\right)\le\kappa.

Set

M0=1+w2,M∗=2w,r=1−w1+w=725.M_0=\frac{1+w}{\sqrt{2}},\qquad M_*=\sqrt{2w},\qquad r=\frac{1-w}{1+w}=\frac{7}{25}.

Apply ln⁡z≤ln⁡M+z/M−1\ln z \le\ln M + z/M - 1 to the first two logarithms at M=M0M=M_0 and the third at M=M∗M=M_*. The weighted logarithmic constants sum to

12ln⁡(1+w)+14ln⁡w+u22ln⁡M0M∗.\frac{1}{2}\ln(1+w)+\frac{1}{4}\ln w+\frac{u^2}{2}\ln\frac{M_0}{M_*}.

The weighted linear terms sum to

(1−ru)b0+(1+ru)b12−1≤1+r2u2−1≤r2u22.\frac{(1-ru)b_0+(1+ru)b_1}{\sqrt{2}}-1 \le\sqrt{1+r^2u^2}-1 \le\frac{r^2u^2}{2}.

Here the first inequality is Cauchy–Schwarz and uses b02+b12=1b_0^2+b_1^2=1. Also M0/M∗=(1−r2)−1/2M_0/M_*=(1-r^2)^{-1/2}. Combining these observations with (8) gives

(F−κ)ln⁡2≤u2(−14−14ln⁡(1−r2)+r22).(15)(F-\kappa)\ln2 \le u^2\left(-\frac{1}{4}-\frac{1}{4}\ln(1-r^2)+\frac{r^2}{2}\right). \tag*{(15)}

Since −ln⁡(1−x)≤x/(1−x)-\ln(1-x)\le x/(1-x) for 0≤x<10\le x<1, the expression in parentheses is at most

−14+492304+491250<0.-\frac{1}{4}+\frac{49}{2304}+\frac{49}{1250}<0.

This proves (12) in the interior. For the boundary cases, approximate the parent mean by interior means and add an arbitrarily small independent fair-bit noise to the child. Conditional entropy and all terms in (12) are continuous in the resulting finite joint laws, so the inequality passes to the limit.

Finally, put a=9/25a=9/25. Then w=a/(1−a)w=a/(1-a) and τ−1/4=a/2\tau-1/4=a/2. Consequently,

κ+στ=12+12(log⁡2(1+w)−alog⁡2w)=1+h(a)2.\kappa+\sigma\tau=\frac{1}{2}+\frac{1}{2}\left(\log_2(1+w)-a\log_2 w\right)=\frac{1+h(a)}{2}.

The first line of (6) proves (13).

Sampling parents without replacement

Lemma 2.3. Consider an array of L≥4L\ge4 bits with mean qq. Sample an ordered pair of distinct indices uniformly, and let X,YX,Y be the sampled bits. For an arbitrary conditional law of a binary child ZZ given (X,Y)(X,Y), put v=EZv=\mathbb{E}Z and let dd be as in Lemma 2.2. Then

H(Z∣X,Y)≤κ+σd+h(v)−h(q)2+η(L),(16)H(Z\mid X,Y)\le\kappa+\sigma d+\frac{h(v)-h(q)}{2}+\eta(L), \tag*{(16)}

where

η(L)=1+σL+12h(1/L).(17)\eta(L)=\frac{1+\sigma}{L}+\frac{1}{2}h(1/L). \tag*{(17)}

Proof. Compare the parent law with the law obtained by sampling two indices independently with replacement. These laws have total variation distance at most 1/L1/L. One coupling samples both indices independently and, only when they coincide, resamples the second index uniformly from the other L−1L-1 choices. The resulting distinct pair is uniform.

Use the same child kernel under the two parent laws, assigning it arbitrarily at parent types of zero mass. Conditional entropy is the expectation of a function in [0,1][0,1], so it changes by at most 1/L1/L. The disagreement cost changes by at most 1/L1/L, and so does the child mean. The parent mean remains qq. By (7), the two child entropies differ by at most h(1/L)h(1/L), since hh is increasing on [0,1/2][0,1/2]. Applying Lemma 2.2 to the with-replacement law gives (16).

A fixed locally sparse graph

Fix

L0=107,δ=10−5,t=20000.(18)L_0 = 10^7,\qquad\delta= 10^{-5},\qquad t = 20000. \tag*{(18)}

Let V0V_0 be a set of L0L_0 vertices. Having constructed Vi−1V_{i-1}, let ViV_i be a disjoint set indexed by the unordered pairs of distinct vertices of Vi−1V_{i-1}. Join each vertex of ViV_i to the two vertices indexing it. Do this for 1≤i≤t1 \le i \le t, and include exactly these edges. Denote the resulting graph by GG. Write Li=∣Vi∣L_i = |V_i|, so that

Li=(Li−12).L_i = \binom{L_{i-1}}{2}.

Every LiL_i is finite, and Li≥L0L_i \ge L_0. In particular, GG is fixed independently of every parameter introduced below.

Lemma 3.1. The graph GG is bipartite and 2-degenerate, and satisfies (2).

Proof. Even and odd layers give a bipartition. Order the vertices by increasing layer, with any order inside a layer. Every vertex has at most two neighbors earlier in this order, which proves 2-degeneracy. Restrict the order to a set WW of s≥2s \ge2 vertices. Its first vertex has no earlier neighbor, its second has at most one, and each remaining vertex has at most two. Counting edges by their later endpoint gives

e(G[W])≤0+1+2(s−2)=2s−3.e(G[W]) \le0 + 1 + 2(s - 2) = 2s - 3.

The next elementary bounds ensure a uniform entropy margin at every layer.

Lemma 3.2. For every integer L≥L0L \ge L_0, with M=(L2)M = \binom{L}{2},

η(L)<δ,L+3log⁡2(M+1)−δM<−1.(19)\eta(L) < \delta,\qquad L + 3\log_2(M + 1) - \delta M < -1. \tag*{(19)}

Also,

2t(β−θ−2δ)>1.(20)2t(\beta- \theta- 2\delta) > 1. \tag*{(20)}

Proof. We have 0<σ<10 < \sigma< 1. For 0<x<10 < x < 1, the inequality −(1−x)ln⁡(1−x)≤x-(1 - x)\ln(1 - x) \le x gives

h(x)≤xlog⁡2(1/x)+xln⁡2.h(x) \le x\log_2(1/x) + \frac{x}{\ln2}.

Using log⁡2L0<24\log_2 L_0 < 24 and 1/ln⁡2<21/\ln2 < 2 yields

η(L0)<2107+262⋅107=15107<δ.\eta(L_0) < \frac{2}{10^7} + \frac{26}{2\cdot10^7} = \frac{15}{10^7} < \delta.

Both terms in (17) decrease for L≥L0L \ge L_0, so the first bound follows. Next, M+1≤L2M + 1 \le L^2 and log⁡2L≤L\log_2 L \le L. Furthermore,

δM=L(L−1)200000≥49L.\delta M = \frac{L(L - 1)}{200000} \ge49L.

Thus the second expression in (19) is at most L+6L−49L=−42L<−1L + 6L - 49L = -42L < -1. Finally, (13) gives

β−θ−2δ>.9714−.97135−.00002=.00003.\beta- \theta- 2\delta> .9714 - .97135 - .00002 = .00003.

Multiplying by 2t=400002t = 40000 proves (20).

Excluding the fixed graph in a sampled cube

From now on, NN tends to infinity through positive multiples of 40000. Let

UN={0,1}N,Q=2N,k=τN,p=2−βN.(21)U_N = \{0,1\}^N,\qquad Q = 2^N,\qquad k = \tau N,\qquad p = 2^{-\beta N}. \tag*{(21)}

Then kk is an even integer. The graph BNB_N on UNU_N joins two distinct words when their Hamming distance is at most kk. Each word is retained independently with probability pp to form a random set SS. We shall prove that BN[S]B_N[S] is GG-free with probability tending to one.

Counting child arrays

Consider a single transition with LL parents and M=(L2)M = \binom{L}{2} children. Fix an ordered parent array u=(u1,…,uL)∈UNLu = (u_1,\ldots,u_L) \in U_N^L. A child array z∈UNMz \in U_N^M assigns a word to each unordered pair of parent indices.

For coordinate jj, choose a child index uniformly and orient its two parents by a fair coin. Denote the parent bits by Xj,YjX_j,Y_j and the child bit by ZjZ_j. Define

E(u,z)=1N∑j=1NH(Zj∣Xj,Yj).(22)E(u,z) = \frac{1}{N}\sum_{j=1}^{N} H(Z_j\mid X_j,Y_j). \tag*{(22)}

Lemma 4.1. For a fixed parent array uu, the number of child arrays satisfying E(u,z)≤β−δE(u,z) \le\beta-\delta is at most

(M+1)3N2NM(β−δ).(23)(M+1)^{3N}2^{NM(\beta-\delta)}. \tag*{(23)}

Proof. At each coordinate, split the child indices into the three groups corresponding to unordered parent types 00, 01, and 11. Let their sizes be M00,M01,M11M_{00},M_{01},M_{11}, and let a00,a01,a11a_{00},a_{01},a_{11} count the child bits equal to one in these groups. The three counts have at most (M+1)3(M+1)^3 possibilities. For a specified triple, the number of child-bit assignments is

∏g∈{00,01,11}(Mgag)≤2∑gMgh(ag/Mg),\prod_{g\in\{00,01,11\}}\binom{M_g}{a_g} \le2^{\sum_g M_g h(a_g/M_g)},

by (9), with an empty group contributing zero to the exponent. The fair orientation of a mixed parent pair gives the same conditional child distribution for parent types 01 and 10. Hence the exponent is exactly MH(Zj∣Xj,Yj)M H(Z_j\mid X_j,Y_j).

Specify such a triple at every coordinate. There are at most (M+1)3N(M+1)^{3N} resulting profiles, and for each profile the total number of arrays is at most 2NME(u,z)2^{NME(u,z)}. Summing over the profiles with E(u,z)≤β−δE(u,z)\le\beta-\delta proves the lemma. □

The entropy potential across layers

Proposition 4.2. For the fixed graph GG of § 3,

P(G⊆BN[S])≤t2−N.(24)\mathbb{P}(G\subseteq B_N[S])\le t2^{-N}. \tag*{(24)}

Proof. For a transition with LL parents and MM children, call a child array distinct if its MM words are pairwise distinct. Every particular distinct child array is contained in SS with probability pMp^M. There are QLQ^L possible parent arrays. Lemmas 4.1 and 3.2, followed by the union bound, show that the probability of a parent array and a distinct surviving child array with E(u,z)≤β−δE(u,z)\le\beta-\delta is at most

QL(M+1)3N2NM(β−δ)pM=2N[L+3log⁡2(M+1)−δM]≤2−N.Q^L(M+1)^{3N}2^{NM(\beta-\delta)}p^M =2^{N[L+3\log_2(M+1)-\delta M]} \le2^{-N}.

This calculation counts all parent arrays, regardless of whether their words survive. Taking a union bound over the tt transitions gives an event of probability at least 1−t2−N1-t2^{-N} on which every distinct surviving child array at every transition has entropy greater than β−δ\beta-\delta.

Suppose this event holds and there is an injective copy of GG in BN[S]B_N[S]. For coordinate jj, let qi,jq_{i,j} be the proportion of ones among the images of the vertices in layer ViV_i, and put

Φi=1N∑j=1Nh(qi,j).\Phi_i = \frac{1}{N}\sum_{j=1}^{N} h(q_{i,j}).

We have 0≤Φi≤10 \le\Phi_i \le1. For the transition from Vi−1V_{i-1} to ViV_i, let EiE_i be the quantity (22). The child images are distinct and survive, so Ei>β−δE_i > \beta- \delta.

Let di,jd_{i,j} be the average of the two parent-child disagreement probabilities at coordinate jj. Every parent-child edge of the copy has Hamming distance at most kk. Averaging over all 2Li2L_i parent-child edges therefore gives

1N∑j=1Ndi,j≤kN=τ.\frac{1}{N}\sum_{j=1}^{N} d_{i,j} \le\frac{k}{N} = \tau.

At each coordinate the oriented parent pair is a uniformly sampled pair of distinct indices from the parent layer. Apply Lemma 2.3 and average over coordinates. By (13),

Ei≤θ+Φi−Φi−12+η(Li−1)<θ+Φi−Φi−12+δ.E_i \le\theta+ \frac{\Phi_i-\Phi_{i-1}}{2}+\eta(L_{i-1}) < \theta+ \frac{\Phi_i-\Phi_{i-1}}{2}+\delta.

Thus

Φi−Φi−1>2(β−θ−2δ).\Phi_i-\Phi_{i-1} > 2(\beta-\theta-2\delta).

Summing for 1≤i≤t1 \le i \le t and using (20) yields Φt−Φ0>1\Phi_t-\Phi_0>1, contradicting 0≤Φ0,Φt≤10 \le\Phi_0,\Phi_t \le1. Therefore the event under consideration is GG-free, which proves (24). □

The spectrum of the Hamming ball

We next control independent sets of BNB_N. Let TT be the real symmetric matrix indexed by UNU_N with

T(x,y)=1d(x,y)≤k.T(x,y)=\mathbf{1}_{d(x,y)\le k}.

Its diagonal entries are one and its constant row sum is

D=∑j=0k(Nj).(25)D=\sum_{j=0}^{k}\binom{N}{j}. \tag*{(25)}

By (9) and the monotonicity of hh on [0,1/2][0,1/2],

2Nh(τ)N+1≤D≤(N+1)2Nh(τ).(26)\frac{2^{Nh(\tau)}}{N+1}\le D\le(N+1)2^{Nh(\tau)}. \tag*{(26)}

In particular D=2(h(τ)+o(1))ND=2^{(h(\tau)+o(1))N}.

Characters and Krawtchouk polynomials

Identify UNU_N with F2N\mathbb{F}_2^N and write ∣x∣|x| for the Hamming weight of a word xx. For b∈F2Nb\in\mathbb{F}_2^N, define

χb(x)=(−1)b⋅x.\chi_b(x)=(-1)^{b\cdot x}.

The characters are orthogonal under summation over UNU_N, each with squared norm QQ. As T(x,y)T(x,y) depends only on x+yx+y, each character is an eigenvector. Define Kj(n)(v)K_j^{(n)}(v) by

(1−z)v(1+z)n−v=∑j=0nKj(n)(v)zj.(27)(1-z)^v(1+z)^{n-v}=\sum_{j=0}^{n}K_j^{(n)}(v)z^j. \tag*{(27)}

Equivalently,

Kj(n)(v)=∑a=0j(−1)a(va)(n−vj−a).K_j^{(n)}(v)=\sum_{a=0}^{j}(-1)^a\binom{v}{a}\binom{n-v}{j-a}.

Using the polynomial definition of the binomial coefficients extends Kj(n)K_j^{(n)} to a polynomial in the real variable vv. If ∣b∣=i|b|=i, summing χb\chi_b over words of a given weight shows that its eigenvalue is

λi=∑j=0kKj(N)(i).\lambda_i=\sum_{j=0}^{k}K_j^{(N)}(i).

We have λ0=D\lambda_0=D. For 1≤i≤N1\le i\le N, coefficient extraction gives

λi=[zk](1−z)i(1+z)N−i1−z=Kk(N−1)(i−1).(28)\lambda_i=[z^k]\frac{(1-z)^i(1+z)^{N-i}}{1-z}=K_k^{(N-1)}(i-1). \tag*{(28)}

Lemma 5.1. Let 1≤k≤(n+1)/21\le k\le(n+1)/2 be even. If Kk(n)(v)<0K_k^{(n)}(v)<0 for an integer 0≤v≤n0\le v\le n, then

∣n−2v∣<2k(n−k+1).(29)|n-2v|<2\sqrt{k(n-k+1)}. \tag*{(29)}

Proof. Put x=n−2vx=n-2v. Differentiating (27) and comparing coefficients gives

(j+1)Kj+1=xKj−(n−j+1)Kj−1.(j+1)K_{j+1}=xK_j-(n-j+1)K_{j-1}.

Thus the monic polynomials Pj(x)=j!Kj(n)((n−x)/2)P_j(x)=j!K_j^{(n)}((n-x)/2) satisfy

P0=1,P1=x,Pj+1=xPj−j(n−j+1)Pj−1.(30)P_0=1,\qquad P_1=x,\qquad P_{j+1}=xP_j-j(n-j+1)P_{j-1}. \tag*{(30)}

The determinant recurrence identifies PkP_k with the characteristic polynomial of the real symmetric k×kk\times k tridiagonal matrix having zero diagonal and off-diagonal entries

j(n−j+1),1≤j≤k−1.\sqrt{j(n-j+1)},\qquad1\le j\le k-1.

All roots are real. Each eigenvalue has absolute value at most the maximal absolute row sum, which is at most 2k(n−k+1)2\sqrt{k(n-k+1)}. Here j(n−j+1)j(n-j+1) is increasing for 0≤j≤(n+1)/20\le j\le(n+1)/2. The monic polynomial PkP_k is positive to the right of its largest root. Recurrence (30) also gives Pk(−x)=(−1)kPk(x)P_k(-x)=(-1)^kP_k(x). Since kk is even, PkP_k is positive on both exterior intervals beyond the indicated root bound, and is nonnegative at the endpoints. A negative value must satisfy (29).

Lemma 5.2. For 0≤k≤n0\le k\le n,

∑v=0n(nv)Kk(n)(v)2=2n(nk).(31)\sum_{v=0}^{n}\binom{n}{v}K_k^{(n)}(v)^2=2^n\binom{n}{k}. \tag*{(31)}

Proof. On F2n\mathbb{F}_2^n, let f(x)=1∣x∣=kf(x)=1_{|x|=k} and define the unnormalized Fourier coefficient f^(b)=∑xf(x)χb(x)\widehat{f}(b)=\sum_x f(x)\chi_b(x). If ∣b∣=v|b|=v, then (27) gives f^(b)=Kk(n)(v)\widehat{f}(b)=K_k^{(n)}(v). Orthogonality gives

∑bf^(b)2=∑x,yf(x)f(y)∑bχb(x+y)=2n∑xf(x)2=2n(nk).\sum_b\widehat{f}(b)^2=\sum_{x,y}f(x)f(y)\sum_b\chi_b(x+y)=2^n\sum_xf(x)^2=2^n\binom{n}{k}.

Grouping bb by its weight proves (31).

A bound on the negative eigenvalues

Proposition 5.3. For all sufficiently large admissible NN, every eigenvalue of TT is at least −Λ-\Lambda, where

ΛD≤2−0.0152N.(32)\frac{\Lambda}{D}\le2^{-0.0152N}. \tag*{(32)}

Proof. Set n=N−1n=N-1. Since k=τNk=\tau N is even and k≤(n+1)/2k\le(n+1)/2, Lemma 5.1 applies. If the eigenvalue in (28) is negative, with v=i−1v=i-1, then

12−k(n−k+1)n<vn<12+k(n−k+1)n.\frac{1}{2}-\frac{\sqrt{k(n-k+1)}}{n}<\frac{v}{n}<\frac{1}{2}+\frac{\sqrt{k(n-k+1)}}{n}.

Now

k(n−k+1)N−1=NN−1τ(1−τ).\frac{\sqrt{k(n-k+1)}}{N-1}=\frac{N}{N-1}\sqrt{\tau(1-\tau)}.

The exact inequality .49512=.24512401>.2451=τ(1−τ).4951^2=.24512401>.2451=\tau(1-\tau) implies

12−τ(1−τ)>.0049.\frac{1}{2}-\sqrt{\tau(1-\tau)}>.0049.

Consequently every negative eigenvalue has v/n∈[.0049,.9951]v/n\in[.0049,.9951] for all sufficiently large NN. By Lemmas 2.1 and 5.2,

∣Kk(n)(v)∣2≤2n(nk)(nv)≤(n+1)2n[1+h(k/n)−h(v/n)]≤(n+1)2n[1+h(k/n)−h(.0049)].\begin{aligned} |K_k^{(n)}(v)|^2\leq\frac{2^n\binom{n}{k}}{\binom{n}{v}} \\ &\leq(n+1)2^{n[1+h(k/n)-h(v/n)]} \\ &\leq(n+1)2^{n[1+h(k/n)-h(.0049)]}. \end{aligned}

In the last step we use the symmetry and monotonicity of binary entropy. Since k/n→τk/n\to\tau, this bounds the magnitude of every negative eigenvalue by

2(1+h(τ)−h(.0049)2+o(1))N.2^{\left(\frac{1+h(\tau)-h(.0049)}{2}+o(1)\right)N}.

After division by the lower bound in (26), the exponent becomes

−h(τ)+h(.0049)−12+o(1).-\frac{h(\tau)+h(.0049)-1}{2}+o(1).

The estimates (2.2) give

h(τ)+h(.0049)−12>.015225>.0152.\frac{h(\tau)+h(.0049)-1}{2}>.015225>.0152.

Taking Λ\Lambda to be the larger of zero and the magnitude of the most negative eigenvalue proves (5.8). □

Independent-set containers and random thinning

Put

MN=⌈2.985N⌉,bN=2.01425N.(33)M_N=\left\lceil2^{.985N}\right\rceil,\qquad b_N=2^{.01425N}. \tag*{(33)}

For admissible N=40000mN=40000m, we have bN=2570mb_N=2^{570m}.

Supersaturation

Lemma 6.1. For all sufficiently large admissible NN, every W⊆UNW\subseteq U_N with ∣W∣≥MN|W|\geq M_N contains a vertex whose degree in BN[W]B_N[W] is at least

D∣W∣4Q.(34)\frac{D|W|}{4Q}. \tag*{(34)}

Proof. Decompose 1W=(∣W∣/Q)1+f\mathbf{1}_W=(|W|/Q)\mathbf{1}+f, where ff is orthogonal to the constant vector. Proposition 5.3 and ∥f∥2=∣W∣−∣W∣2/Q≤∣W∣\|f\|^2=|W|-|W|^2/Q\leq|W| give

1WTT1W≥D∣W∣2Q−Λ∣W∣.\mathbf{1}_W^{\mathsf T}T\mathbf{1}_W\geq\frac{D|W|^2}{Q}-\Lambda|W|.

Since ∣W∣/Q≥2−.015N|W|/Q\geq2^{-.015N} and Λ/D≤2−.0152N\Lambda/D\leq2^{-.0152N}, for large NN the second term is at most half the first. Hence

1WTT1W≥D∣W∣22Q.\mathbf{1}_W^{\mathsf T}T\mathbf{1}_W\geq\frac{D|W|^2}{2Q}.

There is one diagonal entry for each vertex, so

2e(BN[W])∣W∣=1WTT1W−∣W∣∣W∣≥D∣W∣2Q−1.\frac{2e(B_N[W])}{|W|}=\frac{\mathbf{1}_W^{\mathsf T}T\mathbf{1}_W-|W|}{|W|}\geq\frac{D|W|}{2Q}-1.

By (26), DMN/Q→∞DM_N/Q \to\infty. The last expression is therefore at least D∣W∣/(4Q)D|W|/(4Q), uniformly for ∣W∣≥MN|W| \ge M_N. Some vertex has at least the average degree. □

A deterministic encoding

Fix a total order of UNU_N to resolve ties between vertices of the same degree. Given an independent set II of BNB_N, start with W=UNW = U_N and an empty set FF. While ∣W∣≥MN|W| \ge M_N, take a vertex xx of maximum degree in BN[W]B_N[W] and do the following.

  1. If x∉Ix \notin I, delete xx from WW.

  2. If x∈Ix \in I, add xx to FF and delete xx and all its current neighbors from WW.

Write WFW_F for the set remaining when the procedure stops. Independence implies

I⊆F∪WF,∣WF∣<MN.(35)I \subseteq F \cup W_F,\qquad|W_F| < M_N. \tag*{(35)}

Lemma 6.2. For all sufficiently large admissible NN, the set WFW_F is determined by the unordered set FF. Moreover, every set FF produced by the procedure has size at most

LN=⌈1+4QDln⁡Q⌉.(36)L_N = \left\lceil1 + \frac{4Q}{D}\ln Q \right\rceil. \tag*{(36)}

The number of possible pairs (F,WF)(F,W_F) is at most (Q+1)LN+1(Q+1)^{L_N+1}, and

LN=o(bN),(LN+1)ln⁡(Q+1)=o(bN).(37)L_N = o(b_N),\qquad(L_N+1)\ln(Q+1) = o(b_N). \tag*{(37)}

Proof. Replay the procedure using membership in FF to choose between its two deletion rules. At each stage of the original run, the selected vertex belongs to II exactly when it belongs to FF. Indeed, every selected vertex of II is recorded, and all recorded vertices lie in II. An induction shows that the replay selects the same vertices and deletes the same sets. This proves the determination assertion.

Put a=D/(4Q)a = D/(4Q), so 0<a≤1/40 < a \le1/4. Whenever a vertex is recorded, Lemma 6.1 shows that the current set loses at least the fraction aa of its vertices. Other steps also decrease its size. If s≥1s \ge1 vertices are recorded, the set immediately before the last such step has size at least MNM_N and at most Q(1−a)s−1Q(1-a)^{s-1}. Therefore

s−1≤ln⁡(Q/MN)−ln⁡(1−a)≤ln⁡Qa=4QDln⁡Q,s-1 \le\frac{\ln(Q/M_N)}{-\ln(1-a)} \le\frac{\ln Q}{a} = \frac{4Q}{D}\ln Q,

which gives (6.4). The number of subsets of UNU_N of size at most LNL_N is at most (Q+1)LN+1(Q+1)^{L_N+1}. Each such recorded set determines at most one pair (F,WF)(F,W_F).

Finally, (5.2) yields

LN=O(N22(1−h(τ))N).L_N = O\left(N^2 2^{(1-h(\tau))N}\right).

As 1−h(τ)<.01419<.014251-h(\tau) < .01419 < .01425, both assertions of (6.5) follow. A polynomial factor is dominated by the exponential gap between these two constants. □

Thinning the containers

Proposition 6.3. For the independently retained set SS with retention probability p=2−βNp = 2^{-\beta N},

P(α(BN[S])≥bN)=o(1).(38)\mathbb{P}\left(\alpha(B_N[S]) \ge b_N\right) = o(1). \tag*{(38)}

Proof. Every WFW_F in Lemma 6.2 is a fixed subset of the ambient cube. Let XF=∣WF∩S∣X_F = |W_F \cap S|. Independence of the retention variables gives the exact exponential moment

E2XF=(1+p)∣WF∣≤exp⁡(pMN).(39)\mathbb{E}2^{X_F} = (1+p)^{|W_F|} \le\exp(pM_N). \tag*{(39)}

The parameters satisfy

pMN≤2(.985−β)N+1=2.0136N+1=o(bN).pM_N \le2^{(.985-\beta)N+1} = 2^{.0136N+1} = o(b_N).

For large NN, (37) gives LN≤bN/2L_N \le b_N/2, and the preceding bound gives pMN≤(ln⁡2)bN/4pM_N \le(\ln2)b_N/4. Markov’s inequality applied to (39) then yields

P(XF≥bN−LN)≤exp⁡(pMN−(ln⁡2)(bN−LN))≤exp⁡(−(ln⁡2)bN/4).\mathbb{P}(X_F \ge b_N-L_N) \le\exp\bigl(pM_N-(\ln2)(b_N-L_N)\bigr) \le\exp\bigl(-(\ln2)b_N/4\bigr).

If there is an independent set I⊆SI \subseteq S of size at least bNb_N, its encoding satisfies (35). Hence XF≥bN−∣F∣≥bN−LNX_F \ge b_N-|F| \ge b_N-L_N. Taking the union bound over all possible pairs (F,WF)(F,W_F) gives

P(α(BN[S])≥bN)≤exp⁡((LN+1)ln⁡(Q+1)−ln⁡24bN)=o(1),\mathbb{P}\bigl(\alpha(B_N[S]) \ge b_N\bigr) \le\exp\left((L_N+1)\ln(Q+1)-\frac{\ln2}{4}b_N\right)=o(1),

by (37).

Completion of the Ramsey argument

Proof of Theorem 1.1. Lemma 3.1 gives the required structural properties of the fixed graph GG. It remains to prove the Ramsey bound.

The order of the random sample has mean pQ=2(1−β)NpQ=2^{(1-\beta)N} and variance at most pQpQ. Chebyshev’s inequality gives

P(∣S∣<pQ2)≤4pQ=o(1).(40)\mathbb{P}\left(\lvert S\rvert< \frac{pQ}{2}\right)\le\frac{4}{pQ}=o(1). \tag*{(40)}

Together with Proposition 4.2 and Proposition 6.3, this shows that, for every sufficiently large admissible NN, there exists a set S⊆UNS\subseteq U_N satisfying all three properties

∣S∣≥122(1−β)N,G⊈BN[S],α(BN[S])<bN.(41)\lvert S\rvert\ge\frac{1}{2}2^{(1-\beta)N},\qquad G\not\subseteq B_N[S],\qquad\alpha(B_N[S])<b_N. \tag*{(41)}

Indeed, the sum of the three failure probabilities tends to zero.

Color each edge of the complete graph on SS red if its endpoints are adjacent in BNB_N, and blue otherwise. The second property in (41) excludes a red GG. A blue clique is an independent set in BN[S]B_N[S], so the third property excludes a blue KbNK_{b_N}. By the definition of the Ramsey number,

R(G,KbN)>∣S∣≥122(1−β)N.R(G,K_{b_N})>\lvert S\rvert\ge\frac{1}{2}2^{(1-\beta)N}.

Taking N=40000mN=40000m gives

bN=2570m,(1−β)N=1144m,b_N=2^{570m},\qquad(1-\beta)N=1144m,

and proves (3). For these cliques,

e(K2570m)=2570m(2570m−1)2<21140m−1.e(K_{2^{570m}})=\frac{2^{570m}(2^{570m}-1)}{2}<2^{1140m-1}.

Division proves (4). The cliques have no isolated vertices. Their ratios tend to infinity while GG remains fixed, which disproves (1) for a graph satisfying the full local hypothesis (2).

Exact scalar inequalities

This appendix gives rational certificates for (6). For 1≤y≤21\le y\le2, set

s(y)=2∑j=01512j+1(y−1y+1)2j+1,ρ=344⋅333.s(y)=2\sum_{j=0}^{15}\frac{1}{2j+1}\left(\frac{y-1}{y+1}\right)^{2j+1},\qquad\rho=\frac{3}{44\cdot3^{33}}.

The expansion ln⁡y=2artanh⁡((y−1)/(y+1))\ln y=2\operatorname{artanh}\left((y-1)/(y+1)\right) has nonnegative terms. Since (y−1)/(y+1)≤1/3(y-1)/(y+1)\le1/3, its omitted tail satisfies

0≤ln⁡y−s(y)≤2(1/3)3333(1−1/9)=ρ<10−16.0\le\ln y-s(y)\le\frac{2(1/3)^{33}}{33(1-1/9)}=\rho<10^{-16}.

Thus

s(y)≤ln⁡y≤s(y)+ρ.(42)s(y) \le\ln y \le s(y) + \rho. \tag*{(42)}

Let ℓ=s(2)\ell= s(2). For a rational x=2ey∈(0,1)x = 2^{e}y \in(0,1) with 1≤y≤21 \le y \le2 and e<0e < 0, define

Lx=s(y)+e(ℓ+ρ),Ux=s(y)+ρ+eℓ.L_x = s(y) + e(\ell+ \rho), \qquad U_x = s(y) + \rho+ e\ell.

Equation (A.1) implies Lx≤ln⁡x≤UxL_x \le\ln x \le U_x. Define the rational numbers

Ax=−xUx−(1−x)U1−x,Bx=−xLx−(1−x)L1−x.A_x = -xU_x - (1-x)U_{1-x}, \qquad B_x = -xL_x - (1-x)L_{1-x}.

For the three arguments below, Ax>0A_x > 0, and therefore

Axℓ+ρ≤h(x)≤Bxℓ.(43)\frac{A_x}{\ell+ \rho} \le h(x) \le\frac{B_x}{\ell}. \tag*{(43)}

The required power-of-two reductions are

xeye′y′9/25−236/25−132/2543/100−243/25−157/5049/10000−8784/625−19951/5000\begin{array}{c|c|c|c|c} x & e & y & e' & y' \\ \hline 9/25 & -2 & 36/25 & -1 & 32/25 \\ 43/100 & -2 & 43/25 & -1 & 57/50 \\ 49/10000 & -8 & 784/625 & -1 & 9951/5000 \end{array}

where x=2eyx = 2^{e}y and 1−x=2e′y′1-x = 2^{e'}y'. To make the final comparisons explicit, take

xaxbx9/2594268/10000094270/10000043/10098581/10000098582/10000049/100004464/1000004465/100000.\begin{array}{c|c|c} x & a_x & b_x \\ \hline 9/25 & 94268/100000 & 94270/100000 \\ 43/100 & 98581/100000 & 98582/100000 \\ 49/10000 & 4464/100000 & 4465/100000. \end{array}

Substitution in the finite rational sums gives, in all three rows,

Ax−ax(ℓ+ρ)>1107,bxℓ−Bx>1107.(44)A_x-a_x(\ell+\rho)>\frac{1}{10^7}, \qquad b_x\ell-B_x>\frac{1}{10^7}. \tag*{(44)}

These inequalities involve rational numbers alone and follow by clearing their positive denominators. They imply Ax>0A_x > 0 and, together with (A.2), prove ax<h(x)<bxa_x < h(x) < b_x. This is exactly (6).

For completeness, the other scalar estimates used in the proof follow from

492304+491250<14,(495110000)2>43⋅5710000,\frac{49}{2304}+\frac{49}{1250}<\frac{1}{4}, \qquad\left(\frac{4951}{10000}\right)^2>\frac{43\cdot57}{10000},

and the direct consequences

h(.43)+h(.0049)−12>.015225,1−h(.43)<.01419.\frac{h(.43)+h(.0049)-1}{2}>.015225, \qquad1-h(.43)<.01419.

All decimal constants in the proof are terminating decimals and hence denote exact rational numbers.

Acknowledgment

The authors acknowledge assistance from OpenAI’s ChatGPT in developing and checking the argument and in preparing the exposition.

References

References

  1. [1]J. Balogh, A. Treglown, and A. Z. Wagner, Applications of graph containers in the Boolean lattice, Random Structures Algorithms 49 (2016), no. 4, 845–872. doi:10.1002/rsa.20666.DOI
  2. [2]T. F. Bloom, Erdős problems, Problem 566, https://www.erdosproblems.com/566, accessed November 11, 2026.
  3. [3]P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Ramsey size linear graphs, Combin. Probab. Comput. 2 (1993), no. 4, 389–399. doi:10.1017/S096354830000078X.DOI
  4. [4]OpenAI, Ten advances in mathematics and theoretical computer science, preprint, updated August 6, 2026, Chapter 10, pp. 236–248. https://cdn.openai.com/pdf/ten-proofs-oai.pdf.DOI

Paper details

vlnc:W_n4eexba7
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 10

downloads · 0

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

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents