We construct a fixed finite bipartite graph G 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) is unbounded as H ranges over graphs without isolated vertices. For all sufficiently large m, R(G,K2570m)>21144m−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 G and H, let R(G,H) be the least integer n such that every red-blue coloring of the edges of Kn contains a red copy of G or a blue copy of H. Copies are subgraphs. Write e(H) for the number of edges of H.
Erdős, Faudree, Rousseau, and Schelp [3] call a graph GRamsey size-linear if there is a constant CG such that
R(G,H)≤CGe(H)(1)
for every finite simple graph H without isolated vertices. They asked whether the local condition
e(G[W])≤2∣W∣−3for every W⊆V(G) with ∣W∣≥2(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 G satisfying (2) such that, for every sufficiently large positive integer m,
R(G,K2570m)>21144m−1.(3)
In particular,
e(K2570m)R(G,K2570m)>24m.(4)
The graph G 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 G-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 log2 use base two. Natural logarithms are denoted by ln.
Set
τ=10043,β=50004857,w=169,σ=−log2w.(5)
The binary entropy function is
h(x)=−xlog2x−(1−x)log2(1−x),0≤x≤1,
with the endpoint values defined by continuity. We shall use
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 X with probabilities px, write
H(X)=−x∑pxlog2px.
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],
∣h(a)−h(b)∣≤h(∣a−b∣).(7)
Moreover,
h(21+u)≤1−2ln2u2(−1≤u≤1).(8)
For integers n≥1 and 0≤j≤n,
n+12nh(j/n)≤(jn)≤2nh(j/n).(9)
Proof. Couple Bernoulli variables A and B with means a and b so that P(A=B)=∣a−b∣. With D=1A=B, each of A and B is determined by the other together with D. The entropy chain rule gives H(A)≤H(B)+H(D) and the reverse inequality with A and B interchanged. This proves (2.3).
For 0<x<1,
h′′(x)=−x(1−x)ln21≤−ln24.
Integrating twice from x=1/2, where h(1/2)=1 and h′(1/2)=0, proves (2.4). Continuity supplies the endpoints.
For 0<j<n, put q=j/n. In the binomial distribution with parameters n,q, the term at j is maximal. Indeed, the ratio of the term at i+1 to the term at i is
i+1n−in−jj.(10)
which is greater than one for i<j and less than one for i≥j. The maximal term is between 1/(n+1) and 1. Substituting
(jn)qj(1−q)n−j=(jn)2−nh(q)
gives (2.5). For j=0,n, the inequalities follow directly. □
A two-parent inequality
Define
κ=21+21log2(1+w)+41log2w,θ=21+h(9/25).(11)
Lemma 2.2. Let X,Y be independent Bernoulli variables with the same mean q. Let Z be a binary random variable with arbitrary conditional law given (X,Y), and write v=EZ and
d=2P(X=Z)+P(Y=Z).
Then
H(Z∣X,Y)≤κ+σd+2h(v)−h(q).(12)
Furthermore,
κ+στ=θ<.97135<β.(13)
Proof. We first take 0<q,v<1. Put πz=P(Z=z) and
c(x,y,z)=21x=z+1y=z.
For a fixed parent pair (x,y), apply the entropy bound associated with the positive weights
tz=πzwc(x,y,z).
For any probability vector (pz) and positive weights (tz), this bound is
−z∑pzlog2pz≤log2(z∑tz)−z∑pzlog2tz.
To verify it, normalize tz to a probability vector and use lnt≤t−1 to obtain nonnegativity of relative entropy. Averaging over (X,Y) therefore gives
H(Z∣X,Y)≤σd+21h(v)+Elog2(z∑tz).(14)
Let u=2q−1, b0=1−v, and b1=v. The probabilities of parent types 00, 11, and the two mixed types together are
Apply lnz≤lnM+z/M−1 to the first two logarithms at M=M0 and the third at M=M∗. The weighted logarithmic constants sum to
21ln(1+w)+41lnw+2u2lnM∗M0.
The weighted linear terms sum to
2(1−ru)b0+(1+ru)b1−1≤1+r2u2−1≤2r2u2.
Here the first inequality is Cauchy–Schwarz and uses b02+b12=1. Also M0/M∗=(1−r2)−1/2. Combining these observations with (8) gives
(F−κ)ln2≤u2(−41−41ln(1−r2)+2r2).(15)
Since −ln(1−x)≤x/(1−x) for 0≤x<1, the expression in parentheses is at most
−41+230449+125049<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/25. Then w=a/(1−a) and τ−1/4=a/2. Consequently,
Lemma 2.3.Consider an array of L≥4 bits with mean q. Sample an ordered pair of distinct indices uniformly, and let X,Y be the sampled bits. For an arbitrary conditional law of a binary child Z given (X,Y), put v=EZ and let d be as in Lemma 2.2. Then
H(Z∣X,Y)≤κ+σd+2h(v)−h(q)+η(L),(16)
where
η(L)=L1+σ+21h(1/L).(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/L. One coupling samples both indices independently and, only when they coincide, resamples the second index uniformly from the other L−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], so it changes by at most 1/L. The disagreement cost changes by at most 1/L, and so does the child mean. The parent mean remains q. By (7), the two child entropies differ by at most h(1/L), since h is increasing on [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)
Let V0 be a set of L0 vertices. Having constructed Vi−1, let Vi be a disjoint set indexed by the unordered pairs of distinct vertices of Vi−1. Join each vertex of Vi to the two vertices indexing it. Do this for 1≤i≤t, and include exactly these edges. Denote the resulting graph by G. Write Li=∣Vi∣, so that
Li=(2Li−1).
Every Li is finite, and Li≥L0. In particular, G is fixed independently of every parameter introduced below.
Lemma 3.1.The graph G 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 W of s≥2 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.
The next elementary bounds ensure a uniform entropy margin at every layer.
Lemma 3.2.For every integer L≥L0, with M=(2L),
η(L)<δ,L+3log2(M+1)−δM<−1.(19)
Also,
2t(β−θ−2δ)>1.(20)
Proof. We have 0<σ<1. For 0<x<1, the inequality −(1−x)ln(1−x)≤x gives
h(x)≤xlog2(1/x)+ln2x.
Using log2L0<24 and 1/ln2<2 yields
η(L0)<1072+2⋅10726=10715<δ.
Both terms in (17) decrease for L≥L0, so the first bound follows. Next, M+1≤L2 and log2L≤L. Furthermore,
δM=200000L(L−1)≥49L.
Thus the second expression in (19) is at most L+6L−49L=−42L<−1. Finally, (13) gives
From now on, N tends to infinity through positive multiples of 40000. Let
UN={0,1}N,Q=2N,k=τN,p=2−βN.(21)
Then k is an even integer. The graph BN on UN joins two distinct words when their Hamming distance is at most k. Each word is retained independently with probability p to form a random set S. We shall prove that BN[S] is G-free with probability tending to one.
Counting child arrays
Consider a single transition with L parents and M=(2L) children. Fix an ordered parent array u=(u1,…,uL)∈UNL. A child array z∈UNM assigns a word to each unordered pair of parent indices.
For coordinate j, choose a child index uniformly and orient its two parents by a fair coin. Denote the parent bits by Xj,Yj and the child bit by Zj. Define
E(u,z)=N1j=1∑NH(Zj∣Xj,Yj).(22)
Lemma 4.1.For a fixed parent array u, the number of child arrays satisfying E(u,z)≤β−δ is at most
(M+1)3N2NM(β−δ).(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,M11, and let a00,a01,a11 count the child bits equal to one in these groups. The three counts have at most (M+1)3 possibilities. For a specified triple, the number of child-bit assignments is
g∈{00,01,11}∏(agMg)≤2∑gMgh(ag/Mg),
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).
Specify such a triple at every coordinate. There are at most (M+1)3N resulting profiles, and for each profile the total number of arrays is at most 2NME(u,z). Summing over the profiles with E(u,z)≤β−δ proves the lemma. □
Proof. For a transition with L parents and M children, call a child array distinct if its M words are pairwise distinct. Every particular distinct child array is contained in S with probability pM. There are QL 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)≤β−δ is at most
QL(M+1)3N2NM(β−δ)pM=2N[L+3log2(M+1)−δM]≤2−N.
This calculation counts all parent arrays, regardless of whether their words survive. Taking a union bound over the t transitions gives an event of probability at least 1−t2−N on which every distinct surviving child array at every transition has entropy greater than β−δ.
Suppose this event holds and there is an injective copy of G in BN[S]. For coordinate j, let qi,j be the proportion of ones among the images of the vertices in layer Vi, and put
Φi=N1j=1∑Nh(qi,j).
We have 0≤Φi≤1. For the transition from Vi−1 to Vi, let Ei be the quantity (22). The child images are distinct and survive, so Ei>β−δ.
Let di,j be the average of the two parent-child disagreement probabilities at coordinate j. Every parent-child edge of the copy has Hamming distance at most k. Averaging over all 2Li parent-child edges therefore gives
N1j=1∑Ndi,j≤Nk=τ.
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≤θ+2Φi−Φi−1+η(Li−1)<θ+2Φi−Φi−1+δ.
Thus
Φi−Φi−1>2(β−θ−2δ).
Summing for 1≤i≤t and using (20) yields Φt−Φ0>1, contradicting 0≤Φ0,Φt≤1. Therefore the event under consideration is G-free, which proves (24). □
The spectrum of the Hamming ball
We next control independent sets of BN. Let T be the real symmetric matrix indexed by UN with
T(x,y)=1d(x,y)≤k.
Its diagonal entries are one and its constant row sum is
Identify UN with F2N and write ∣x∣ for the Hamming weight of a word x. For b∈F2N, define
χb(x)=(−1)b⋅x.
The characters are orthogonal under summation over UN, each with squared norm Q. As T(x,y) depends only on x+y, each character is an eigenvector. Define Kj(n)(v) by
(1−z)v(1+z)n−v=j=0∑nKj(n)(v)zj.(27)
Equivalently,
Kj(n)(v)=a=0∑j(−1)a(av)(j−an−v).
Using the polynomial definition of the binomial coefficients extends Kj(n) to a polynomial in the real variable v. If ∣b∣=i, summing χb over words of a given weight shows that its eigenvalue is
λi=j=0∑kKj(N)(i).
We have λ0=D. For 1≤i≤N, coefficient extraction gives
λi=[zk]1−z(1−z)i(1+z)N−i=Kk(N−1)(i−1).(28)
Lemma 5.1. Let 1≤k≤(n+1)/2 be even. If Kk(n)(v)<0 for an integer 0≤v≤n, then
∣n−2v∣<2k(n−k+1).(29)
Proof. Put x=n−2v. Differentiating (27) and comparing coefficients gives
(j+1)Kj+1=xKj−(n−j+1)Kj−1.
Thus the monic polynomials Pj(x)=j!Kj(n)((n−x)/2) satisfy
P0=1,P1=x,Pj+1=xPj−j(n−j+1)Pj−1.(30)
The determinant recurrence identifies Pk with the characteristic polynomial of the real symmetric k×k tridiagonal matrix having zero diagonal and off-diagonal entries
j(n−j+1),1≤j≤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). Here j(n−j+1) is increasing for 0≤j≤(n+1)/2. The monic polynomial Pk is positive to the right of its largest root. Recurrence (30) also gives Pk(−x)=(−1)kPk(x). Since k is even, Pk 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≤n,
v=0∑n(vn)Kk(n)(v)2=2n(kn).(31)
Proof. On F2n, let f(x)=1∣x∣=k and define the unnormalized Fourier coefficient f(b)=∑xf(x)χb(x). If ∣b∣=v, then (27) gives f(b)=Kk(n)(v). Orthogonality gives
In the last step we use the symmetry and monotonicity of binary entropy. Since k/n→τ, this bounds the magnitude of every negative eigenvalue by
2(21+h(τ)−h(.0049)+o(1))N.
After division by the lower bound in (26), the exponent becomes
−2h(τ)+h(.0049)−1+o(1).
The estimates (2.2) give
2h(τ)+h(.0049)−1>.015225>.0152.
Taking Λ 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)
For admissible N=40000m, we have bN=2570m.
Supersaturation
Lemma 6.1.For all sufficiently large admissible N, every W⊆UN with ∣W∣≥MN contains a vertex whose degree in BN[W] is at least
4QD∣W∣.(34)
Proof. Decompose 1W=(∣W∣/Q)1+f, where f is orthogonal to the constant vector. Proposition 5.3 and ∥f∥2=∣W∣−∣W∣2/Q≤∣W∣ give
1WTT1W≥QD∣W∣2−Λ∣W∣.
Since ∣W∣/Q≥2−.015N and Λ/D≤2−.0152N, for large N the second term is at most half the first. Hence
1WTT1W≥2QD∣W∣2.
There is one diagonal entry for each vertex, so
∣W∣2e(BN[W])=∣W∣1WTT1W−∣W∣≥2QD∣W∣−1.
By (26), DMN/Q→∞. The last expression is therefore at least D∣W∣/(4Q), uniformly for ∣W∣≥MN. Some vertex has at least the average degree. □
A deterministic encoding
Fix a total order of UN to resolve ties between vertices of the same degree. Given an independent set I of BN, start with W=UN and an empty set F. While ∣W∣≥MN, take a vertex x of maximum degree in BN[W] and do the following.
If x∈/I, delete x from W.
If x∈I, add x to F and delete x and all its current neighbors from W.
Write WF for the set remaining when the procedure stops. Independence implies
I⊆F∪WF,∣WF∣<MN.(35)
Lemma 6.2. For all sufficiently large admissible N, the set WF is determined by the unordered set F. Moreover, every set F produced by the procedure has size at most
LN=⌈1+D4QlnQ⌉.(36)
The number of possible pairs (F,WF) is at most (Q+1)LN+1, and
LN=o(bN),(LN+1)ln(Q+1)=o(bN).(37)
Proof. Replay the procedure using membership in F to choose between its two deletion rules. At each stage of the original run, the selected vertex belongs to I exactly when it belongs to F. Indeed, every selected vertex of I is recorded, and all recorded vertices lie in I. An induction shows that the replay selects the same vertices and deletes the same sets. This proves the determination assertion.
Put a=D/(4Q), so 0<a≤1/4. Whenever a vertex is recorded, Lemma 6.1 shows that the current set loses at least the fraction a of its vertices. Other steps also decrease its size. If s≥1 vertices are recorded, the set immediately before the last such step has size at least MN and at most Q(1−a)s−1. Therefore
s−1≤−ln(1−a)ln(Q/MN)≤alnQ=D4QlnQ,
which gives (6.4). The number of subsets of UN of size at most LN is at most (Q+1)LN+1. Each such recorded set determines at most one pair (F,WF).
Finally, (5.2) yields
LN=O(N22(1−h(τ))N).
As 1−h(τ)<.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 S with retention probability p=2−βN,
P(α(BN[S])≥bN)=o(1).(38)
Proof. Every WF in Lemma 6.2 is a fixed subset of the ambient cube. Let XF=∣WF∩S∣. Independence of the retention variables gives the exact exponential moment
E2XF=(1+p)∣WF∣≤exp(pMN).(39)
The parameters satisfy
pMN≤2(.985−β)N+1=2.0136N+1=o(bN).
For large N, (37) gives LN≤bN/2, and the preceding bound gives pMN≤(ln2)bN/4. Markov’s inequality applied to (39) then yields
If there is an independent set I⊆S of size at least bN, its encoding satisfies (35). Hence XF≥bN−∣F∣≥bN−LN. Taking the union bound over all possible pairs (F,WF) gives
Proof of Theorem 1.1. Lemma 3.1 gives the required structural properties of the fixed graph G. It remains to prove the Ramsey bound.
The order of the random sample has mean pQ=2(1−β)N and variance at most pQ. Chebyshev’s inequality gives
P(∣S∣<2pQ)≤pQ4=o(1).(40)
Together with Proposition 4.2 and Proposition 6.3, this shows that, for every sufficiently large admissible N, there exists a set S⊆UN satisfying all three properties
∣S∣≥212(1−β)N,G⊆BN[S],α(BN[S])<bN.(41)
Indeed, the sum of the three failure probabilities tends to zero.
Color each edge of the complete graph on S red if its endpoints are adjacent in BN, and blue otherwise. The second property in (41) excludes a red G. A blue clique is an independent set in BN[S], so the third property excludes a blue KbN. By the definition of the Ramsey number,
Division proves (4). The cliques have no isolated vertices. Their ratios tend to infinity while G 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≤2, set
s(y)=2j=0∑152j+11(y+1y−1)2j+1,ρ=44⋅3333.
The expansion lny=2artanh((y−1)/(y+1)) has nonnegative terms. Since (y−1)/(y+1)≤1/3, its omitted tail satisfies
0≤lny−s(y)≤33(1−1/9)2(1/3)33=ρ<10−16.
Thus
s(y)≤lny≤s(y)+ρ.(42)
Let ℓ=s(2). For a rational x=2ey∈(0,1) with 1≤y≤2 and e<0, define
Lx=s(y)+e(ℓ+ρ),Ux=s(y)+ρ+eℓ.
Equation (A.1) implies Lx≤lnx≤Ux. Define the rational numbers
Ax=−xUx−(1−x)U1−x,Bx=−xLx−(1−x)L1−x.
For the three arguments below, Ax>0, and therefore
Substitution in the finite rational sums gives, in all three rows,
Ax−ax(ℓ+ρ)>1071,bxℓ−Bx>1071.(44)
These inequalities involve rational numbers alone and follow by clearing their positive denominators. They imply Ax>0 and, together with (A.2), prove ax<h(x)<bx. This is exactly (6).
For completeness, the other scalar estimates used in the proof follow from
230449+125049<41,(100004951)2>1000043⋅57,
and the direct consequences
2h(.43)+h(.0049)−1>.015225,1−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]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]T. F. Bloom, Erdős problems, Problem 566, https://www.erdosproblems.com/566, accessed November 11, 2026.
[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]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