Introduction
For finite simple graphs H H H and G G G , write H → G H \to G H → G if every red-blue coloring of E ( H ) E(H) E ( H ) contains a monochromatic subgraph isomorphic to G G G . The two-color size Ramsey number is
R ^ ( G ) = min { e ( H ) : H is a finite simple graph and H → G } . \widehat{R}(G) = \min\{e(H) : H \text{ is a finite simple graph and } H \to G\}. R ( G ) = min { e ( H ) : H is a finite simple graph and H → G } .
It was introduced by Erdős, Faudree, Rousseau and Schelp [5 ] . All copies in this paper are ordinary subgraphs, and all logarithms are natural unless their base is displayed.
In a last-minute addition to his 1982 survey, Erdős [3 p. 78] asked whether the quotient R ^ ( G ) / e ( G ) \widehat{R}(G)/e(G) R ( G ) / e ( G ) must grow faster than the edge-to-vertex ratio of G G G , uniformly over all graphs of large density. We establish this assertion.
Theorem 1.1. There exists a function f : R → R f : \mathbb{R} \to\mathbb{R} f : R → R such that
lim C → ∞ f ( C ) C = ∞ \lim_{C \to\infty} \frac{f(C)}{C} = \infty C → ∞ lim C f ( C ) = ∞ and, for every sufficiently large C C C , every finite simple graph G G G with v ( G ) > 0 v(G) > 0 v ( G ) > 0 and e ( G ) ≥ C v ( G ) e(G) \ge Cv(G) e ( G ) ≥ C v ( G ) satisfies
R ^ ( G ) > f ( C ) e ( G ) . \widehat{R}(G) > f(C)e(G). R ( G ) > f ( C ) e ( G ) .
Equivalently, for every fixed M > 0 M > 0 M > 0 there is C M C_M C M such that R ^ ( G ) > M C e ( G ) \widehat{R}(G) > MC e(G) R ( G ) > M C e ( G ) whenever C ≥ C M C \ge C_M C ≥ C M and e ( G ) ≥ C v ( G ) > 0 e(G) \ge Cv(G) > 0 e ( G ) ≥ C v ( G ) > 0 . The uniformity includes targets with arbitrarily many nonisomorphic connected components and arbitrary component multiplicities.
Complete bipartite graphs were studied by Pikhurko [10 ] and by Conlon, Fox and Wigderson [1 ] . These results give strong estimates for specified bipartite families. The earlier public working report on problem 911 [7 ] records an exact minimum-degree reduction and a biclique-based partial result. A uniform argument must also treat targets with dispersed neighborhoods and many component types. The proof below uses the entropy of these types to select a connected component whose exceptional embeddings occupy few host edges.
Public notes attributed to Charlie Karoubi [9 ] also discuss the elementary degree and vertex-cover bounds and explicitly leave the full question open. These notes and the working report are unrefereed.
Related multicolor work of DeBiasio [2 ] gives a lower bound proportional to r 2 e ( H ) r^2e(H) r 2 e ( H ) for non-star connected targets when r r r colors are used. With two colors fixed, that estimate does not supply the density-dependent gain required here. The uniformity in the target density, rather than growth in the number of colors, is essential.
Outline of the proof
Section 3 proves a uniform dictionary bound for strongly unbalanced incidence targets and reduces the remaining work to polynomially bounded maximum degree. Section 4 gives a further reduction to logarithmic density on small vertex sets. In Sections 5 and 6, a biased forest count and dense-block extraction force a class with many distinct component types. Sections 7 and 8 use this class to construct avoiding colorings in two complementary degree regimes. The final dyadic summation in Section 9 proves Theorem 1.1.
The constants are chosen for separation of scales. For fixed parameters, every use of o ( 1 ) o(1) o ( 1 ) is as the minimum-degree parameter tends to infinity. No estimate depends on the total order of the target.
Probabilistic and counting preliminaries
The order and size of a graph are denoted by v ( G ) v(G) v ( G ) and e ( G ) e(G) e ( G ) , and its minimum and maximum degrees by δ ( G ) \delta(G) δ ( G ) and Δ ( G ) \Delta(G) Δ ( G ) . All auxiliary target graphs have at least one edge. Entropy formulas use the continuous convention 0 log 0 = 0 0\log0=0 0 log 0 = 0 ; terms with a zero coefficient in t log ( A / t ) t\log(A/t) t log ( A / t ) are likewise zero. A component type is an isomorphism class of connected components. When candidate images are assigned to vertices of a fixed target, we call those target vertices roles .
For a set of host edges, its target capacity is the maximum number of its edges that can be used by a copy of the full target. Capacities are subadditive. A set of h h h host vertices meets at most Δ ( G ) h \Delta(G)h Δ ( G ) h edges of a target copy. If every target set of order h h h spans at most σ h \sigma h σ h edges, a host-edge set supported on h h h vertices has capacity at most σ h \sigma h σ h . We use these deterministic bounds when accounting for blue edges.
We use the asymmetric Lovász local lemma in the following variable form. Suppose events A i A_i A i are determined by subsets of a finite family of independent variables. Join two events when their variable sets intersect. If 0 < x i < 1 0<x_i<1 0 < x i < 1 and
Pr ( A i ) ≤ x i ∏ j ∼ i ( 1 − x j ) , \Pr(A_i)\leq x_i\prod_{j\sim i}(1-x_j), Pr ( A i ) ≤ x i j ∼ i ∏ ( 1 − x j ) ,
then there is positive probability that no A i A_i A i occurs. The original local lemma is due to Erdős and Lovász [6 ] .
Lemma 2.1 (Conditional local lemma). Under these hypotheses, if an event B B B is determined by a variable set S S S , then
Pr ( B ∣ ⋂ i A i c ) ≤ Pr ( B ) ∏ i : S ∩ S i ≠ ∅ ( 1 − x i ) − 1 . \Pr\left(B\mid\bigcap_i A_i^c\right)\leq\Pr(B)\prod_{i:S\cap S_i\ne\varnothing}(1-x_i)^{-1}. Pr ( B ∣ i ⋂ A i c ) ≤ Pr ( B ) i : S ∩ S i = ∅ ∏ ( 1 − x i ) − 1 . In particular, if every variable occurs in events of total weight at most q ≤ 1 / 2 q\leq1/2 q ≤ 1/2 , a condition on u u u variables incurs a factor at most exp ( 2 q u ) \exp(2qu) exp ( 2 q u ) .
Proof. The usual induction proving the asymmetric local lemma also gives Pr ( A i ∣ ⋂ j ∈ J A j c ) ≤ x i \Pr(A_i\mid\bigcap_{j\in J}A_j^c)\leq x_i Pr ( A i ∣ ⋂ j ∈ J A j c ) ≤ x i for any set J J J excluding i i i . The event B B B is independent of the joint family whose variable sets avoid S S S . Condition first on their avoidance. Dividing by the conditional probability of avoiding the remaining events gives the displayed product. Finally, − log ( 1 − x i ) ≤ 2 x i -\log(1-x_i)\leq2x_i − log ( 1 − x i ) ≤ 2 x i when x i ≤ 1 / 2 x_i\leq1/2 x i ≤ 1/2 , and the sum of the weights of events touching S S S is at most q u qu q u . □
Lemma 2.2 (A read bound). Let X 1 , … , X N X_1,\ldots,X_N X 1 , … , X N be indicators determined by independent variables, with each variable affecting at most r r r indicators. If μ = ∑ i E X i \mu=\sum_i\mathbb{E}X_i μ = ∑ i E X i , then
Pr ( ∑ i X i ≤ μ 2 ) ≤ exp ( − μ 8 r ) . \Pr\left(\sum_i X_i\leq\frac{\mu}{2}\right)\leq\exp\left(-\frac{\mu}{8r}\right). Pr ( i ∑ X i ≤ 2 μ ) ≤ exp ( − 8 r μ ) .
Proof. Product Hölder gives E ∏ i g i ≤ ∏ i ( E g i r ) 1 / r \mathbb{E}\prod_i g_i \le\prod_i(\mathbb{E}g_i^r)^{1/r} E ∏ i g i ≤ ∏ i ( E g i r ) 1/ r for nonnegative functions with this dependence structure. One proves it by integrating each independent variable and applying Hölder to the at most r r r factors using that variable. Apply the inequality to g i = exp ( − X i / r ) g_i=\exp(-X_i/r) g i = exp ( − X i / r ) . Markov’s inequality bounds the desired probability by
exp ( μ / ( 2 r ) ) ∏ i [ 1 − ( 1 − e − 1 ) E X i ] 1 / r ≤ exp ( − ( 1 − e − 1 − 1 / 2 ) μ r ) . \exp(\mu/(2r))\prod_i\left[1-(1-e^{-1})\mathbb{E}X_i\right]^{1/r}\le\exp\left(-\frac{(1-e^{-1}-1/2)\mu}{r}\right). exp ( μ / ( 2 r )) i ∏ [ 1 − ( 1 − e − 1 ) E X i ] 1/ r ≤ exp ( − r ( 1 − e − 1 − 1/2 ) μ ) .
Now 1 − e − 1 − 1 / 2 > 1 / 8 1-e^{-1}-1/2>1/8 1 − e − 1 − 1/2 > 1/8 . This is a standard read-r r r concentration estimate; see also [8 ] . □
We use the following form of the classical degree–cover bound; see Erdős and Faudree [4 inequality (7)] .
Lemma 2.3 (Degree and cover). If J 0 J_0 J 0 is a subgraph of a graph J J J with e ( J 0 ) > 0 e(J_0)>0 e ( J 0 ) > 0 , then
R ^ ( J ) ≥ Δ ( J ) τ ( J 0 ) 2 ≥ Δ ( J ) e ( J 0 ) 2 Δ ( J 0 ) . \widehat{R}(J)\ge\frac{\Delta(J)\tau(J_0)}{2}\ge\frac{\Delta(J)e(J_0)}{2\Delta(J_0)}. R ( J ) ≥ 2 Δ ( J ) τ ( J 0 ) ≥ 2Δ ( J 0 ) Δ ( J ) e ( J 0 ) . where τ \tau τ is the vertex-cover number.
Proof. In a host with fewer than Δ ( J ) τ ( J 0 ) / 2 \Delta(J)\tau(J_0)/2 Δ ( J ) τ ( J 0 ) /2 edges, fewer than τ ( J 0 ) \tau(J_0) τ ( J 0 ) vertices have degree at least Δ ( J ) \Delta(J) Δ ( J ) . Color all edges meeting those vertices blue and the remaining edges red. The red graph has maximum degree below Δ ( J ) \Delta(J) Δ ( J ) , and the blue graph has a vertex cover too small to contain J 0 J_0 J 0 . The second inequality follows because a vertex cover of J 0 J_0 J 0 meets at most Δ ( J 0 ) \Delta(J_0) Δ ( J 0 ) edges per vertex. □
Lemma 2.4 (Restricted-star count). Let P , k , a P,k,a P , k , a be positive integers. Let a host vertex set U U U have order k k k and span at most P k Pk P k edges. For some vertices v ∈ U v\in U v ∈ U , designate a pool of at most C v C_v C v possible neighbors, where 1 ≤ C v ≤ P 1\le C_v\le P 1 ≤ C v ≤ P . Suppose t v t_v t v selected edges are assigned to v v v from that pool, with each edge assigned at most once, and put t = ∑ v t v ≤ a t=\sum_v t_v\le a t = ∑ v t v ≤ a . For fixed pools and counts, the number of possible a a a -edge subsets is at most
( P k a − t ) ∏ v ( C v t v ) . \binom{Pk}{a-t}\prod_v\binom{C_v}{t_v}. ( a − t P k ) v ∏ ( t v C v ) . If this number is positive, its logarithm is at most
a log ( P k / a ) + 2 a − ∑ v t v log ( P / C v ) . a\log(Pk/a)+2a-\sum_v t_v\log(P/C_v). a log ( P k / a ) + 2 a − v ∑ t v log ( P / C v ) . Terms with t v = 0 t_v=0 t v = 0 contribute zero.
Proof. Choose the assigned edges separately, then the unassigned edges from the whole pool. The bound may overcount, which is harmless. The binomial estimate and ∑ v t v log ( t / t v ) ≤ t log k \sum_v t_v\log(t/t_v)\le t\log k ∑ v t v log ( t / t v ) ≤ t log k bound the assigned choices by t log ( e P k / t ) − ∑ v t v log ( P / C v ) t\log(ePk/t)-\sum_v t_v\log(P/C_v) t log ( e P k / t ) − ∑ v t v log ( P / C v ) . Combining this with the unassigned choices costs at most a log 2 \log2 log 2 beyond a log ( e P k / a ) a\log(ePk/a) a log ( e P k / a ) . □
Lemma 2.5 (Centers for a candidate list). Let D , T > 0 D,T>0 D , T > 0 , let s ≥ 2 s\ge2 s ≥ 2 be an integer, and let Y Y Y be a finite set of vertices, each of degree at most D D D in a graph. Suppose every subset of Y Y Y of order at most s s s has more than T T T common neighbors. If ∣ Y ∣ > s |Y|>s ∣ Y ∣ > s and ϑ = log ( 2 D / T ) / ( s − 1 ) < 1 \vartheta=\log(2D/T)/(s-1)<1 ϑ = log ( 2 D / T ) / ( s − 1 ) < 1 , at least T / 2 T/2 T /2 vertices are adjacent to a ( 1 − ϑ ) (1-\vartheta) ( 1 − ϑ ) fraction of Y Y Y .
Proof. Put a z = ∣ N ( z ) ∩ Y ∣ a_z=|N(z)\cap Y| a z = ∣ N ( z ) ∩ Y ∣ . Counting pairs of an s s s -subset of Y Y Y and a common neighbor gives
∑ z ( a z / ∣ Y ∣ ) s ≥ T , ∑ z a z / ∣ Y ∣ ≤ D . \sum_z(a_z/|Y|)^s\ge T,\qquad\sum_z a_z/|Y|\le D. z ∑ ( a z /∣ Y ∣ ) s ≥ T , z ∑ a z /∣ Y ∣ ≤ D . The first inequality uses ( a z s ) / ( ∣ Y ∣ s ) ≤ ( a z / ∣ Y ∣ ) s \binom{a_z}{s}/\binom{|Y|}{s}\le(a_z/|Y|)^s ( s a z ) / ( s ∣ Y ∣ ) ≤ ( a z /∣ Y ∣ ) s . The terms with a z < ( 1 − ϑ ) ∣ Y ∣ a_z<(1-\vartheta)|Y| a z < ( 1 − ϑ ) ∣ Y ∣ contribute at most D ( 1 − ϑ ) s − 1 ≤ T / 2 D(1-\vartheta)^{s-1}\le T/2 D ( 1 − ϑ ) s − 1 ≤ T /2 . Each remaining term is at most one. □
Lemma 2.6 (Residual codegrees). Let q ≥ 1 q \ge1 q ≥ 1 be an integer, D > 0 D > 0 D > 0 , and ρ ≥ 0 \rho\ge0 ρ ≥ 0 . Let a graph of maximum degree at most D D D contain no two disjoint q q q -sets of cross density at least ρ \rho ρ . If T ′ ≥ 2 q T' \ge2q T ′ ≥ 2 q and ( T ′ − q ) / D > ρ (T' - q)/D > \rho ( T ′ − q ) / D > ρ , the graph joining pairs of codegree greater than T ′ T' T ′ has maximum degree below q q q .
Proof. If x x x has q q q such partners, remove those partners from N ( x ) N(x) N ( x ) . Each partner still has more than T ′ − q T' - q T ′ − q neighbors in the remaining set, which has order at most D D D . Averaging a q q q -subset there gives the forbidden rectangle. Indeed each partner has more than T ′ − q ≥ q T' - q \ge q T ′ − q ≥ q neighbors remaining, so there are enough vertices for this averaging step. For a bipartite graph with the partners on one side and their neighbors on the other, no removal is needed, and T ′ / D > ρ T'/D > \rho T ′ / D > ρ suffices. □
Reduction to polynomial maximum degree
The reduction in this section is uniform in the number of vertices and in the number of degree scales. We use the fixed exponent A = 210 A = 210 A = 210 ; its size is only a convenience for the normalization below.
Dyadic decomposition
Proposition 3.1. To prove Theorem 1.1 , it suffices to establish the following two statements for every fixed M ≥ 1 M \ge1 M ≥ 1 and all sufficiently large integers q q q :
every graph of minimum degree at least q / 2 16 q/2^{16} q / 2 16 and maximum degree at most q 210 q^{210} q 210 has size Ramsey number greater than M q Mq M q times its number of edges;
the same conclusion, with a non-strict inequality allowed, holds for bipartite graphs whose nonisolated vertices have degree at least q / 2 16 q/2^{16} q / 2 16 , whose right degrees are at most 2 q 2q 2 q , and whose left degrees exceed q 210 / 8 q^{210}/8 q 210 /8 .
Proof. First consider a graph G G G of minimum degree at least d d d . Orient every edge from the endpoint of larger degree to the endpoint of smaller degree, breaking ties by a fixed order. Randomly label vertices left or right and retain edges directed from left to right. Some labeling retains at least e ( G ) / 4 e(G)/4 e ( G ) /4 edges. Partition the right vertices by their original degrees in dyadic intervals [ q , 2 q ) [q, 2q) [ q , 2 q ) . In a band, every left endpoint has original degree at least q q q . Repeatedly delete a vertex of current degree below q / 128 q/128 q /128 . At a left vertex the total loss over the bands is at most ∑ q ≤ deg G ( v ) q / 128 ≤ deg G ( v ) / 64 \sum_{q \le\deg_G(v)} q/128 \le\deg_G(v)/64 ∑ q ≤ d e g G ( v ) q /128 ≤ deg G ( v ) /64 ; a right vertex occurs in one band only. Thus the total retained edge mass is at least 13 e ( G ) / 64 13e(G)/64 13 e ( G ) /64 .
In each band split the left vertices at current degree q 210 q^{210} q 210 . In each of the resulting two graphs, peel a left vertex below one eighth of its degree before the split, or a right vertex below q / 2 16 q/2^{16} q / 2 16 . The left loss is at most one eighth of the band’s edges. Since the right order before splitting is at most 128 e q / q 128e_q/q 128 e q / q , the right loss in the two graphs is at most e q / 256 e_q/256 e q /256 . Consequently the final pieces have total edge mass at least 21 e ( G ) / 128 21e(G)/128 21 e ( G ) /128 . The low pieces satisfy the first description and the high pieces satisfy the second. Every active scale has q > d / 2 q > d/2 q > d /2 .
Let R = R ^ ( G ) R = \widehat{R}(G) R = R ( G ) . A Ramsey host for G G G is a Ramsey host for each piece. If both assertions hold with multiplier M 1 = 128 M M_1 = 128M M 1 = 128 M , then the combined edge mass at scale q q q is at most 2 R / ( M 1 q ) 2R/(M_1q) 2 R / ( M 1 q ) . The reciprocal dyadic sum over q > d / 2 q > d/2 q > d /2 is at most 4 / d 4/d 4/ d . Hence
21 128 e ( G ) ≤ 8 R M 1 d , \frac{21}{128}e(G) \le\frac{8R}{M_1d}, 128 21 e ( G ) ≤ M 1 d 8 R ,
which implies R > M d e ( G ) R > Mde(G) R > M d e ( G ) . This proves uniform superlinear growth in the minimum degree.
For a graph with e ( G ) ≥ C v ( G ) e(G) \ge Cv(G) e ( G ) ≥ C v ( G ) , peel vertices below C / 2 C/2 C /2 . At least e ( G ) / 2 e(G)/2 e ( G ) /2 edges remain, with minimum degree at least C / 2 C/2 C /2 . Applying the preceding result and monotonicity proves the required fixed-multiplier assertion. Its equivalence with the real-valued formulation in Theorem 1.1 is recorded explicitly in the final section.
:::
Normalization of the high-degree pieces
Proposition 3.2. Suppose q q q is sufficiently large, G G G is a bipartite graph with positive edge count, its right degrees are at most 2 q 2q 2 q , its nonisolated degrees are at least q / 2 16 q/2^{16} q / 2 16 , and every nonisolated left degree is at least q 209 q^{209} q 209 . If
R ^ ( G ) ≤ Λ e ( G ) , 1 ≤ Λ ≤ q 2 , \widehat{R}(G) \leq\Lambda e(G), \qquad1 \leq\Lambda\leq q^2, R ( G ) ≤ Λ e ( G ) , 1 ≤ Λ ≤ q 2 , then G G G contains an incidence subgraph F F F with exact right degree t = ⌊ q / 2 20 ⌋ t = \lfloor q/2^{20}\rfloor t = ⌊ q / 2 20 ⌋ , positive edge count, and a number p ≥ q 209 p \geq q^{209} p ≥ q 209 such that
p 2 27 ≤ deg F ( x ) ≤ 5 Λ p ( x on the left ) , e ( G ) ≤ 2 26 e ( F ) . \frac{p}{2^{27}} \leq\deg_F(x) \leq5\Lambda p \quad(x\text{ on the left}), \qquad e(G) \leq2^{26}e(F). 2 27 p ≤ deg F ( x ) ≤ 5Λ p ( x on the left ) , e ( G ) ≤ 2 26 e ( F ) .
Proof. Choose an edge-weighted median p p p of the left degrees, so that left vertices of degree at most p p p and those of degree at least p p p each meet at least half the edges. The first group gives a subgraph with at least e ( G ) / 2 e(G)/2 e ( G ) /2 edges and maximum degree at most p p p . The degree-cover bound, Lemma 2.3 , applied to this subgraph gives Δ ( G ) ≤ 4 Λ p \Delta(G) \leq4\Lambda p Δ ( G ) ≤ 4Λ p .
Retain the edges at left vertices of degree at least p p p . Peel left vertices below p / 8 p/8 p /8 and right vertices below q / 2 19 q/2^{19} q / 2 19 . The left loss is at most e ( G ) / 8 e(G)/8 e ( G ) /8 : the number of initially retained left vertices is at most e ( G ) / p e(G)/p e ( G ) / p . The right loss is also at most e ( G ) / 8 e(G)/8 e ( G ) /8 , since the original nonisolated right order is at most 2 16 e ( G ) / q 2^{16}e(G)/q 2 16 e ( G ) / q . At least e ( G ) / 4 e(G)/4 e ( G ) /4 edges remain.
At each surviving right vertex independently choose exactly t t t neighbors. For large q q q , t ≥ q / 2 21 t \geq q/2^{21} t ≥ q / 2 21 , so each left degree has expectation at least p / 2 25 p/2^{25} p / 2 25 . Its probability of falling below half this expectation is at most exp ( − p / 2 28 ) \exp(-p/2^{28}) exp ( − p / 2 28 ) . Such an event shares variables with at most 8 q 3 p 8q^3p 8 q 3 p other left events, using Λ ≤ q 2 \Lambda\leq q^2 Λ ≤ q 2 and the original right degree bound. Since p ≥ q 209 p \geq q^{209} p ≥ q 209 , the symmetric local lemma applies uniformly for all p p p in this range. The selected graph has left degree at least p / 2 27 p/2^{27} p / 2 27 and at most 5 Λ p 5\Lambda p 5Λ p . Selection retains at least a 2 − 22 2^{-22} 2 − 22 fraction of the last edge count; the stated weaker loss 2 26 2^{26} 2 26 follows. □
Corollary 3.3. In Proposition 3.1 , the high-degree assertion follows from uniform superlinear growth for incidence graphs of exact right degree d d d whose left degrees lie in [ P , d 4 P ] [P,d^4P] [ P , d 4 P ] , with P ≥ d 200 P \geq d^{200} P ≥ d 200 .
Proof. If the high-degree assertion fails at a fixed multiplier M M M , choose arbitrarily large q q q and a Ramsey host with at most M q e ( G ) Mq e(G) M q e ( G ) edges. For large q q q , M q ≤ q 2 Mq \leq q^2 M q ≤ q 2 and q 210 / 8 ≥ q 209 q^{210}/8 \geq q^{209} q 210 /8 ≥ q 209 . Apply the proposition with Λ = M q \Lambda= Mq Λ = M q , and put P = p / 2 27 P = p/2^{27} P = p / 2 27 . For sufficiently large q q q ,
P ≥ t 200 , 5 M q p ≤ t 4 P , q ≤ 2 21 t . P \geq t^{200}, \qquad5Mqp \leq t^4P, \qquad q \leq2^{21}t. P ≥ t 200 , 5 M q p ≤ t 4 P , q ≤ 2 21 t .
The same host arrows F F F and has at most 2 47 M t e ( F ) 2^{47}Mt e(F) 2 47 M t e ( F ) edges, contradicting the asserted uniform bound at degree t → ∞ t \to\infty t → ∞ . □
A dictionary for large-right incidence blocks
Proposition 3.4. Let q ≥ 2 32 q \geq2^{32} q ≥ 2 32 be an integer. Let F F F be a vertex-disjoint union of incidence graphs F i F_i F i , with parts A i , B i A_i,B_i A i , B i , satisfying
∣ A i ∣ ≤ q 20 , ∣ B i ∣ ≥ 128 q 69 , deg F i ( y ) = q ( y ∈ B i ) . |A_i| \leq q^{20}, \qquad|B_i| \geq128q^{69}, \qquad\deg_{F_i}(y) = q \quad(y \in B_i). ∣ A i ∣ ≤ q 20 , ∣ B i ∣ ≥ 128 q 69 , deg F i ( y ) = q ( y ∈ B i ) . There is no restriction on the number or diversity of these blocks. Then
R ^ ( F ) > 7 16 q 49 e ( F ) . \widehat{R}(F) > \frac{7}{16}q^{49}e(F). R ( F ) > 16 7 q 49 e ( F ) . Adding isolated vertices to the target does not affect this lower bound.
Proof. Put
a = q 20 , Γ = q 50 , D = 8 Γ , M = ( a + 1 ) q , R = 16 M Γ D , K = ( R + 1 ) a + 1 , (1) a = q^{20}, \qquad\Gamma= q^{50}, \qquad D = 8\Gamma, \qquad M = (a+1)^q, \qquad R = 16M\Gamma D, \qquad K = (R+1)^a + 1, \tag*{(1)} a = q 20 , Γ = q 50 , D = 8Γ , M = ( a + 1 ) q , R = 16 M Γ D , K = ( R + 1 ) a + 1 , (1)
and let ℓ = ⌈ 2 q / 16 ⌉ \ell= \lceil2^{q/16}\rceil ℓ = ⌈ 2 q /16 ⌉ , s = ⌊ q / 2 ⌋ s = \lfloor q/2\rfloor s = ⌊ q /2 ⌋ , and J = q 43 J = q^{43} J = q 43 . Fix an arbitrary host H H H . Write Y = { v : deg H ( v ) ≤ D } Y = \{v : \deg_H(v) \le D\} Y = { v : deg H ( v ) ≤ D } . On the vertices of degree greater than D D D , form a graph Q Q Q by joining distinct x , z x,z x , z when
max { deg H ( x ) , deg H ( z ) } ≤ 16 M Γ ∣ N H ( x ) ∩ N H ( z ) ∩ Y ∣ . \max\{\deg_H(x),\deg_H(z)\} \le16M\Gamma|N_H(x) \cap N_H(z) \cap Y|. max { deg H ( x ) , deg H ( z )} ≤ 16 M Γ∣ N H ( x ) ∩ N H ( z ) ∩ Y ∣.
Summing codegrees at x x x gives Δ ( Q ) ≤ R \Delta(Q) \le R Δ ( Q ) ≤ R . Color the graph joining vertices at Q Q Q -distance at most a a a with K K K labels. Such a coloring exists because its maximum degree is below K K K . Its labels are injective on every connected set of at most a a a vertices in Q Q Q .
Dictionary tests. In a target block, remove the left vertices of target degree at most D D D , and write T y T_y T y for a right vertex’s remaining neighborhood. Let B ∗ = { y : ∣ T y ∣ ≥ s } B_* = \{y : |T_y| \ge s\} B ∗ = { y : ∣ T y ∣ ≥ s } . We will test all partial injective label maps on A i A_i A i : a map to the K K K labels, with a further value meaning “undefined.” For each map retain exactly the rows of B ∗ B_* B ∗ on which every label is defined. There are at most ( K + 1 ) a (K+1)^a ( K + 1 ) a tests per block. This includes the restriction of every injective labeling of any selected left subset.
Give each label an independent uniform binary word of length ℓ \ell ℓ . For a test on a row set B ′ B' B ′ , call a coordinate bad when more than ∣ B ′ ∣ / ( 4 ℓ ) |B'|/(4\ell) ∣ B ′ ∣/ ( 4 ℓ ) rows have constant sign on their label sets at that coordinate. A row uses at least s s s distinct labels, so Markov’s inequality bounds the probability of a bad coordinate by 4 ℓ 2 1 − s 4\ell2^{1-s} 4 ℓ 2 1 − s . Independence between coordinates and a union bound give
Pr ( at least J bad coordinates ) ≤ ( 8 ℓ 2 − s ) J . \Pr(\text{at least }J\text{ bad coordinates}) \le(8\ell2^{-s})^J. Pr ( at least J bad coordinates ) ≤ ( 8 ℓ 2 − s ) J .
The parameters above satisfy
log ( ( K + 1 ) a ) ≤ 131 q 42 , 8 ℓ 2 − s ≤ exp ( − q / 8 ) , ( K + 1 ) a exp ( − q J / 8 ) ≤ 1 8 . \log((K+1)^a) \le131q^{42}, \qquad8\ell2^{-s} \le\exp(-q/8), \qquad(K+1)^a\exp(-qJ/8) \le\frac18. log (( K + 1 ) a ) ≤ 131 q 42 , 8 ℓ 2 − s ≤ exp ( − q /8 ) , ( K + 1 ) a exp ( − q J /8 ) ≤ 8 1 .
For completeness, log ( q 20 + 1 ) ≤ 1 + 20 q \log(q^{20}+1) \le1+20q log ( q 20 + 1 ) ≤ 1 + 20 q gives log R ≤ 128 q 2 \log R \le128q^2 log R ≤ 128 q 2 , log ( R + 1 ) ≤ 129 q 2 \log(R+1) \le129q^2 log ( R + 1 ) ≤ 129 q 2 , and log ( K + 1 ) ≤ 131 q 22 \log(K+1) \le131q^{22} log ( K + 1 ) ≤ 131 q 22 . Also ℓ ≤ 2 ⋅ 2 q / 16 \ell\le2\cdot2^{q/16} ℓ ≤ 2 ⋅ 2 q /16 and s ≥ ( q − 1 ) / 2 s \ge(q-1)/2 s ≥ ( q − 1 ) /2 , so the logarithm of the middle expression is at most 11 log 2 / 2 − 3 q log 2 / 8 ≤ − q / 8 11\log2/2 - 3q\log2/8 \le-q/8 11 log 2/2 − 3 q log 2/8 ≤ − q /8 . Finally 131 q 42 − q 44 / 8 ≤ − 3 log 2 131q^{42} - q^{44}/8 \le-3\log2 131 q 42 − q 44 /8 ≤ − 3 log 2 for q ≥ 65536 q \ge65536 q ≥ 65536 . Call a block good when every test has fewer than J J J bad coordinates. Weighted expectation, with weight ∣ B i ∣ |B_i| ∣ B i ∣ , supplies one dictionary for which good blocks carry at least 7 / 8 7/8 7/8 of the total right order. For each test, at most ∣ B ′ ∣ / 4 |B'|/4 ∣ B ′ ∣/4 rows are uniform at one or more good coordinates, by summing the defining bound over at most ℓ \ell ℓ coordinates.
One assignment of coordinates to host rows. Independently give every vertex of Y Y Y a uniform coordinate. For every nonempty Q Q Q -connected set W W W of order at most a a a , put R W = Y ∩ ⋃ x ∈ W N H ( x ) R_W = Y \cap\bigcup_{x\in W} N_H(x) R W = Y ∩ ⋃ x ∈ W N H ( x ) . Consider every dyadic scale B = 2 j B=2^j B = 2 j satisfying
8 a D ≤ q B , B ≤ 8 M deg H ( x ) , deg H ( x ) < 2 Γ B ( x ∈ W ) . 8aD \le qB, \qquad B \le8M\deg_H(x), \qquad\deg_H(x) < 2\Gamma B \quad(x \in W). 8 a D ≤ q B , B ≤ 8 M deg H ( x ) , deg H ( x ) < 2Γ B ( x ∈ W ) .
For every set S S S of at most J J J coordinates, forbid the event that at least ⌈ B / ( 8 a ) ⌉ \lceil B/(8a)\rceil ⌈ B / ( 8 a )⌉ vertices of R W R_W R W receive a coordinate in S S S . Since ∣ R W ∣ ≤ 2 a Γ B |R_W| \le2a\Gamma B ∣ R W ∣ ≤ 2 a Γ B , the binomial tail is at most
( 16 e a 2 J / ℓ ) ⌈ B / ( 8 a ) ⌉ ≤ exp ( − q B / ( 512 a ) ) . (16ea^2J/\ell)^{\lceil B/(8a)\rceil} \le\exp(-qB/(512a)). ( 16 e a 2 J / ℓ ) ⌈ B / ( 8 a )⌉ ≤ exp ( − q B / ( 512 a )) .
A host row is in the support of at most
N 0 = D ( a + 1 ) R 2 a ( 16 M Γ ) ( J + 1 ) ℓ J N_0 = D(a+1)R^{2a}(16M\Gamma)(J+1)\ell^J N 0 = D ( a + 1 ) R 2 a ( 16 M Γ ) ( J + 1 ) ℓ J
events. Indeed, root a connected set at a neighbor of that row and encode it by a walk of length at most 2 a 2a 2 a ; there are at most a + 1 a+1 a + 1 possible orders. The admissible scales have multiplicative range less than 16 M Γ 16M\Gamma 16 M Γ , hence number at most that quantity. Finally, the number of coordinate subsets is at most ( J + 1 ) ℓ J (J+1)\ell^J ( J + 1 ) ℓ J .
Give a scale-B B B event weight x B = exp ( − q B / ( 1024 a ) ) x_B=\exp(-qB/(1024a)) x B = exp ( − q B / ( 1024 a )) . The concrete parameters satisfy
log N 0 ≤ q 46 , N 0 exp ( − D / 128 ) ≤ η : = q 8192 a 2 Γ . \log N_0 \le q^{46}, \qquad N_0\exp(-D/128) \le\eta:= \frac{q}{8192a^2\Gamma}. log N 0 ≤ q 46 , N 0 exp ( − D /128 ) ≤ η := 8192 a 2 Γ q .
These estimates use only q ≥ 2 32 q \ge2^{32} q ≥ 2 32 ; the exponential term D / 128 = q 50 / 16 D/128 = q^{50}/16 D /128 = q 50 /16 dominates q 46 q^{46} q 46 and the logarithm of 1 / η 1/\eta 1/ η . Every event weight is at most 1 / 2 1/2 1/2 , and the total event weight at any one variable is at most η \eta η . Its dependency product is therefore at least
exp ( − 2 η ∣ R W ∣ ) ≥ exp ( − 4 η a Γ B ) ≥ x B . \exp(-2\eta|R_W|) \ge\exp(-4\eta a\Gamma B) \ge x_B. exp ( − 2 η ∣ R W ∣ ) ≥ exp ( − 4 η a Γ B ) ≥ x B .
The event probability is at most x B 2 x_B^2 x B 2 . The asymmetric local lemma gives an assignment avoiding all these events simultaneously.
Exclude a cheap monochromatic block. Color an edge between a host vertex of degree greater than D D D and a vertex of Y Y Y by the former’s label word at the latter’s assigned coordinate. Color all other edges arbitrarily. Fix a good target block and suppose it has a monochromatic copy of degree charge at most Γ b \Gamma b Γ b , where b = ∣ B i ∣ b=|B_i| b = ∣ B i ∣ and degree charge means the sum of host degrees over all vertices of the copy.
Deleting low-degree target left vertices loses at most a D ≤ q b / 16 aD \le qb/16 a D ≤ q b /16 edges, so ∣ B ∗ ∣ ≥ 7 b / 8 |B_*| \ge7b/8 ∣ B ∗ ∣ ≥ 7 b /8 . There are at most M M M patterns T y T_y T y : encode a set of at most q q q elements of A i A_i A i by a q q q -tuple with an extra padding symbol. Patterns occurring fewer than b / ( 8 M ) b/(8M) b / ( 8 M ) times contain at most b / 8 b/8 b /8 rows. Patterns in which fewer than half the rows have low host images contain at most twice the number of high right images, hence at most b / 4 b/4 b /4 rows. There are at most b / 8 b/8 b /8 high right images. After these deletions, at least 3 b / 8 3b/8 3 b /8 low rows survive.
Turn every surviving pattern into a clique on the target left side. Every pair in such a pattern has at least b / ( 16 M ) b/(16M) b / ( 16 M ) common low host neighbors. Since individual image degrees are at most Γ b \Gamma b Γ b , it maps to an edge of Q Q Q . Thus each target component maps to a connected set with injective host labels. For a component U U U , let B U B_U B U consist of all rows of B ∗ B_* B ∗ whose pattern lies in U U U . These row sets are disjoint, and every surviving row belongs to one of them. Their total order is at most b b b .
At most b / 4 b/4 b /4 surviving rows can use a good coordinate. Therefore at least b / 8 b/8 b /8 use bad coordinates, and some component U U U supplies at least b / ( 8 a ) b/(8a) b / ( 8 a ) such rows. Every vertex of this component belongs to a surviving pattern, and hence has degree at least b / ( 8 M ) b/(8M) b / ( 8 M ) . Its host image W W W has all degrees between b / ( 8 M ) b/(8M) b / ( 8 M ) and Γ b \Gamma b Γ b . Taking B = 2 ⌊ log 2 b ⌋ B=2\lfloor\log_2 b\rfloor B = 2 ⌊ log 2 b ⌋ gives an admissible scale: the condition 8 a D ≤ q B 8aD \le qB 8 a D ≤ q B follows from b ≥ 128 q 69 b \ge128q^{69} b ≥ 128 q 69 . The bad-coordinate set for B U B_U B U has fewer than J J J elements. The selected low row images are distinct members of R W R_W R W , and at least ⌈ B / ( 8 a ) ⌉ \lceil B/(8a)\rceil ⌈ B / ( 8 a )⌉ receive one of these coordinates. This contradicts the assignment.
Each monochromatic copy of the full target therefore gives disjoint good-block images, each with degree charge greater than Γ ∣ B i ∣ \Gamma|B_i| Γ∣ B i ∣ . Their aggregate charge is greater than 7 Γ ∑ i ∣ B i ∣ / 8 7\Gamma\sum_i |B_i|/8 7Γ ∑ i ∣ B i ∣/8 . Since the total host degree sum is 2 e ( H ) 2e(H) 2 e ( H ) and e ( F ) = q ∑ i ∣ B i ∣ e(F)=q\sum_i |B_i| e ( F ) = q ∑ i ∣ B i ∣ , a host of at most 7 q 49 e ( F ) / 16 7q^{49}e(F)/16 7 q 49 e ( F ) /16 edges cannot contain such a copy. This proves the proposition. □
Strongly unbalanced targets
Proposition 3.5. For every fixed M ≥ 1 M \ge1 M ≥ 1 and all sufficiently large integers d d d , let G G G be an incidence graph of positive order and exact right degree d d d . If its left degrees lie in [ P , d d P ] [P,d^dP] [ P , d d P ] with P ≥ d 200 P \ge d^{200} P ≥ d 200 , then
R ^ ( G ) > M d e ( G ) . \widehat{R}(G) > M d e(G). R ( G ) > M d e ( G ) .
The assertion is uniform in P P P , the order, and the component structure.
Proof. Write a , b a,b a , b for the side orders, put W = P / d 12 W=P/d^{12} W = P / d 12 , and call a left pair heavy when its codegree is at least W W W . The heavy-pair graph has maximum degree at most d 17 d^{17} d 17 . Call a right row concentrated when at least q = ⌊ d / 4 ⌋ q=\lfloor d/4\rfloor q = ⌊ d /4 ⌋ of its neighbors lie in some closed heavy-pair neighborhood.
Many concentrated rows. Suppose more than half the rows are concentrated. Assign each such row to a witnessing center. Color the square of the heavy-pair graph and keep one center color. Distinct retained centers have disjoint closed neighborhoods. Retain exactly q q q neighbors inside the assigned ball at each row. Delete a center if it has fewer than 128 q 69 128q^{69} 128 q 69 rows. There are at most a ≤ d b / P a \le db/P a ≤ d b / P centers, so this last deletion costs at most 128 q 69 d b / P 128q^{69}db/P 128 q 69 d b / P rows. For d ≥ 2 32 d \ge2^{32} d ≥ 2 32 this is smaller than the fixed fraction retained in the square-coloring step. The elementary counts, including q ≥ d / 5 q \ge d/5 q ≥ d /5 , give a subgraph F F F with
e ( G ) ≤ 128 d 34 e ( F ) , ∣ A i ∣ ≤ q 20 , ∣ B i ∣ ≥ 128 q 69 . e(G) \le128d^{34}e(F), \qquad|A_i| \le q^{20}, \qquad|B_i| \ge128q^{69}. e ( G ) ≤ 128 d 34 e ( F ) , ∣ A i ∣ ≤ q 20 , ∣ B i ∣ ≥ 128 q 69 .
The ball-size bound follows from 1 + d 17 ≤ q 20 1+d^{17} \le q^{20} 1 + d 17 ≤ q 20 for these d d d . Proposition 3.4 and monotonicity give
R ^ ( G ) > 7 q 49 2048 d 34 e ( G ) > M d e ( G ) \widehat{R}(G) > \frac{7q^{49}}{2048d^{34}}e(G) > Md\,e(G) R ( G ) > 2048 d 34 7 q 49 e ( G ) > M d e ( G )
for sufficiently large d d d depending on M M M .
At least half the rows are not concentrated. Their neighborhoods contribute ordered light-pair codegree mass at least a P d / 4 aPd/4 a P d /4 . Let ρ = d − 6 \rho=d^{-6} ρ = d − 6 , and, for a proposed host with at most M d e ( G ) Md\,e(G) M d e ( G ) edges, set
D L = ⌈ 16 M d 5 P ⌉ , D R = ⌈ 16 M d 2 ⌉ . D_L=\lceil16Md^5P\rceil,\qquad D_R=\lceil16Md^2\rceil. D L = ⌈ 16 M d 5 P ⌉ , D R = ⌈ 16 M d 2 ⌉ .
Use high host vertices of degree in [ P , D L ] [P,D_L] [ P , D L ] and nonisolated low host vertices of degree at most D R D_R D R . These sets are disjoint for large d d d . They satisfy D R 2 ≤ 1024 d 5 D_R^2\le1024d^5 D R 2 ≤ 1024 d 5 and D L D R ≤ 1024 d 8 P D_LD_R\le1024d^8P D L D R ≤ 1024 d 8 P once M 2 ≤ d M^2\le d M 2 ≤ d .
Partition light pairs by their positive integer codegrees into dyadic bands, starting from a power of two in [ W , 2 W ] [W,2W] [ W , 2 W ] . The associated host pair graph at band j j j has maximum degree at most D j = D 0 2 j D_j=D_0 2^j D j = D 0 2 j , where 2 ≤ D 0 ≤ 4096 d 20 2\le D_0\le4096d^{20} 2 ≤ D 0 ≤ 4096 d 20 . If every target band had fewer than 32 a ρ − 1 log D j 32a\rho^{-1}\log D_j 32 a ρ − 1 log D j edges, summing their codegree contributions would give O ( a P d − 6 log d ) O(aPd^{-6}\log d) O ( a P d − 6 log d ) , contradicting a P d / 4 aPd/4 a P d /4 . Thus one band has a connected component T T T with k k k vertices and f f f edges such that
k ≥ d , ρ f ≥ 32 k log D j . k\ge d,\qquad\rho f\ge32k\log D_j. k ≥ d , ρ f ≥ 32 k log D j .
Mark each host pair independently with probability ρ \rho ρ . For every copy of T T T in the host pair graph, forbid the event that all its edges are unmarked. Give this event weight exp ( − ρ f / 2 ) \exp(-\rho f/2) exp ( − ρ f /2 ) . The number of copies using a fixed pair is at most k 2 D j k − 2 k^2D_j^{k-2} k 2 D j k − 2 , so the total event weight at a pair is at most d − 13 d^{-13} d − 13 . Because 4 d − 13 ≤ ρ 4d^{-13}\le\rho 4 d − 13 ≤ ρ , the asymmetric local lemma applies. Moreover, conditioning on the avoidance of all these events multiplies the probability of any event determined by s s s pair variables by at most exp ( 2 d − 13 s ) \exp(2d^{-13}s) exp ( 2 d − 13 s ) .
At a low host row there are at most D R 2 ≤ 1024 d 5 D_R^2\le1024d^5 D R 2 ≤ 1024 d 5 relevant pair variables. The binomial upper tail and the preceding correction bound show that the conditional probability of at least d / 4 d/4 d /4 marked pairs is at most 2 d − 8 2d^{-8} 2 d − 8 . Select an avoiding outcome for which the number of such bad host rows is at most 2 d − 8 2d^{-8} 2 d − 8 times the low host order. That order is at most twice the host edge count, so the bad row count is at most e ( G ) / ( 8 d ) e(G)/(8d) e ( G ) / ( 8 d ) for large d d d .
Color a high-low edge blue when its high endpoint belongs to a marked pair in the neighborhood of its low endpoint, and color the remaining high-low edges red. All other host edges are blue. A red copy of G G G must have its left images high and its right images low, since P > D R P>D_R P > D R . The selected target pair component then gives an entirely unmarked copy of T T T , a contradiction.
In a blue copy, the target edge mass at left images of degree above D L D_L D L is at most e ( G ) / 8 e(G)/8 e ( G ) /8 , by the host degree sum and the target left degree bound d 4 P d^4P d 4 P . Right images above D R D_R D R cost at most e ( G ) / 8 e(G)/8 e ( G ) /8 , and bad low right images cost at most e ( G ) / 8 e(G)/8 e ( G ) /8 . Every remaining right image meets fewer than d / 4 d/4 d /4 marked pairs and therefore fewer than d / 2 d/2 d /2 blue high-low edges. These account for at most e ( G ) / 2 e(G)/2 e ( G ) /2 edges. The total is below e ( G ) e(G) e ( G ) , a contradiction. This completes both cases.
The polynomial-degree reduction
Proposition 3.6. To prove Theorem 1.1 it remains to prove that, for every fixed B , M ≥ 1 B,M\ge1 B , M ≥ 1 , all sufficiently large d d d and all positive-order graphs G G G with δ ( G ) ≥ d \delta(G)\ge d δ ( G ) ≥ d and Δ ( G ) ≤ d B \Delta(G)\le d^B Δ ( G ) ≤ d B satisfy R ^ ( G ) > M d e ( G ) \widehat{R}(G)>Md\,e(G) R ( G ) > M d e ( G ) .
Proof. The low pieces of Proposition 3.1 have polynomial maximum degree after rescaling their minimum degree by the fixed factor 2 16 2^{16} 2 16 . Its high pieces are covered by Corollary 3.3 and Proposition 3.5 . The dyadic edge-mass argument therefore gives the full minimum-degree assertion and then the original density statement. The converse implication is immediate from the handshake lemma, so no restricted family is being substituted for the original target. □ \square □
Logarithmic local density
Relative-degree dense balls
Lemma 4.1. Let F F F be connected, of minimum degree at least d d d , maximum degree at most Δ \Delta Δ , and order at most K K K . Put w ( v ) = deg F ( v ) w(v)=\deg_F(v) w ( v ) = deg F ( v ) and w ( U ) = ∑ v ∈ U w ( v ) w(U)=\sum_{v\in U}w(v) w ( U ) = ∑ v ∈ U w ( v ) . Every subgraph retaining at least 3 e ( F ) / 4 3e(F)/4 3 e ( F ) /4 edges contains a connected vertex set U U U spanning at least w ( U ) / 16 w(U)/16 w ( U ) /16 retained edges. One may take ∣ U ∣ ≥ d / 8 + 1 |U|\ge d/8+1 ∣ U ∣ ≥ d /8 + 1 and diam ( F [ U ] ) ≤ 2 ⌈ log 9 / 8 ( K Δ ) ⌉ \operatorname{diam}(F[U])\le2\lceil\log_{9/8}(K\Delta)\rceil diam ( F [ U ]) ≤ 2 ⌈ log 9/8 ( K Δ )⌉ .
Proof. For a target component F F F , put w ( v ) = deg F ( v ) w(v)=\deg_F(v) w ( v ) = deg F ( v ) , and w ( U ) = ∑ v ∈ U w ( v ) w(U)=\sum_{v\in U}w(v) w ( U ) = ∑ v ∈ U w ( v ) . Suppose a residual subgraph of F F F retains at least 3 e ( F ) / 4 3e(F)/4 3 e ( F ) /4 edges. Peel vertices whose current degree is below w ( v ) / 4 w(v)/4 w ( v ) /4 . The total peeled edge count is at most ∑ v w ( v ) / 4 = e ( F ) / 2 \sum_v w(v)/4=e(F)/2 ∑ v w ( v ) /4 = e ( F ) /2 , so a nonempty core remains with current degree at least w ( v ) / 4 w(v)/4 w ( v ) /4 at every vertex.
In that core, a ball U U U spanning fewer than w ( U ) / 16 w(U)/16 w ( U ) /16 residual edges has at least w ( U ) / 8 w(U)/8 w ( U ) /8 outgoing edges. Every outside endpoint contributes original weight at least its number of incident outgoing edges from the ball. Thus the next ball has weight at least 9 w ( U ) / 8 9w(U)/8 9 w ( U ) /8 . Total weight is at most K Δ K\Delta K Δ , so some ball of radius at most ⌈ log 9 / 8 ( K Δ ) ⌉ \lceil\log_{9/8}(K\Delta)\rceil ⌈ log 9/8 ( K Δ )⌉ spans at least w ( U ) / 16 w(U)/16 w ( U ) /16 residual edges. It has diameter at most
r = 2 ⌈ log 9 / 8 ( K Δ ) ⌉ ≤ 12 log 2 ( K Δ ) + 2 (2) r=2\lceil\log_{9/8}(K\Delta)\rceil\le12\log_2(K\Delta)+2 \tag*{(2)} r = 2 ⌈ log 9/8 ( K Δ )⌉ ≤ 12 log 2 ( K Δ ) + 2 (2)
and order u ≥ d / 8 + 1 u\ge d/8+1 u ≥ d /8 + 1 by simplicity, because w ( U ) ≥ d u w(U)\ge du w ( U ) ≥ d u . □ \square □
A palette with few repeated labels
Lemma 4.2. Let J J J have maximum degree at most D ≥ 2 D\ge2 D ≥ 2 , let K ≥ 1 K\ge1 K ≥ 1 , and let 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 . There is a labeling with at most P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12 / ε ⌉ P=(D^2+1)\lceil K(D+1)^{12/\varepsilon}\rceil P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12/ ε ⌉ labels such that every connected u u u -vertex set, u ≤ K u\le K u ≤ K , has at most 2 ε u 2\varepsilon u 2 ε u vertices whose label repeats in that set. If two edges in the set have the same unordered label pair, both endpoint labels repeat in the set.
Proof. Let J J J have maximum degree at most D D D , where D ≥ 2 D\ge2 D ≥ 2 . Fix an integer K ≥ 1 K\ge1 K ≥ 1 and 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 . Independently give its vertices random labels from a palette of size
P 0 = ⌈ K ( D + 1 ) 12 / ε ⌉ . (3) P_0=\left\lceil K(D+1)^{12/\varepsilon}\right\rceil. \tag*{(3)} P 0 = ⌈ K ( D + 1 ) 12/ ε ⌉ . (3)
For a connected set of order u ≤ K u\le K u ≤ K , expose the labels in any fixed order. The probability that there are more than ε u \varepsilon u ε u collisions with previous labels is at most
2 u ( K / P 0 ) ε u ≤ ( D + 1 ) − 10 u . (4) 2^u\left(K/P_0\right)^{\varepsilon u}\le(D+1)^{-10u}. \tag*{(4)} 2 u ( K / P 0 ) ε u ≤ ( D + 1 ) − 10 u . (4)
Indeed for any fixed positions of the collisions the conditional probability at each specified position is at most u / P 0 u/P_0 u / P 0 . A connected set of order t t t through a specified vertex can be encoded by a spanning-tree walk of length 2 ( t − 1 ) 2(t-1) 2 ( t − 1 ) , so there are at most D 2 ( t − 1 ) D^{2(t-1)} D 2 ( t − 1 ) such sets. Give a collision event on u u u vertices local-lemma weight ( D + 1 ) − 4 u (D+1)^{-4u} ( D + 1 ) − 4 u . The sum of event weights through any vertex is at most ∑ t ≥ 1 ( D + 1 ) − 2 t < 1 / 8 \sum_{t\ge1}(D+1)^{-2t}<1/8 ∑ t ≥ 1 ( D + 1 ) − 2 t < 1/8 . Events on disjoint sets are independent. The dependency product for a size-u u u event is at least exp ( − u / 4 ) \exp(-u/4) exp ( − u /4 ) and the local lemma applies.
Fix the resulting labeling and append a proper color of J 2 J^2 J 2 using at most D 2 + 1 D^2+1 D 2 + 1 colors. The full palette has size P = P 0 ( D 2 + 1 ) P=P_0(D^2+1) P = P 0 ( D 2 + 1 ) . In every connected set of order u ≤ K u\le K u ≤ K , at most 2 ε u 2\varepsilon u 2 ε u vertices have a full label occurring more than once in that set. Moreover, if two distinct edges in the set have the same unordered pair of full labels, both endpoint labels occur more than once there. Otherwise the edges would share the uniquely labeled endpoint and their other endpoints would have the same full label at distance two, which is impossible.
The palette obstruction
Lemma 4.3. Let F F F have minimum degree at least q ≥ 128 q \ge128 q ≥ 128 , maximum degree at most Δ \Delta Δ , and component orders at most K K K . Suppose each vertex set of order at most K K K spans at most τ \tau τ times its order edges, where τ ≥ q / 2 \tau\ge q/2 τ ≥ q /2 . For Λ ≥ 1 \Lambda\ge1 Λ ≥ 1 , set
D = ⌈ 128 Λ Δ ⌉ , ε = q / ( 256 τ ) , p = 256 log D / q , D = \lceil128\Lambda\Delta\rceil,\qquad\varepsilon= q/(256\tau),\qquad p = 256\log D/q, D = ⌈ 128ΛΔ ⌉ , ε = q / ( 256 τ ) , p = 256 log D / q , and P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12 / ε ⌉ P = (D^2 + 1)\lceil K(D + 1)^{12/\varepsilon}\rceil P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12/ ε ⌉ . Put ℓ = log ( 1 / ( 16 e p ) ) \ell= \log(1/(16ep)) ℓ = log ( 1/ ( 16 e p )) . If ℓ > 0 \ell> 0 ℓ > 0 ,
log P + 2 log Δ ≤ q ℓ / 64 , K ∑ u ≥ ⌈ q / 8 ⌉ exp ( − q ℓ u / 64 ) < 1 / 1000 , \log P + 2\log\Delta\le q\ell/64,\qquad K\sum_{u\ge\lceil q/8\rceil}\exp(-q\ell u/64) < 1/1000, log P + 2 log Δ ≤ q ℓ /64 , K u ≥ ⌈ q /8 ⌉ ∑ exp ( − q ℓ u /64 ) < 1/1000 , then R ^ ( F ) > Λ e ( F ) \widehat{R}(F) > \Lambda e(F) R ( F ) > Λ e ( F ) .
Proof. Suppose a host H H H with m ≤ Λ e ( F ) m \le\Lambda e(F) m ≤ Λ e ( F ) arrows F F F . Delete host vertices of degree above D D D , provisionally coloring their incident edges blue. A target image uses at most e ( F ) / 64 e(F)/64 e ( F ) /64 such edges. Apply Lemma 4.2 to the retained graph and color each unordered pair of distinct labels blue independently with probability p p p . Give the host edges their label-pair colors.
For a component F i F_i F i , put w ( v ) = deg F i ( v ) w(v) = \deg_{F_i}(v) w ( v ) = deg F i ( v ) . On a connected target set U U U of order u u u , deleting edges whose two endpoint labels repeat costs at most 2 τ ε u = q u / 128 ≤ w ( U ) / 128 2\tau\varepsilon u = qu/128 \le w(U)/128 2 τ ε u = q u /128 ≤ w ( U ) /128 edges. All remaining image edges have distinct label pairs. Thus a set with w ( U ) / 16 w(U)/16 w ( U ) /16 blue target edges has at least w ( U ) / 32 w(U)/32 w ( U ) /32 blue edges on distinct label pairs. For a fixed label map there are at most w ( U ) / 2 w(U)/2 w ( U ) /2 such pairs, so the probability of this event is at most
( 16 e p ) ⌈ w ( U ) / 32 ⌉ ≤ exp ( − q ℓ u / 32 ) . (16ep)^{\lceil w(U)/32\rceil} \le\exp(-q\ell u/32). ( 16 e p ) ⌈ w ( U ) /32 ⌉ ≤ exp ( − q ℓ u /32 ) . There are at most v ( F i ) Δ 2 u v(F_i)\Delta^{2u} v ( F i ) Δ 2 u connected u u u -sets and P u P^u P u label maps. The hypotheses therefore make the probability that F i F_i F i admits any such set of order u ≥ q / 8 u \ge q/8 u ≥ q /8 less than 1 / 1000 1/1000 1/1000 . The expected edge mass of these exceptional components is less than e ( F ) / 1000 e(F)/1000 e ( F ) /1000 .
Choose a relative-degree dense ball in one fixed component, using Lemma 4.1. If it has order u 0 u_0 u 0 , it contains at least q u 0 / 16 qu_0/16 q u 0 /16 edges, of which at least q u 0 / 32 qu_0/32 q u 0 /32 have distinct label pairs in any retained-host image. Its red probability is at most exp ( − p q u 0 / 32 ) = D − 8 u 0 \exp(-pqu_0/32) = D^{-8u_0} exp ( − pq u 0 /32 ) = D − 8 u 0 . An edge belongs to at most u 0 2 D u 0 − 2 u_0^2D^{u_0-2} u 0 2 D u 0 − 2 embeddings of this fixed connected graph. Since u 0 ≥ q / 8 ≥ 16 u_0 \ge q/8 \ge16 u 0 ≥ q /8 ≥ 16 and Λ ≤ D \Lambda\le D Λ ≤ D , the expected number of host edges in red copies of the ball is less than e ( F ) / 1000 e(F)/1000 e ( F ) /1000 .
Markov’s inequality gives a palette for which the latter support has at most e ( F ) / 64 e(F)/64 e ( F ) /64 edges and the exceptional component mass is at most e ( F ) / 4 e(F)/4 e ( F ) /4 . Recolor the support blue. Red F F F is impossible. A blue image of F F F , after removing the two provisionally recolored parts, loses at most e ( F ) / 32 e(F)/32 e ( F ) /32 edges. Some nonexceptional component retains at least three quarters of its edges. Its relative-degree dense ball would give an exceptional label map, a contradiction.
A quantitative bounded-component estimate
Proposition 4.4. Put B = 2 48 B = 2^{48} B = 2 48 . Let d , Δ , K d,\Delta,K d , Δ , K be positive integers with d ≤ Δ d \le\Delta d ≤ Δ , let Λ ≥ 1 \Lambda\ge1 Λ ≥ 1 , and set T = 1 + log ( 128 Λ ) T = 1 + \log(128\Lambda) T = 1 + log ( 128Λ ) . If
d ≥ exp ( 1 ) B T , log K ≤ d 8192 log d B T , (5) d \ge\exp(1)BT,\qquad\log K \le\frac{d}{8192}\log\frac{d}{BT}, \tag*{(5)} d ≥ exp ( 1 ) B T , log K ≤ 8192 d log B T d , (5) then every graph of minimum degree at least d d d , maximum degree at most Δ \Delta Δ , and component orders at most K K K satisfies R ^ ( G ) > Λ e ( G ) \widehat{R}(G) > \Lambda e(G) R ( G ) > Λ e ( G ) .
Proof. Fix Δ \Delta Δ , K K K and induct downward on d d d , with all eligible Λ \Lambda Λ quantified at each step. Write e = e ( G ) e=e(G) e = e ( G ) , and take a host with m ≤ Λ e m\leq\Lambda e m ≤ Λ e . Greedily remove minimum-degree-s s s subgraphs on at most K K K vertices, where s = 16 d s=16d s = 16 d , by peeling sets of at most K K K vertices with at least s s s times their order edges. Let W W W be their disjoint union. If the removal costs at least e / 4 e/4 e /4 edges, then e ( W ) ≥ s e / ( 8 Δ ) e(W)\geq se/(8\Delta) e ( W ) ≥ se / ( 8Δ ) , by charging deleted edges to vertices of W W W . This case implies s ≤ Δ s\leq\Delta s ≤ Δ . Set Λ 1 = 8 Δ Λ / s \Lambda_1=8\Delta\Lambda/s Λ 1 = 8ΔΛ/ s . Then
m ≤ Λ 1 e ( W ) , 1 + ln ( 128 Λ 1 Δ ) ≤ 2 T . (6) m\leq\Lambda_1e(W),\qquad1+\ln(128\Lambda_1\Delta)\leq2T. \tag*{(6)} m ≤ Λ 1 e ( W ) , 1 + ln ( 128 Λ 1 Δ ) ≤ 2 T . (6)
Both parameter conditions hold at degree s s s and multiplier Λ 1 \Lambda_1 Λ 1 , since s = 16 d s=16d s = 16 d . The induction hypothesis gives a contradiction. If s > Δ s>\Delta s > Δ , this removal branch is impossible, so there is no need for a separate base case.
Otherwise peel the remaining graph to minimum degree q = ⌊ d / 4 ⌋ ≥ d / 5 q=\lfloor d/4\rfloor\geq d/5 q = ⌊ d /4 ⌋ ≥ d /5 , losing at most e / 2 e/2 e /2 additional edges. The residual target F F F has e ( F ) ≥ e / 4 e(F)\geq e/4 e ( F ) ≥ e /4 , maximum degree at most Δ \Delta Δ , component orders at most K K K , and every set of at most K K K vertices spans fewer than s s s times its order edges. The host budget is at most 4 Λ e ( F ) 4\Lambda e(F) 4Λ e ( F ) . Apply the palette obstruction in Lemma 4.3 with q q q replacing its minimum-degree parameter, τ = s \tau=s τ = s , and
D = ⌈ 512 Λ Δ ⌉ , ε = q 256 s ≥ 1 20480 , p = 256 ln D q . (7) D=\lceil512\Lambda\Delta\rceil,\qquad\varepsilon=\frac{q}{256s}\geq\frac{1}{20480},\qquad p=\frac{256\ln D}{q}. \tag*{(7)} D = ⌈ 512ΛΔ ⌉ , ε = 256 s q ≥ 20480 1 , p = q 256 ln D . (7)
Here ln ( D + 1 ) ≤ 2 T \ln(D+1)\leq2T ln ( D + 1 ) ≤ 2 T . As in that proof, the label count satisfies
ln P + 2 ln Δ ≤ ln K + 2 20 T ≤ d 640 ln d B T . (8) \ln P+2\ln\Delta\leq\ln K+2^{20}T\leq\frac{d}{640}\ln\frac{d}{BT}. \tag*{(8)} ln P + 2 ln Δ ≤ ln K + 2 20 T ≤ 640 d ln B T d . (8)
The first inequality uses P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12 / ε ⌉ P=(D^2+1)\lceil K(D+1)^{12/\varepsilon}\rceil P = ( D 2 + 1 ) ⌈ K ( D + 1 ) 12/ ε ⌉ . The second follows from the hypotheses and B = 2 48 B=2^{48} B = 2 48 . Put ℓ = ln ( d / ( B T ) ) ≥ 1 \ell=\ln(d/(BT))\geq1 ℓ = ln ( d / ( B T )) ≥ 1 . We have 16 exp ( 1 ) p ≤ B T / d 16\exp(1)p\leq BT/d 16 exp ( 1 ) p ≤ B T / d , so for a connected target set of order u ≥ q / 8 u\geq q/8 u ≥ q /8 and any fixed label map, the blue tail is at most exp ( − q u ℓ / 32 ) ≤ exp ( − d u ℓ / 160 ) \exp(-qu\ell/32)\leq\exp(-du\ell/160) exp ( − q u ℓ /32 ) ≤ exp ( − d u ℓ /160 ) . The probability of a bad component is at most
K ∑ u ≥ q / 8 exp ( − d u ℓ / 320 ) < 1 / 1000. (9) K\sum_{u\geq q/8}\exp(-du\ell/320)<1/1000. \tag*{(9)} K u ≥ q /8 ∑ exp ( − d u ℓ /320 ) < 1/1000. (9)
The displayed palette-size upper bound is stronger than what the last inequality needs. Also, a fixed red dense relative-degree ball on u 0 ≥ q / 8 u_0\geq q/8 u 0 ≥ q /8 vertices has red probability at most D − 8 u 0 D^{-8u_0} D − 8 u 0 per embedding, by the same count of distinct label pairs after discarding repeated-label endpoint pairs. The expected red-copy support is at most m u 0 2 D u 0 − 2 D − 8 u 0 < e ( F ) / 1000 mu_0^2D^{u_0-2}D^{-8u_0}<e(F)/1000 m u 0 2 D u 0 − 2 D − 8 u 0 < e ( F ) /1000 , since m / e ( F ) ≤ 4 Λ ≤ D m/e(F)\leq4\Lambda\leq D m / e ( F ) ≤ 4Λ ≤ D . The alteration and blue contradiction from the sparse-collision palette proof now apply without change. This closes the induction.
Local sparsity reduction
Proposition 4.5. Fix A A A , B B B , M ≥ 1 M\geq1 M ≥ 1 . Suppose G G G has minimum degree at least d d d and maximum degree at most d B d^B d B . Let H H H be a host with H → G H\to G H → G and e ( H ) ≤ M d e ( G ) e(H)\leq Md\,e(G) e ( H ) ≤ M d e ( G ) . For sufficiently large d d d there is a subgraph F F F with at least e ( G ) / 4 e(G)/4 e ( G ) /4 edges, minimum degree at least q = ⌊ d / 4 ⌋ q=\lfloor d/4\rfloor q = ⌊ d /4 ⌋ , maximum degree at most d B d^B d B , and
e F ( U ) ≤ C A , B log q ∣ U ∣ ( ∣ U ∣ ≤ q A ) . (10) e_F(U)\leq C_{A,B}\log q\lvert U\rvert\qquad(\lvert U\rvert\leq q^A). \tag*{(10)} e F ( U ) ≤ C A , B log q ∣ U ∣ (∣ U ∣ ≤ q A ) . (10) The same host satisfies H → F H\to F H → F and has at most 20 M d q e ( F ) 20Md\,q\,e(F) 20 M d q e ( F ) edges. In particular, the polynomial maximum-degree reduction may also impose this local density condition.
Proof. Set K = ⌈ d A + 1 ⌉ K=\lceil d^{A+1}\rceil K = ⌈ d A + 1 ⌉ and s = ⌈ C log d ⌉ s=\lceil C\log d\rceil s = ⌈ C log d ⌉ , where C = C ( A , B ) C=C(A,B) C = C ( A , B ) is sufficiently large. Whenever a current vertex set of order at most K K K spans at least s s s times its order edges, peel that subgraph to a nonempty core of minimum degree at least s s s . Remove its vertices from the current graph and record the core. The recorded cores are disjoint.
If these removals delete at least e ( G ) / 4 e(G)/4 e ( G ) /4 edges, their union W W W has e ( W ) ≥ s e ( G ) / ( 8 d B ) e(W)\ge se(G)/(8d^{B}) e ( W ) ≥ se ( G ) / ( 8 d B ) , because at least e ( G ) / ( 4 d B ) e(G)/(4d^{B}) e ( G ) / ( 4 d B ) vertices were removed. Apply the quantitative bounded-component estimate with degree parameter s s s , maximum degree d B d^{B} d B , order bound K K K , and multiplier d B + 3 d^{B+3} d B + 3 . In that estimate T = O B ( log d ) T=O_{B}(\log d) T = O B ( log d ) and log K = O A ( log d ) \log K=O_{A}(\log d) log K = O A ( log d ) . Taking C C C sufficiently large verifies both hypotheses. It follows that
R ^ ( G ) ≥ R ^ ( W ) > d B + 3 e ( W ) ≥ s d 3 8 e ( G ) > M d e ( G ) , (11) \widehat{R}(G)\ge\widehat{R}(W)>d^{B+3}e(W)\ge\frac{sd^{3}}{8}e(G)>Md\,e(G), \tag*{(11)} R ( G ) ≥ R ( W ) > d B + 3 e ( W ) ≥ 8 s d 3 e ( G ) > M d e ( G ) , (11)
a contradiction for large d d d . Otherwise at least 3 e ( G ) / 4 3e(G)/4 3 e ( G ) /4 edges remain. Peel vertices of current degree below q q q . Since v ( G ) ≤ 2 e ( G ) / d v(G)\le2e(G)/d v ( G ) ≤ 2 e ( G ) / d , this removes at most e ( G ) / 2 e(G)/2 e ( G ) /2 more edges. The resulting F F F has at least e ( G ) / 4 e(G)/4 e ( G ) /4 edges and inherits the maximum degree bound. Every remaining set of at most K K K vertices has fewer than s s s times its order edges. Since q A ≤ K q^{A}\le K q A ≤ K and log d = O ( log q ) \log d=O(\log q) log d = O ( log q ) , the claimed density bound follows. Since F ⊆ G F\subseteq G F ⊆ G and H → G H\to G H → G , we have H → F H\to F H → F . Finally d ≤ 5 q d\le5q d ≤ 5 q and e ( G ) ≤ 4 e ( F ) e(G)\le4e(F) e ( G ) ≤ 4 e ( F ) .
Entropy of connected component types
Counting with a spanning forest
Lemma 5.1. Let F F F have n n n vertices. Choose a rooted spanning forest of F F F with k k k rooted components. For each vertex u u u , let s u s_u s u denote its number of children. Write S = ∑ u s u = n − k S=\sum_u s_u=n-k S = ∑ u s u = n − k and B = ∑ u : s u > 0 s u log 2 s u B=\sum_{u:s_u>0}s_u\log_2s_u B = ∑ u : s u > 0 s u log 2 s u . Assume S > 0 S>0 S > 0 . In a host with N N N vertices and m m m edges, the number of embeddings of the labeled F F F is at most
N k ( 2 m / S ) S 2 B . (12) N^k(2m/S)^S2^B. \tag*{(12)} N k ( 2 m / S ) S 2 B . (12) Proof. Independently choose each root image uniformly in the host. Traverse each rooted tree with parents preceding children, and choose each child image uniformly among the neighbors of the previously chosen parent image. An attempt fails if an isolated parent needs a child. The process permits collisions and ignores nonforest edges, so each true embedding ϕ \phi ϕ is an outcome of probability
N − k ∏ u : s u > 0 deg H ( ϕ ( u ) ) − s u . (13) N^{-k}\prod_{u:s_u>0}\deg_H(\phi(u))^{-s_u}. \tag*{(13)} N − k u : s u > 0 ∏ deg H ( ϕ ( u ) ) − s u . (13) For such an embedding, ∑ u : s u > 0 deg H ( ϕ ( u ) ) ≤ 2 m \sum_{u:s_u>0}\deg_H(\phi(u))\le2m ∑ u : s u > 0 deg H ( ϕ ( u )) ≤ 2 m by injectivity. The weighted arithmetic-geometric mean inequality with weights s u / S s_u/S s u / S gives
∏ u : s u > 0 deg H ( ϕ ( u ) ) s u ≤ ( 2 m / S ) S ∏ u : s u > 0 s u s u . (14) \prod_{u:s_u>0}\deg_H(\phi(u))^{s_u}\le(2m/S)^S\prod_{u:s_u>0}s_u^{s_u}. \tag*{(14)} u : s u > 0 ∏ deg H ( ϕ ( u ) ) s u ≤ ( 2 m / S ) S u : s u > 0 ∏ s u s u . (14) Summing the resulting lower bound on the probability of each distinct embedding proves the count.
A biased forest entropy bound
Proposition 5.2. Fix constants A , B ≥ 1 A, B \ge1 A , B ≥ 1 . Let G G G have minimum degree at least d d d , maximum degree at most d B d^B d B , edge count e e e , and r r r connected components. Write t i t_i t i for the multiplicities of its distinct component types and w i = t i / r w_i=t_i/r w i = t i / r . Use natural logarithms and write H ( w ) = − ∑ i w i ln w i \mathcal{H}(w)=-\sum_i w_i\ln w_i H ( w ) = − ∑ i w i ln w i . There is a constant C A , B C_{A,B} C A , B such that for all sufficiently large d d d ,
r H ( w ) ≤ e ( ln d − ln ln d − C A , B ) ⟹ R ^ ( G ) > d A e . (15) r\mathcal{H}(w)\le e(\ln d-\ln\ln d-C_{A,B})\quad\Longrightarrow\quad\widehat{R}(G)>d^A e. \tag*{(15)} r H ( w ) ≤ e ( ln d − ln ln d − C A , B ) ⟹ R ( G ) > d A e . (15)
There is no expansion, order, or component-size regularity assumption. For pairwise nonisomorphic d d d -regular components of one order k k k , the condition is ln r ≤ ( d k / 2 ) ( ln d − ln ln d − C A , B ) \ln r\le(dk/2)(\ln d-\ln\ln d-C_{A,B}) ln r ≤ ( d k /2 ) ( ln d − ln ln d − C A , B ) .
Proof. Red avoidance and full blue images.
Write Λ = d A \Lambda=d^A Λ = d A , η = ( ln d ) − 2 \eta=(\ln d)^{-2} η = ( ln d ) − 2 , and D = ⌈ 2 Λ Δ ( G ) / η ⌉ D=\lceil2\Lambda\Delta(G)/\eta\rceil D = ⌈ 2ΛΔ ( G ) / η ⌉ . Take any host H H H with m ≤ Λ e m\le\Lambda e m ≤ Λ e edges and delete its vertices of degree above D D D , leaving J J J . At most η e \eta e η e edges of any full target embedding have an endpoint in the removed set.
Color retained edges independently blue with probability p = C 0 ln D / d p=C_0\ln D/d p = C 0 ln D / d , for sufficiently large absolute C 0 C_0 C 0 . Fix one target component F F F of order k 0 k_0 k 0 and edge count a 0 ≥ d k 0 / 2 a_0\ge dk_0/2 a 0 ≥ d k 0 /2 . Use a red bad event for every embedding of F F F in J J J . Give it local lemma weight x = exp ( − p a 0 / 2 ) x=\exp(-pa_0/2) x = exp ( − p a 0 /2 ) . A retained edge lies in at most k 0 2 D k 0 − 2 k_0^2D^{k_0-2} k 0 2 D k 0 − 2 such events by an anchored spanning tree. Hence their weight sum per retained edge is at most q = D − 5 d q=D^{-5d} q = D − 5 d for large d d d , taking C 0 C_0 C 0 large enough. The asymmetric local lemma applies since a red event has probability at most x 2 x^2 x 2 and its dependency product is at least exp ( − 2 q a 0 ) ≥ x \exp(-2qa_0)\ge x exp ( − 2 q a 0 ) ≥ x .
Condition on all red events being avoided. For any fixed set of a ′ a' a ′ retained edges, the conditional probability that they are all blue is at most
p a ′ exp ( 2 q a ′ ) . (16) p^{a'}\exp(2qa'). \tag*{(16)} p a ′ exp ( 2 q a ′ ) . (16)
This is the standard conditional local lemma inequality, using the dependency product over red events touching those a ′ a' a ′ variables. Color every removed host edge blue. A full target embedding into H H H has at least ( 1 − η ) e (1-\eta)e ( 1 − η ) e retained edges, so its probability of being blue under the conditioned coloring is at most ( p exp ( 2 q ) ) ( 1 − η ) e (p\exp(2q))^{(1-\eta)e} ( p exp ( 2 q ) ) ( 1 − η ) e .
Count full embeddings before the deletion.
Discard original host isolates, which cannot be used by an embedding. Choose a rooted spanning forest of G G G and put n = v ( G ) n=v(G) n = v ( G ) and s = n − r s=n-r s = n − r . By Lemma 5.1 , the number of distinct target edge-image sets in H H H is at most
( 2 m ) r ( 2 m / s ) s Δ ( G ) s ∏ i t i ! . (17) \frac{(2m)^r(2m/s)^s\Delta(G)^s}{\prod_i t_i!}. \tag*{(17)} ∏ i t i ! ( 2 m ) r ( 2 m / s ) s Δ ( G ) s . (17)
Each edge-image set has at least ∏ i t i ! \prod_i t_i! ∏ i t i ! embeddings by permuting identical components. Counting in H H H instead of J J J keeps the original spanning forest and its r r r roots. There is no need to count the extra connected fragments produced by the deletion.
The logarithm of this expression is at most
r H ( w ) + r ln ( 2 exp ( 1 ) m / r ) + s ln ( 2 m / s ) + s ln Δ ( G ) = r H ( w ) + O A , B ( e ln d / d ) . (18) r\mathcal{H}(w)+r\ln(2\exp(1)m/r)+s\ln(2m/s)+s\ln\Delta(G)=r\mathcal{H}(w)+O_{A,B}(e\ln d/d). \tag*{(18)} r H ( w ) + r ln ( 2 exp ( 1 ) m / r ) + s ln ( 2 m / s ) + s ln Δ ( G ) = r H ( w ) + O A , B ( e ln d / d ) . (18)
For the estimate, n ≤ 2 e / d n\le2e/d n ≤ 2 e / d and r ≤ n / ( d + 1 ) r\le n/(d+1) r ≤ n / ( d + 1 ) by minimum degree. The map x ↦ x ln ( 2 exp ( 1 ) Λ e / x ) x\mapsto x\ln(2\exp(1)\Lambda e/x) x ↦ x ln ( 2 exp ( 1 ) Λ e / x ) is increasing on [ 0 , 2 e / d ] [0,2e/d] [ 0 , 2 e / d ] . Bounding both the root and nonroot terms at 2 e / d 2e/d 2 e / d gives the stated estimate, and s ln Δ ( G ) = O B ( e ln d / d ) s\ln\Delta(G)=O_B(e\ln d/d) s ln Δ ( G ) = O B ( e ln d / d ) .
Since D D D is polynomial in d d d , ln ( 1 / p ) ≥ ln d − ln ln d − O A , B ( 1 ) \ln(1/p)\ge\ln d-\ln\ln d-O_{A,B}(1) ln ( 1/ p ) ≥ ln d − ln ln d − O A , B ( 1 ) . The logarithm of the expected number of full blue target edge-image sets in the conditioned coloring is therefore at most
r H ( w ) + O A , B ( e ln d / d ) − ( 1 − η ) e ( ln ( 1 / p ) − 2 q ) < 0 (19) r\mathcal{H}(w)+O_{A,B}(e\ln d/d)-(1-\eta)e(\ln(1/p)-2q)<0 \tag*{(19)} r H ( w ) + O A , B ( e ln d / d ) − ( 1 − η ) e ( ln ( 1/ p ) − 2 q ) < 0 (19)
under the stated condition with sufficiently large C A , B C_{A,B} C A , B . There is an outcome with no blue target. There is also no red target, because all its red edges would be retained and the fixed component F F F is absent in red.
Low-entropy classes have small total mass
Lemma 5.3. Fix M M M , B ≥ 1 B\ge1 B ≥ 1 and L > 1 L>1 L > 1 . Suppose G G G has minimum degree at least d d d and maximum degree at most d B d^{B} d B . Let H H H be a host with H → G H\to G H → G and e ( H ) ≤ M d e ( G ) e(H)\le Md e(G) e ( H ) ≤ M d e ( G ) . For some K 0 = K 0 ( L , B ) K_0=K_0(L,B) K 0 = K 0 ( L , B ) , select in each order-and-edge-count class ( k , a ) (k,a) ( k , a ) any collection of at most
exp ( a ( log d − log log d − K 0 ) ) (20) \exp(a(\log d-\log\log d-K_0)) \tag*{(20)} exp ( a ( log d − log log d − K 0 )) (20) distinct component types. The union of all their occurrences in G G G has fewer than M d 1 − L e ( G ) Md^{1-L}e(G) M d 1 − L e ( G ) edges.
Proof. Let W W W be the union of these selected components. The claimed bound holds if W W W is empty. Otherwise, the entropy of its component types splits into the entropy of the class and the conditional type entropy inside the class. The conditional term, multiplied by the number of components, is at most e ( W ) ( ln d − ln ln d − K 0 ) e(W)(\ln d-\ln\ln d-K_0) e ( W ) ( ln d − ln ln d − K 0 ) . The class term is only O ( e ( W ) / d ) O(e(W)/d) O ( e ( W ) / d ) . For example use a probability distribution on possible classes assigning mass 2 − k 2^{-k} 2 − k to order k k k and dividing that mass uniformly across integers 0 ≤ a ≤ ⌊ Δ k / 2 ⌋ 0\le a\le\lfloor\Delta k/2\rfloor 0 ≤ a ≤ ⌊ Δ k /2 ⌋ . Cross entropy bounds the class entropy by the mean of k ln 2 + ln ( 1 + Δ k ) k\ln2+\ln(1+\Delta k) k ln 2 + ln ( 1 + Δ k ) over components. Its sum is O ( v ( W ) ) O(v(W)) O ( v ( W )) because each order is at least d + 1 d+1 d + 1 and Δ \Delta Δ is polynomial in d d d . Apply Proposition 5.2 with multiplier d L d^L d L . For K 0 K_0 K 0 sufficiently large, R ^ ( W ) > d L e ( W ) \widehat{R}(W)>d^Le(W) R ( W ) > d L e ( W ) . Since W ⊆ G W\subseteq G W ⊆ G and H → G H\to G H → G , we have H → W H\to W H → W . Thus d L e ( W ) < R ^ ( W ) ≤ e ( H ) ≤ M d e ( G ) d^Le(W)<\widehat{R}(W)\le e(H)\le Mde(G) d L e ( W ) < R ( W ) ≤ e ( H ) ≤ M d e ( G ) , which gives the claimed mass bound.
A dense witness
Lemma 5.4. For a finite simple graph G G G with e = e ( G ) > 0 e=e(G)>0 e = e ( G ) > 0 and maximum degree Δ \Delta Δ , put
s ( G ) = max F ⊆ G , v ( F ) > 0 e ( F ) / v ( F ) . (21) s(G)=\max_{\substack{F\subseteq G,\,v(F)>0}} e(F)/v(F). \tag*{(21)} s ( G ) = F ⊆ G , v ( F ) > 0 max e ( F ) / v ( F ) . (21) There is an absolute constant c > 0 c>0 c > 0 such that
R ^ ( G ) > c s ( G ) ln ( Δ + 1 ) e . (22) \widehat{R}(G)>c\frac{s(G)}{\ln(\Delta+1)}e. \tag*{(22)} R ( G ) > c ln ( Δ + 1 ) s ( G ) e . (22) In particular one dense subgraph, even one carrying a very small fraction of the target edges, can force a larger size Ramsey multiplier for the entire graph.
Proof. Choose a connected subgraph F F F of order k k k and edge count a a a with a / k = s ( G ) a/k=s(G) a / k = s ( G ) , by taking a maximum-density subgraph and then one of its densest connected components. Write s = s ( G ) s=s(G) s = s ( G ) . Put Λ = c s / ln ( Δ + 1 ) \Lambda=cs/\ln(\Delta+1) Λ = cs / ln ( Δ + 1 ) . If Λ < 1 \Lambda<1 Λ < 1 , the bound follows from R ^ ( G ) ≥ e \widehat{R}(G)\ge e R ( G ) ≥ e . Otherwise suppose H H H has at most Λ e \Lambda e Λ e edges, and delete its vertices of degree above D = ⌈ 16 Λ Δ ⌉ D=\lceil16\Lambda\Delta\rceil D = ⌈ 16ΛΔ ⌉ . In any full target copy this deletion loses at most e / 8 e/8 e /8 target edges. Since s ≤ Δ / 2 s\le\Delta/2 s ≤ Δ/2 , we have ln D = O ( ln ( Δ + 1 ) ) \ln D=O(\ln(\Delta+1)) ln D = O ( ln ( Δ + 1 )) uniformly.
Independently color the retained host edges blue with probability p = 16 ln D / s p=16\ln D/s p = 16 ln D / s and red otherwise. A sufficiently small absolute c c c ensures p < 1 / 2 p<1/2 p < 1/2 and 2 p Λ ≤ 1 / 16 2p\Lambda\le1/16 2 p Λ ≤ 1/16 . Take a red bad event for every embedding of F F F into the retained graph. At a fixed host edge there are at most k 2 D k − 2 k^2D^{k-2} k 2 D k − 2 events, by spanning-tree traversal from a pinned preimage edge. Give each weight exp ( − p a / 2 ) = D − 8 k \exp(-pa/2)=D^{-8k} exp ( − p a /2 ) = D − 8 k . Its probability is at most the square of its weight, and the sum of weights at a host edge is at most D − 5 k D^{-5k} D − 5 k , using k 2 ≤ D 2 k k^2 \le D^{2k} k 2 ≤ D 2 k . The asymmetric local lemma therefore excludes all red events, with conditional blue probability at each edge at most 2 p 2p 2 p . For example its required weight sum is negligible compared with p p p , since Λ ≥ 1 \Lambda\ge1 Λ ≥ 1 implies s ≥ c − 1 ln ( Δ + 1 ) s \ge c^{-1}\ln(\Delta+ 1) s ≥ c − 1 ln ( Δ + 1 ) and D ≥ 16 Δ ≥ 32 s D \ge16\Delta\ge32s D ≥ 16Δ ≥ 32 s .
Fix an outcome with no red F F F and at most e / 16 e/16 e /16 blue retained edges, which exists by the conditional expectation. Color all removed edges blue. Red G G G would contain red F F F . A blue copy of the full G G G must retain at least 7 e / 8 7e/8 7 e /8 blue edges, impossible. This proves the bound.
Dense blocks and the entropy threshold
Dense-block extraction
Proposition 6.1. Fix A , B ≥ 1 A, B \ge1 A , B ≥ 1 . There is c = c ( A , B ) > 0 c = c(A, B) > 0 c = c ( A , B ) > 0 such that, for sufficiently large d d d , every graph G G G with δ ( G ) ≥ d \delta(G) \ge d δ ( G ) ≥ d , Δ ( G ) ≤ d A \Delta(G) \le d^A Δ ( G ) ≤ d A and e G ( U ) ≤ B log d ∣ U ∣ e_G(U) \le B \log d |U| e G ( U ) ≤ B log d ∣ U ∣ for ∣ U ∣ ≤ 2 ⌈ ( log d ) 4 ⌉ |U| \le2\lceil(\log d)^4\rceil ∣ U ∣ ≤ 2 ⌈( log d ) 4 ⌉ satisfies
R ^ ( G ) > c d log log d e ( G ) . (23) \widehat{R}(G) > \frac{cd}{\log\log d}e(G). \tag*{(23)} R ( G ) > log log d c d e ( G ) . (23)
Proof. Fix A , B ≥ 1 A, B \ge1 A , B ≥ 1 . Suppose G G G has minimum degree at least d d d , maximum degree Δ ≤ d A \Delta\le d^A Δ ≤ d A , and every set of order at most 2 ℓ 2\ell 2 ℓ , where ℓ = ⌈ ( ln d ) 4 ⌉ \ell= \lceil(\ln d)^4\rceil ℓ = ⌈( ln d ) 4 ⌉ , has density at most σ = B ln d \sigma= B\ln d σ = B ln d . We show the lower bound with Λ = c A , B d / ln ln d \Lambda= c_{A,B}d/\ln\ln d Λ = c A , B d / ln ln d . All estimates are for sufficiently large d d d with A , B , c A , B A, B, c_{A,B} A , B , c A , B fixed.
Assume a host H H H arrows G G G with m ≤ Λ e m \le\Lambda e m ≤ Λ e , where e = e ( G ) e = e(G) e = e ( G ) . Lemma 5.4 gives s ( G ) = O A ( Λ ln d ) s(G) = O_A(\Lambda\ln d) s ( G ) = O A ( Λ ln d ) for the hereditary target density. Prune host vertices of original degree above D = ⌈ 16 Λ Δ ⌉ D = \lceil16\Lambda\Delta\rceil D = ⌈ 16ΛΔ ⌉ , and edges with both original endpoint degrees above P = ⌈ 32 Λ s ( G ) ⌉ P = \lceil32\Lambda s(G)\rceil P = ⌈ 32Λ s ( G )⌉ . As in Lemma 5.3 , in any copy of G G G these two removals cost at most e / 8 e/8 e /8 and e / 16 e/16 e /16 target edges. The retained graph J J J has maximum degree at most D D D and each induced set of order k k k spans at most P k Pk P k edges.
Greedily find two disjoint sets of ℓ \ell ℓ vertices having at least ℓ 2 / 4 \ell^2/4 ℓ 2 /4 edges between them, assign all currently present edges between them to a block, and delete those edges from the current graph. Repeat until no such pair remains. The union K K K of the assigned blocks has an edge partition into blocks of size at most ℓ 2 \ell^2 ℓ 2 , with supports of size at most 2 ℓ 2\ell 2 ℓ . Supports may overlap. The residual J − K J-K J − K has no such dense pair. Each block contributes at most 2 σ ℓ 2\sigma\ell 2 σ ℓ edges to any copy of G G G , by local target sparsity. The number of blocks is at most 4 m / ℓ 2 4m/\ell^2 4 m / ℓ 2 , so their total target capacity is at most 8 σ m / ℓ 8\sigma m/\ell 8 σ m / ℓ .
A fixed component with mostly single uses of blocks.
By the low-entropy mass estimate in Lemma 5.3 with polynomial multiplier d 2 d^2 d 2 , some class of components of order k k k and edge count a a a has at least exp ( a ( ln d − ln ln d − O A ( 1 ) ) ) \exp(a(\ln d-\ln\ln d-O_A(1))) exp ( a ( ln d − ln ln d − O A ( 1 ))) distinct types. Here a ≥ d k / 2 a \ge dk/2 a ≥ d k /2 and P k / a ≥ 32 Λ Pk/a \ge32\Lambda P k / a ≥ 32Λ . Set θ = 1 / 64 \theta= 1/64 θ = 1/64 . Call a copy of a type in the class bad if at least θ a / 2 \theta a/2 θ a /2 of its edges occur in blocks containing two or more of its edges. Such a copy contains at least θ a / 6 \theta a/6 θ a /6 disjoint same-block edge pairs, by grouping the edges into pairs inside each block. Put j = ⌊ θ a / 12 ⌋ j = \lfloor\theta a/12\rfloor j = ⌊ θ a /12 ⌋ .
On a fixed connected image set of order k k k , the available edges number at most P k Pk P k and same-block edge pairs number at most P k ℓ 2 Pk\ell^2 P k ℓ 2 . Thus bad subsets of a a a edges number at most
( P k ℓ 2 j ) ( P k a − 2 j ) . (24) \binom{Pk\ell^2}{j}\binom{Pk}{a-2j}. \tag*{(24)} ( j P k ℓ 2 ) ( a − 2 j P k ) . (24)
This bound allows extra choices with overlapping pairs. The logarithm is at most
a ln ( P k / a ) + O θ ( a ) − j ln ( P k / ( a ℓ 2 ) ) . (25) a\ln(Pk/a)+O_\theta(a)-j\ln\left(Pk/(a\ell^2)\right). \tag*{(25)} a ln ( P k / a ) + O θ ( a ) − j ln ( P k / ( a ℓ 2 ) ) . (25)
This follows from the binomial estimate with j / a j/a j / a bounded below by a fixed positive constant. We have P k / a = O A ( d ln d ) Pk/a = O_A(d\ln d) P k / a = O A ( d ln d ) , and P k / ( a ℓ 2 ) ≥ 32 Λ / ℓ 2 = d 1 − o ( 1 ) Pk/(a\ell^2) \ge32\Lambda/\ell^2 = d^{1-o(1)} P k / ( a ℓ 2 ) ≥ 32Λ/ ℓ 2 = d 1 − o ( 1 ) . The penalty is therefore Ω θ ( a ln d ) \Omega_\theta(a\ln d) Ω θ ( a ln d ) . For copies through a fixed edge there are at most D 2 k D^{2k} D 2 k connected image sets, by spanning-tree walks, with logarithm o ( a ) o(a) o ( a ) . The ratio of the resulting bad type count to the number of distinct types is exp ( − Ω θ ( a ln d ) ) \exp(-\Omega_{\theta}(a\ln d)) exp ( − Ω θ ( a ln d )) . Averaging over types gives one fixed component F F F whose bad-copy edge support has at most m exp ( − Ω θ ( a ln d ) ) < e / 16 m\exp(-\Omega_{\theta}(a\ln d))<e/16 m exp ( − Ω θ ( a ln d )) < e /16 edges. Delete that support from J J J to obtain J 1 J_1 J 1 , and put J 0 = J 1 − K J_0=J_1-K J 0 = J 1 − K . Every copy of F F F in J 1 J_1 J 1 is good in the original block partition, and J 0 J_0 J 0 has no dense pair of the specified form.
Red copies using many block edges.
Mark each block independently with probability p K = L K ln D / d p_K=L_K\ln D/d p K = L K ln D / d , for a sufficiently large absolute constant L K L_K L K . A copy of F F F using at least θ a \theta a θ a block edges uses at least θ a / 2 \theta a/2 θ a /2 distinct blocks, by goodness. Use a red event for each such embedding, requiring all the blocks it uses to be unmarked. The number of events at one block has logarithm O ( k ln D ) O(k\ln D) O ( k ln D ) . To bound it, pin an actual edge in the block and a target edge and traverse a fixed spanning tree of F F F in the degree-D D D graph. The factor ℓ 2 \ell^2 ℓ 2 for the choice of the actual edge is harmless. Give the event weight exp ( − p K θ a / 4 ) \exp(-p_K\theta a/4) exp ( − p K θ a /4 ) . Its probability is at most the square of its weight. For sufficiently large L K L_K L K the weight sum at a block is at most D − k D^{-k} D − k , and an event uses at most a a a blocks. The asymmetric local lemma applies and makes each conditional mark probability at most 2 p K 2p_K 2 p K . Consequently the conditional expected marked block capacity is at most 16 p K σ m / ℓ = o ( e ) 16p_K\sigma m/\ell=o(e) 16 p K σ m / ℓ = o ( e ) .
Red copies using few block edges.
For a copy ϕ \phi ϕ using fewer than θ a \theta a θ a block edges, call a role exceptional if more than one eighth of its incident target edges map into K K K . The sum of the degrees of exceptional roles is at most 16 θ a 16\theta a 16 θ a . The other roles are called ordinary.
There is a connected seed T T T of at most L S k ln ( D + 1 ) / d L_Sk\ln(D+1)/d L S k ln ( D + 1 ) / d vertices in F F F with a flagged subset S ⊆ T S\subseteq T S ⊆ T having the following property. For every role v v v outside T T T , the set S ∩ N F ( v ) S\cap N_F(v) S ∩ N F ( v ) is nonempty. For every host vertex x x x adjacent in J 0 J_0 J 0 to some vertex of ϕ ( N F ( v ) ) \phi(N_F(v)) ϕ ( N F ( v )) , the fraction of vertices adjacent to x x x among ϕ ( S ∩ N F ( v ) ) \phi(S\cap N_F(v)) ϕ ( S ∩ N F ( v )) differs from the fraction among ϕ ( N F ( v ) ) \phi(N_F(v)) ϕ ( N F ( v )) by at most 1 / 16 1/16 1/16 . Adjacency here is measured in J 0 J_0 J 0 .
To see this, initially sample S S S by including each target vertex independently with probability α = L ln ( D + 1 ) / d \alpha=L\ln(D+1)/d α = L ln ( D + 1 ) / d . For each role v v v of degree d v ≥ d d_v\ge d d v ≥ d , the sampled neighbor count differs from α d v \alpha d_v α d v by at most α d v / 64 \alpha d_v/64 α d v /64 except with probability 2 exp ( − Ω ( α d v ) ) 2\exp(-\Omega(\alpha d_v)) 2 exp ( − Ω ( α d v )) . For each candidate x x x as above, the sampled count of its adjacent neighbors similarly differs from its mean by at most α d v / 64 \alpha d_v/64 α d v /64 with probability of failure at most 2 exp ( − Ω ( α d v ) ) 2\exp(-\Omega(\alpha d_v)) 2 exp ( − Ω ( α d v )) , by the additive binomial tail. On success the ratio error is at most 2 / 63 < 1 / 16 2/63<1/16 2/63 < 1/16 . The candidate count is at most D 2 D^2 D 2 by bounded host degrees. Taking L L L large makes the total failure probability at a role at most 1 / d 1/d 1/ d . Add all failed roles to S S S , leaving the original sampled roles flagged. The resulting set dominates F F F . A connected graph with a dominating set has a connected superset of that set with at most three times its size. Indeed the graph on the dominators joining pairs at distance at most three is connected, by assigning every vertex a dominator and following paths in F F F . Use the paths along a spanning tree of that auxiliary graph. The expected number of original sampled and added failed roles is at most ( α + 1 / d ) k (\alpha+1/d)k ( α + 1/ d ) k , so an outcome of the required size exists. Added roles and connectors do not change the flagged sample.
Given the seed image, assign each role in T T T its singleton image list. At a role outside T T T , take the list of all host vertices adjacent in J 0 J_0 J 0 to at least three quarters of the flagged neighbor images. Every ordinary role has its image on the list. Every listed candidate sees at least 11 / 16 11/16 11/16 of the full actual neighbor image set, by the seed property. The list has size less than ℓ \ell ℓ . Otherwise select ℓ \ell ℓ candidates and remove those candidates from the full neighbor image set. This costs at most ℓ = o ( d v ) \ell=o(d_v) ℓ = o ( d v ) neighbors at each candidate. At least ℓ \ell ℓ neighbors remain. An averaging choice of ℓ \ell ℓ of them gives density at least 1 / 4 1/4 1/4 between these two disjoint ℓ \ell ℓ -sets in J 0 J_0 J 0 , a contradiction.
Enumerate the connected seed T T T , its flagged subset, its image in J 1 J_1 J 1 , the set of exceptional target roles, and an assignment of ordinary roles from their lists. Keep configurations that arise from a copy and a seed as above. At least a − 16 θ a − θ a ≥ a / 2 a-16\theta a-\theta a\ge a/2 a − 16 θ a − θ a ≥ a /2 edges join ordinary roles and have images in J 0 J_0 J 0 . These distinct edges are determined by the configuration. Independently mark each edge of J 0 J_0 J 0 with probability p 0 = L 0 ln ln d / d p_0=L_0\ln\ln d/d p 0 = L 0 ln ln d / d . Take a red event per configuration requiring those edges unmarked.
Through a fixed residual edge the number of such configurations has logarithm O A ( k ln ln d ) O_A(k\ln\ln d) O A ( k ln ln d ) . To anchor the count, choose the preimage of an endpoint of that edge. If it belongs to T T T , its image is pinned. Otherwise it passes the ordinary role’s list and is adjacent to the image of some flagged seed neighbor. Choose that role and one of at most D D D host neighbors for its image. There are at most 2 k 2 D 2k^2D 2 k 2 D choices for this anchor. The number of connected target seed sets of size at most L s k ln ( D + 1 ) / d L_s k\ln(D+1)/d L s k ln ( D + 1 ) / d containing the anchored role is at most ∑ u ≤ L s k ln ( D + 1 ) / d Δ 2 u \sum_{u\le L_s k\ln(D+1)/d}\Delta^{2u} ∑ u ≤ L s k l n ( D + 1 ) / d Δ 2 u , by spanning-tree walks. For each seed set, its rooted image count is at most D ∣ T ∣ − 1 D^{|T|-1} D ∣ T ∣ − 1 . Flags and exceptional-role sets cost at most 2 ∣ T ∣ + k 2^{|T|+k} 2 ∣ T ∣ + k , and ordinary image choices at most ℓ k \ell^k ℓ k . Combining gives the asserted estimate since D = d O A ( 1 ) D=d^{O_A(1)} D = d O A ( 1 ) and ln k = O ( k ) \ln k=O(k) ln k = O ( k ) . The asymmetric local lemma with weights exp ( − p 0 a / 4 ) \exp(-p_0a/4) exp ( − p 0 a /4 ) now applies for large L 0 L_0 L 0 depending only on A , B A,B A , B . In fact the weight sum at a variable is at most exp ( − k ln ln d ) \exp(-k\ln\ln d) exp ( − k ln ln d ) , while an event uses at most a a a variables and has probability at most the square of its weight. Conditional mark probabilities are at most 2 p 0 2p_0 2 p 0 .
Complete the coloring.
The two local-lemma experiments have disjoint variable sets. After conditioning on their respective avoidances, the expected sum of marked block capacity and marked residual edges is at most o ( e ) + 2 L 0 c A , B e o(e)+2L_0c_{A,B}e o ( e ) + 2 L 0 c A , B e . Choose c A , B c_{A,B} c A , B sufficiently small that some conditioned outcome has sum at most e / 8 e/8 e /8 . Color marked edges and all previously pruned edges blue, and everything else red. A red copy of G G G would give one of the forbidden red events for F F F . A blue copy could use at most 3 e / 16 + e / 16 3e/16+e/16 3 e /16 + e /16 of its edges in the pruned sets and at most e / 8 e/8 e /8 in the retained graph. This proves the claimed restricted bound.
The refined entropy threshold
Proposition 6.2. Fix constants A , M , B ≥ 1 A,M,B\ge1 A , M , B ≥ 1 . Let G G G have minimum degree at least d d d , maximum degree at most d A d^A d A , and density at most B ln d B\ln d B ln d on all sets of order at most 2 ⌈ ( ln d ) 6 ⌉ 2\lceil(\ln d)^6\rceil 2 ⌈( ln d ) 6 ⌉ . Write r r r for the number of connected components, t i t_i t i for the multiplicities of their distinct types, and w i = t i / r w_i=t_i/r w i = t i / r . For a fixed sufficiently large K = K A , M , B K=K_{A,M,B} K = K A , M , B and all sufficiently large d d d ,
r H ( w ) ≤ e ( G ) ( ln d − ln ln ln d − K ) ⟹ R ^ ( G ) > M d e ( G ) . (26) r\mathcal{H}(w)\le e(G)(\ln d-\ln\ln\ln d-K)\quad\Longrightarrow\quad\widehat{R}(G)>Mde(G). \tag*{(26)} r H ( w ) ≤ e ( G ) ( ln d − ln ln ln d − K ) ⟹ R ( G ) > M d e ( G ) . (26)
Proof. A sparse blue allowance on the extracted blocks. Suppose a host with m ≤ M d e m\le Mde m ≤ M d e arrows G G G , where e = e ( G ) e=e(G) e = e ( G ) . Follow Proposition 6.1, with Λ = M d \Lambda=Md Λ = M d , η = ( ln d ) − 2 \eta=(\ln d)^{-2} η = ( ln d ) − 2 , D = ⌈ 2 Λ Δ ( G ‾ ) / η ⌉ D=\lceil2\Lambda\Delta(\overline{G})/\eta\rceil D = ⌈ 2ΛΔ ( G ) / η ⌉ , P = ⌈ 2 Λ s ( G ) / η ⌉ P=\lceil2\Lambda s(G)/\eta\rceil P = ⌈ 2Λ s ( G ) / η ⌉ , and ℓ = ⌈ ( ln d ) 6 ⌉ \ell=\lceil(\ln d)^6\rceil ℓ = ⌈( ln d ) 6 ⌉ . The two pruning allowances each become η e \eta e η e . The hereditary target density bound still gives P = O A , M ( d 2 ( ln d ) 3 ) P=O_{A,M}(d^2(\ln d)^3) P = O A , M ( d 2 ( ln d ) 3 ) , and D D D remains polynomial. The high-diversity class exists by Lemma 5.3 with multiplier d 2 d^2 d 2 . The repeated-block bad copy count loses Ω ( a ln d ) \Omega(a\ln d) Ω ( a ln d ) from the exponent, whereas the change in P P P costs only O ( a ln ln d ) O(a\ln\ln d) O ( a ln ln d ) . Thus choose the fixed component F F F with bad-copy edge support at most η e \eta e η e .
The two red avoidance tests of the dense block proof apply with the same orders of mark probabilities. Their exponents use only the constant fraction thresholds and the anchored counts exp ( O ( k ln D ) ) \exp(O(k\ln D)) exp ( O ( k ln D )) for the block experiment and exp ( O ( k ln ln d ) ) \exp(O(k\ln\ln d)) exp ( O ( k ln ln d )) for the residual experiment. Conditional on avoiding the first family, the expected marked block target capacity is
O ( ( ln D / d ) ( B ln d ) m / ℓ ) = o ( η e ) . (27) O((\ln D/d)(B\ln d)m/\ell)=o(\eta e). \tag*{(27)} O (( ln D / d ) ( B ln d ) m / ℓ ) = o ( η e ) . (27)
Fix a block outcome with capacity at most η e \eta e η e . Its marks use variables disjoint from the residual red test. Count the remaining blue edges in a full embedding.
Run the residual edge experiment with independent probability p 0 = L 0 ln ln d / d p_0=L_0\ln\ln d/d p 0 = L 0 ln ln d / d . Condition on avoidance of its red events. The event weight sum at each edge is at most q = exp ( − k ln ln d ) q=\exp(-k\ln\ln d) q = exp ( − k ln ln d ) , with k = v ( F ) ≥ d + 1 k=v(F)\ge d+1 k = v ( F ) ≥ d + 1 . For any specified set of t t t residual edges, the conditional probability that all are blue is at most ( p 0 exp ( 2 q ) ) t (p_0\exp(2q))^t ( p 0 exp ( 2 q ) ) t , by the conditional local lemma. In any fixed full target image in the original host, at most 4 η e 4\eta e 4 η e edges can be blue through degree pruning, high-high pruning, bad-copy support, and the fixed block coloring together. Therefore a full blue image has probability at most ( p 0 exp ( 2 q ) ) ( 1 − 4 η ) e (p_0\exp(2q))^{(1-4\eta)e} ( p 0 exp ( 2 q ) ) ( 1 − 4 η ) e . This also bounds the probability if a specified image contains an unmarked block edge, in which case that probability is zero.
As in Proposition 5.2, the number of full edge-image sets in the original host is at most exp ( r H ( w ) + O M , A ( e ln d / d ) ) \exp(r\mathcal{H}(w)+O_{M,A}(e\ln d/d)) exp ( r H ( w ) + O M , A ( e ln d / d )) . The logarithm of the expected number of blue images is consequently at most
r H ( w ) + O M , A ( e ln d / d ) − ( 1 − 4 η ) e ( ln d − ln ln ln d − O A , M , B ( 1 ) ) . (28) r\mathcal{H}(w)+O_{M,A}(e\ln d/d)-(1-4\eta)e(\ln d-\ln\ln\ln d-O_{A,M,B}(1)). \tag*{(28)} r H ( w ) + O M , A ( e ln d / d ) − ( 1 − 4 η ) e ( ln d − ln ln ln d − O A , M , B ( 1 )) . (28)
For large fixed K K K this is negative under the displayed hypothesis. The conditioning precludes a red copy and there is an outcome with no blue copy, a contradiction.
Class consequence with a quantitative mass allowance.
Fix L > 1 L>1 L > 1 . The same proof excludes host multiplier d L d^L d L when restricted to low-entropy portions only if the extracted block capacity can be paid at that multiplier. At a fixed linear budget there is instead the following mass statement. For every 0 < μ ≤ 1 0<\mu\le1 0 < μ ≤ 1 fixed, select from each class ( k , a ) (k,a) ( k , a ) any set of at most exp ( a ( ln d − ln ln ln d − K ′ ) ) \exp(a(\ln d-\ln\ln\ln d-K')) exp ( a ( ln d − ln ln ln d − K ′ )) distinct types. For large enough K ′ K' K ′ depending on A A A , M M M , B B B , μ \mu μ , their union of components has edge mass less than μ e ( G ) \mu e(G) μ e ( G ) in a target with host budget M d e ( G ) Mde(G) M d e ( G ) . Otherwise the same host has edge budget at most ( M / μ ) d (M/\mu)d ( M / μ ) d times the selected mass, while the class entropy contribution is only O ( e ( G ) / d ) O(e(G)/d) O ( e ( G ) / d ) with the selected mass in place of e ( G ) e(G) e ( G ) , as in the universal entropy argument. Apply the theorem at M / μ M/\mu M / μ .
Targets with a narrow degree range
The near-regular estimate
Theorem 7.1. There is an absolute κ = 10 − 8 \kappa=10^{-8} κ = 1 0 − 8 such that, for every fixed A A A , M ≥ 1 M\ge1 M ≥ 1 and all sufficiently large d d d , every graph G G G satisfying
δ ( G ) ≥ d , Δ ( G ) ≤ A d ( log d ) κ (29) \delta(G)\ge d,\qquad\Delta(G)\le Ad(\log d)^\kappa \tag*{(29)} δ ( G ) ≥ d , Δ ( G ) ≤ A d ( log d ) κ (29) has R ^ ( G ) > M d e ( G ) \widehat{R}(G)>Mde(G) R ( G ) > M d e ( G ) .
Proof. Setup and two block scales. It suffices to prove the theorem assuming target density at most σ = B ln d \sigma=B\ln d σ = B ln d on sets of order at most 2 ⌈ d 1 / 4 ⌉ 2\lceil d^{1/4}\rceil 2 ⌈ d 1/4 ⌉ , for a fixed B B B . Indeed Proposition 4.5 either gives a polynomial lower bound on the original target or leaves a subtarget with at least a quarter of the edges, minimum degree ⌊ d / 4 ⌋ \lfloor d/4\rfloor ⌊ d /4 ⌋ , and logarithmic density on all sets up to a fixed polynomial cutoff. Its maximum degree is still at most A ′ ⌊ d / 4 ⌋ ( ln ⌊ d / 4 ⌋ ) κ A'\lfloor d/4\rfloor(\ln\lfloor d/4\rfloor)^\kappa A ′ ⌊ d /4 ⌋ ( ln ⌊ d /4 ⌋ ) κ with fixed A ′ A' A ′ . The theorem for that subtarget at a sufficiently large fixed multiplier gives the claimed lower bound on the original target.
Suppose H H H arrows G G G with m ≤ Λ e m\le\Lambda e m ≤ Λ e , where Λ = M d \Lambda=Md Λ = M d and e = e ( G ) e=e(G) e = e ( G ) . Write L = ln d L=\ln d L = ln d , Δ = Δ ( G ) \Delta=\Delta(G) Δ = Δ ( G ) , and D = ⌈ 16 Λ Δ ⌉ D=\lceil16\Lambda\Delta\rceil D = ⌈ 16ΛΔ ⌉ . Delete host vertices of degree above D D D , losing at most e / 8 e/8 e /8 edges in any target copy. Write J J J for the remaining host. It has maximum degree at most D D D and every set of order k k k has at most D k Dk D k edges. For sufficiently large d d d , d ≤ D ≤ d 3 d\le D\le d^3 d ≤ D ≤ d 3 .
First greedily extract the edges between any two disjoint sets of order ℓ 1 = ⌊ L 4 ⌋ \ell_1=\lfloor L^4\rfloor ℓ 1 = ⌊ L 4 ⌋ of current cross density at least ρ 1 = 1 / 4 \rho_1=1/4 ρ 1 = 1/4 . When none remain, repeat at order ℓ 2 = ⌈ d 1 / 4 ⌉ \ell_2=\lceil d^{1/4}\rceil ℓ 2 = ⌈ d 1/4 ⌉ and density ρ 2 = d − 1 / 8 \rho_2=d^{-1/8} ρ 2 = d − 1/8 . The assigned blocks have pairwise disjoint edge sets, with possibly overlapping supports. Let K K K be their union and J 0 = J − K J_0 = J - K J 0 = J − K . The residual graph has neither kind of dense rectangle. The sum of target capacities at scale i i i is at most 2 σ m / ( ρ i ℓ i ) 2\sigma m/(\rho_i\ell_i) 2 σ m / ( ρ i ℓ i ) , since each block contains at least ρ i ℓ i 2 \rho_i\ell_i^2 ρ i ℓ i 2 edges and contributes at most 2 σ ℓ i 2\sigma\ell_i 2 σ ℓ i edges to any target image.
Proposition 6.2 implies some class of connected components of order k k k and edge count a a a has at least exp ( a ( ln d − ln ln ln d − O ( 1 ) ) ) \exp(a(\ln d-\ln\ln\ln d-O(1))) exp ( a ( ln d − ln ln ln d − O ( 1 ))) distinct types. In fact if every class had at most the indicated type count with a sufficiently large fixed constant, the full forest entropy would violate that bound. We use a ≥ d k / 2 a \ge dk/2 a ≥ d k /2 , a ≤ Δ k / 2 a \le\Delta k/2 a ≤ Δ k /2 , and k ≥ d + 1 k \ge d+1 k ≥ d + 1 .
Strip two types of bad copies.
Put θ = L 0 ln L / L \theta= L_0\ln L/L θ = L 0 ln L / L with a sufficiently large fixed L 0 L_0 L 0 . Call a copy repeat-bad if at least θ a / 2 \theta a/2 θ a /2 of its edges occur in blocks containing at least two of its edges. As in Proposition 6.1 , such a copy supplies j = ⌊ θ a / 12 ⌋ j = \lfloor\theta a/12\rfloor j = ⌊ θ a /12 ⌋ disjoint same-block pairs. On a connected image set there are at most D k Dk D k available edges and at most D k ℓ 2 2 Dk\ell_2^2 D k ℓ 2 2 same-block pairs. Thus the logarithm of the bad edge subset count is bounded by
a ln ( D k / a ) + O ( a ) − j ln ( D k / ( a ℓ 2 2 ) ) . (30) a\ln(Dk/a)+O(a)-j\ln(Dk/(a\ell_2^2)). \tag*{(30)} a ln ( D k / a ) + O ( a ) − j ln ( D k / ( a ℓ 2 2 )) . (30)
The error is uniform as θ → 0 \theta\to0 θ → 0 by j ln ( a / j ) = O ( a ) j\ln(a/j)=O(a) j ln ( a / j ) = O ( a ) . The ratio inside the last logarithm is at least 32 Λ / ℓ 2 2 = d 1 / 2 + o ( 1 ) 32\Lambda/\ell_2^2=d^{1/2+o(1)} 32Λ/ ℓ 2 2 = d 1/2 + o ( 1 ) , while ln ( D k / a ) ≤ ln d + κ ln L + O A , M ( 1 ) \ln(Dk/a)\le\ln d+\kappa\ln L+O_{A,M}(1) ln ( D k / a ) ≤ ln d + κ ln L + O A , M ( 1 ) . With L 0 L_0 L 0 sufficiently large the deficit beats the class threshold by Ω ( a ln L ) \Omega(a\ln L) Ω ( a ln L ) , even after the factor D 2 k D^{2k} D 2 k for connected image sets through a fixed edge.
For the other strip, put b = 256 κ b=256\kappa b = 256 κ , T = D / L b T=D/L^b T = D / L b , ϵ = L − 1 / 4 \epsilon=L^{-1/4} ϵ = L − 1/4 , and s = ⌊ ( 20 ϵ ) − 1 ⌋ s=\lfloor(20\epsilon)^{-1}\rfloor s = ⌊( 20 ϵ ) − 1 ⌋ . For a role of a copy in J J J , call it defective if there is a tuple of between two and s s s distinct host candidates, each adjacent in J 0 J_0 J 0 to at least a ( 1 − 5 ϵ ) (1-5\epsilon) ( 1 − 5 ϵ ) fraction of its actual neighbor images, with common J 0 J_0 J 0 neighborhood of size at most T T T . Call a copy tuple-bad if defective roles have total degree at least a / 8 a/8 a /8 . A witnessing tuple at a role has common neighborhood containing at least three quarters of the role’s actual neighbors, by the union bound. Apply Lemma 2.4 using one such tuple per defective role. For each restricted edge assign its deficit ln ( D / C ) \ln(D/C) ln ( D / C ) , with C C C the tuple’s common neighborhood size, at the endpoint of larger deficit. The total assigned deficit is at least b a ln L / 32 ba\ln L/32 ba ln L /32 . For example each role restricts at least three quarters of its edges and each edge is counted at most twice in the incidence sum. The witness tuple at a role has at most ( 1 + D ) 2 s + 2 (1+D)^{2s+2} ( 1 + D ) 2 s + 2 choices, since every member lies within distance two in J J J of the true image. These choices and the counts of assigned edges cost exp ( O ( k s ln D ) ) = exp ( o ( a ) ) \exp(O(ks\ln D))=\exp(o(a)) exp ( O ( k s ln D )) = exp ( o ( a )) . The logarithm of the bad count through a fixed edge is at most
a ( ln d + κ ln L + O ( 1 ) ) − b a ln L / 32 + o ( a ) . (31) a(\ln d+\kappa\ln L+O(1))-ba\ln L/32+o(a). \tag*{(31)} a ( ln d + κ ln L + O ( 1 )) − ba ln L /32 + o ( a ) . (31)
Because b / 32 = 8 κ b/32=8\kappa b /32 = 8 κ , this is below the class threshold by Ω κ ( a ln L ) \Omega_\kappa(a\ln L) Ω κ ( a ln L ) for large d d d .
Average the sum of the repeat-bad and tuple-bad supports over the same class. As in the two preceding counts, the support is the set of all host edges occurring in at least one such bad copy of a type. Select a fixed type F F F whose combined support has at most e / 16 e/16 e /16 edges and delete that support from J J J , leaving J 1 J_1 J 1 . Badness is still measured in the original J J J and J 0 J_0 J 0 . Every copy of F F F in J 1 J_1 J 1 is good for both tests.
Copies using many extracted edges.
Independently mark each block with probability p K = C K ln D / ( θ d ) p_K=C_K\ln D/(\theta d) p K = C K ln D / ( θ d ) . A copy of F F F using at least θ a \theta a θ a edges of K K K uses at least θ a / 2 \theta a/2 θ a /2 distinct blocks, so take the first strip. The red event for this embedding requires those blocks all unmarked. Through a variable the number of events has logarithm O ( k ln D ) O(k\ln D) O ( k ln D ) , by pinning a target edge and an actual edge in that block and traversing the target spanning tree. For large fixed C K C_K C K , the asymmetric local lemma applies with half-exponent weights, as in Proposition 6.1 . Conditional mark probabilities are at most 2 p K 2p_K 2 p K . At each scale the expected marked target capacity divided by e e e is
O ( σ ln D θ ρ i ℓ i ) = o ( 1 ) . (32) O\left(\frac{\sigma\ln D}{\theta\rho_i\ell_i}\right)=o(1). \tag*{(32)} O ( θ ρ i ℓ i σ ln D ) = o ( 1 ) . (32)
This excludes all red copies in this branch at small blue cost.
Tolerant lists and the small support intersections.
Now consider a copy of F F F in J 1 J_1 J 1 using fewer than θ a \theta a θ a edges of K K K . Call a role exceptional if more than 2 ϵ 2\epsilon 2 ϵ of its incident target edges use K K K . Its total exceptional degree volume is at most θ a / ϵ \theta a/\epsilon θ a / ϵ , and there are at most u = θ a / ( ϵ d ) u=\theta a/(\epsilon d) u = θ a / ( ϵ d ) exceptional roles. Proposition 6.1 applies with sample rate C s ϵ − 2 ln ( D + 1 ) / d C_s\epsilon^{-2}\ln(D+1)/d C s ϵ − 2 ln ( D + 1 ) / d and additive error ϵ \epsilon ϵ . Indeed the additive binomial tail exponent is Ω ( ϵ 2 d v ) \Omega(\epsilon^2d_v) Ω ( ϵ 2 d v ) times the sample rate for a role of degree d v d_v d v . Thus we can record a connected seed of size O ( k ϵ − 2 ln ( D + 1 ) / d ) O(k\epsilon^{-2}\ln(D+1)/d) O ( k ϵ − 2 ln ( D + 1 ) / d ) and its flagged sample. Outside the seed, use the list of candidates adjacent in J 0 J_0 J 0 to at least a ( 1 − 4 ϵ ) (1-4\epsilon) ( 1 − 4 ϵ ) fraction of the flagged neighbor images. The true image of a nonexceptional role lies in this list. Each listed candidate sees at least a ( 1 − 5 ϵ ) (1-5\epsilon) ( 1 − 5 ϵ ) fraction of the actual neighbor images in J 0 J_0 J 0 . As in the baseline, any such list of size at least ℓ 1 \ell_1 ℓ 1 yields a prohibited dense pair by averaging over the actual neighbor set. Seed lists are singletons with the true images.
Ignore empty lists and lists containing a tuple of between two and s s s candidates with common J 0 J_0 J 0 neighborhood at most T T T . This operation is determined by the seed. Empty lists are exceptional, and every ignored nonempty list is at a defective role. Thus at most a / 8 + θ a / ϵ a/8+\theta a/\epsilon a /8 + θ a / ϵ target degree volume is ignored. Every remaining nonsingleton list consists of vertices of host degree at least T T T in J 0 J_0 J 0 and every subset of at most s s s of its candidates has more than T T T common neighbors. This includes singleton subsets of a nonsingleton list by its pair condition.
Put T ′ = T d − 1 / 16 T'=Td^{-1/16} T ′ = T d − 1/16 and let Q Q Q join pairs of J 0 J_0 J 0 -codegree above T ′ T' T ′ . By Lemma 2.6, Q Q Q has maximum degree less than q = ℓ 2 q=\ell_2 q = ℓ 2 . In detail, q q q partners of a vertex x x x would each see at least T ′ − q T'-q T ′ − q vertices in N J 0 ( x ) N_{J_0}(x) N J 0 ( x ) outside those partners. Averaging over a disjoint q q q -subset would give a rectangle of density at least ( T ′ − q ) / D > ρ 2 (T'-q)/D>\rho_2 ( T ′ − q ) / D > ρ 2 , a contradiction.
Let X X X be the host vertices of J 0 J_0 J 0 -degree at least T T T . For every t t t -set S S S of host centers, where t = 128 t=128 t = 128 , let B S = X ∩ ⋂ z ∈ S N J 0 ( z ) B_S=X\cap\bigcap_{z\in S}N_{J_0}(z) B S = X ∩ ⋂ z ∈ S N J 0 ( z ) . Retain variables only for 1 ≤ ∣ B S ∣ ≤ q 1\le|B_S|\le q 1 ≤ ∣ B S ∣ ≤ q . Use h = 32 h=32 h = 32 independent rounds of these variables. In each round independently mark each retained variable with probability p = c 0 T / ( h Λ Δ D t ) p=c_0T/(h\Lambda\Delta D^t) p = c 0 T / ( h ΛΔ D t ) . A mark colors blue every retained edge of J 1 J_1 J 1 incident to B S B_S B S . The target capacity of that mark is at most Δ ∣ B S ∣ \Delta|B_S| Δ∣ B S ∣ . Each x ∈ X x\in X x ∈ X belongs to at most D t D^t D t such blocks, and ∣ X ∣ ≤ 2 m / T |X|\le2m/T ∣ X ∣ ≤ 2 m / T . Thus the unconditional expected total marked capacity is at most 2 c 0 ϵ 2c_0\epsilon 2 c 0 ϵ .
A constant number of rounds covers a good list.
Consider a remaining nonsingleton list and a nonempty subset Y Y Y of its candidates not yet covered. If ∣ Y ∣ ≤ s |Y|\le s ∣ Y ∣ ≤ s , at least T T T centers are adjacent to all of Y Y Y . If ∣ Y ∣ > s |Y|>s ∣ Y ∣ > s , count s s s -sets of Y Y Y over their common neighborhoods as in Lemma 2.5. Writing a z = ∣ N J 0 ( z ) ∩ Y ∣ a_z=|N_{J_0}(z)\cap Y| a z = ∣ N J 0 ( z ) ∩ Y ∣ , we have
∑ z ( a z / ∣ Y ∣ ) s ≥ T , ∑ z a z / ∣ Y ∣ ≤ D . (33) \sum_z(a_z/|Y|)^s\ge T,\qquad\sum_z a_z/|Y|\le D. \tag*{(33)} z ∑ ( a z /∣ Y ∣ ) s ≥ T , z ∑ a z /∣ Y ∣ ≤ D . (33)
Consequently at least T / 2 T/2 T /2 centers see a ( 1 − ϑ ) (1-\vartheta) ( 1 − ϑ ) fraction of Y Y Y , where ϑ = ln ( 2 D / T ) / ( s − 1 ) \vartheta=\ln(2D/T)/(s-1) ϑ = ln ( 2 D / T ) / ( s − 1 ) . In either case let W W W be the set of those centers, with zero deficit in the small-list case. By averaging some x ∈ Y x\in Y x ∈ Y sees at least half the centers in W W W . Let W x W_x W x be these centers, of size at least T / 4 T/4 T /4 .
Choose a uniform t t t -set of W x W_x W x . Its block contains x x x . For any y y y outside { x } ∪ N Q ( x ) \{x\}\cup N_Q(x) { x } ∪ N Q ( x ) , the probability that y y y is in the block is at most ( T ′ / ∣ W x ∣ ) t ≤ ( 4 d − 1 / 16 ) t (T'/|W_x|)^t\le(4d^{-1/16})^t ( T ′ /∣ W x ∣ ) t ≤ ( 4 d − 1/16 ) t . At most D 2 D^2 D 2 vertices can share any J 0 J_0 J 0 neighbor with x x x . Thus a union bound shows a 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) fraction of the t t t -sets give blocks contained in { x } ∪ N Q ( x ) \{x\}\cup N_Q(x) { x } ∪ N Q ( x ) and therefore retained. Such a block covers all of Y Y Y when ∣ Y ∣ ≤ s |Y|\le s ∣ Y ∣ ≤ s , and covers at least a ( 1 − ϑ ) (1-\vartheta) ( 1 − ϑ ) fraction otherwise. There are Ω ( T t ) \Omega(T^t) Ω ( T t ) eligible variables in a fresh round. The chance of at least one such mark is at least a fixed positive constant times min ( 1 , p T t ) \min(1,pT^t) min ( 1 , p T t ) , which is Ω ( L − b ( t + 1 ) ) \Omega(L^{-b(t+1)}) Ω ( L − b ( t + 1 ) ) for fixed c 0 c_0 c 0 .
For sufficiently large d d d , t ϑ ≤ L − 1 / 5 t\vartheta\le L^{-1/5} tϑ ≤ L − 1/5 , since s s s has order L 1 / 4 L^{1/4} L 1/4 and ln ( 2 D / T ) = O ( ln L ) \ln(2D/T)=O(\ln L) ln ( 2 D / T ) = O ( ln L ) . At most h − 1 h-1 h − 1 successful rounds shrink a set of at most ℓ 1 \ell_1 ℓ 1 candidates to order at most s s s , and a further successful round covers it. The probability that all candidates are covered after h h h rounds is therefore at least
β = L − 1 / 8 , (34) \beta=L^{-1/8}, \tag*{(34)} β = L − 1/8 , (34)
for sufficiently large d d d . The fixed exponent b ( t + 1 ) h b(t+1)h b ( t + 1 ) h is below 1 / 8 1/8 1/8 with the stated κ \kappa κ , and the fixed multiplicative constants are absorbed as d → ∞ d\to\infty d → ∞ . These events use only their own listed candidates and the independent marks.
Robust red tests without encoding exceptional roles.
For each eligible seed configuration with at least a / 8 a/8 a /8 total degree in nonignored nonsingleton roles, deterministically choose a maximum matching of those roles to their lists. Since every nonexceptional role has its true image in its list, at most u u u roles go unmatched. We have u = o ( a / Δ ) u=o(a/\Delta) u = o ( a /Δ ) because ( Δ / d ) θ / ϵ = o ( 1 ) (\Delta/d)^{\theta/\epsilon}=o(1) ( Δ/ d ) θ / ϵ = o ( 1 ) . Thus at least a / ( 16 Δ ) a/(16\Delta) a / ( 16Δ ) roles are matched. A marked block variable can affect at most q 2 q^2 q 2 such role blockage indicators. Indeed its block has at most q q q candidates y y y , and for each such y y y there are at most q q q matched lists containing y y y . Their matched images are distinct and lie in { y } ∪ N Q ( y ) \{y\}\cup N_Q(y) { y } ∪ N Q ( y ) by the clique property. This proves the read bound even if lists overlap arbitrarily.
The mean blocked count is at least μ 0 = β a / ( 16 Δ ) ≫ u \mu_0=\beta a/(16\Delta)\gg u μ 0 = β a / ( 16Δ ) ≫ u . The product Hölder lower-tail argument in Lemma 2.2 gives probability at most exp ( − μ 0 / ( 8 q 2 ) ) \exp(-\mu_0/(8q^2)) exp ( − μ 0 / ( 8 q 2 )) of blocking at most u u u matched roles. A red extension would require this event since it can avoid a fully blocked list only at an exceptional role. Take one event per configuration. At a fixed variable one of its at most q q q members lies in a tested list. Pin that member’s seed image, or a flagged neighbor image within distance one. Count connected seeds and their rooted images, and their flag subsets. The resulting logarithm is O ( k ϵ − 2 ( ln ( D + 1 ) ) 2 / d ) O(k\epsilon^{-2}(\ln(D+1))^2/d) O ( k ϵ − 2 ( ln ( D + 1 ) ) 2 / d ) . It is o ( μ 0 / q 2 ) o(\mu_0/q^2) o ( μ 0 / q 2 ) since q = O ( d 1 / 4 ) q=O(d^{1/4}) q = O ( d 1/4 ) , a ≥ d k / 2 a\ge dk/2 a ≥ d k /2 , and Δ / d ≤ A L κ \Delta/d\le AL^\kappa Δ/ d ≤ A L κ . An event uses at most h k ℓ 1 D t hk\ell_1D^t hk ℓ 1 D t variables. The local lemma with half-exponent weights applies, as the per-variable weight sum is exponentially small in μ 0 / q 2 \mu_0/q^2 μ 0 / q 2 and k ≥ d + 1 k\ge d+1 k ≥ d + 1 . Its conditioning multiplies each mark probability by at most two.
For the remaining configurations, the total degree volume of ignored and nonsingleton roles is at most a / 4 + o ( a ) a/4+o(a) a /4 + o ( a ) . Match the eligible singleton roles to their specified images, losing at most u u u roles. In a witnessing embedding, excluding the exceptional roles and any unmatched roles costs at most 2 Δ u = o ( a ) 2\Delta u=o(a) 2Δ u = o ( a ) further edges. Therefore the determined set of existing J 1 J_1 J 1 image edges between matched singleton roles has at least a / 2 a/2 a /2 distinct members. Independently mark edges of J 1 J_1 J 1 with probability c 0 / Λ c_0/\Lambda c 0 /Λ . A red extension requires that every such marked image edge be incident to one of at most u u u exceptional roles. For a fixed candidate exceptional set, removing its at most Δ u = o ( a ) \Delta u=o(a) Δ u = o ( a ) edges leaves a fixed positive fraction of a a a edges required unmarked. This has probability exp ( − Ω M ( k ) ) \exp(-\Omega_M(k)) exp ( − Ω M ( k )) . Since u = o ( k ) u=o(k) u = o ( k ) , the number of exceptional subsets is exp ( o ( k ) ) \exp(o(k)) exp ( o ( k )) . The rooted configuration count through a variable is the same as in the nonsingleton test. The local lemma again excludes all these events and makes conditional mark probabilities at most 2 c 0 / Λ 2c_0/\Lambda 2 c 0 /Λ .
Complete the coloring.
The extracted block test, the common-neighborhood intersection test, and the singleton edge test use independent variable families. The red events within each family are defined without looking at the other marks. Condition each family on avoiding its events. The combined expected marked target capacity is at most o ( e ) + 4 c 0 e + 2 c 0 e o(e)+4c_0e+2c_0e o ( e ) + 4 c 0 e + 2 c 0 e . Choose c 0 c_0 c 0 sufficiently small and fix an outcome with marked capacity at most e / 8 e/8 e /8 . Color all marked edges and all pruned edges blue, and color the remaining edges red. Red G G G would contain a red F F F in one of the three excluded cases. A blue copy of G G G can use at most e / 8 + e / 16 e/8+e/16 e /8 + e /16 edges at the pruned locations, and at most e / 8 e/8 e /8 edges in the marked locations. This contradiction proves the restricted superlinear theorem.
Incidence targets of exact right degree
The incidence estimate
Theorem 8.1. Fix A , B , M , τ > 0 A, B, M, \tau> 0 A , B , M , τ > 0 with A , M ≥ 1 A, M \ge1 A , M ≥ 1 . For sufficiently large d d d , let G G G be bipartite with exact right degree d d d , left minimum degree at least d ( log d ) τ d(\log d)^\tau d ( log d ) τ , maximum degree at most d A d^A d A , and e G ( U ) ≤ B log d ∣ U ∣ e_G(U) \le B \log d \lvert U\rvert e G ( U ) ≤ B log d ∣ U ∣ for ∣ U ∣ ≤ d \lvert U\rvert\le d ∣ U ∣ ≤ d . Then R ^ ( G ) > M d e ( G ) \widehat{R}(G) > Md\,e(G) R ( G ) > M d e ( G ) .
Proof. Pruning, two block scales, and a component class. Suppose H H H arrows G G G with m ≤ Λ e m \le\Lambda e m ≤ Λ e , where e = e ( G ) e=e(G) e = e ( G ) and Λ = M d \Lambda=Md Λ = M d . Use the host degree cutoff D = ⌈ 16 Λ Δ ( G ) ⌉ D=\lceil16\Lambda\Delta(G)\rceil D = ⌈ 16ΛΔ ( G )⌉ , and let D R = ⌈ 32 Λ d ⌉ D_R=\lceil32\Lambda d\rceil D R = ⌈ 32Λ d ⌉ . Remove vertices of original degree above D D D , and edges with both original endpoint degrees above D R D_R D R . The target edge losses are at most e / 8 e/8 e /8 and e / 16 e/16 e /16 . For the second bound, each such target edge has a right image of original degree above D R D_R D R , and there are at most 2 m / D R 2m/D_R 2 m / D R such vertices. Low and high host vertices refer to original degree at most or above D R D_R D R . Let J J J be the retained graph, and J × J_\times J × its high-low cross graph. Every k k k -set of J J J spans at most D R k D_R k D R k edges, since every retained edge has a low endpoint.
Write L = ln d L=\ln d L = ln d , U = ln L U=\ln L U = ln L , ℓ 1 = ⌈ L ⌉ \ell_1=\lceil L\rceil ℓ 1 = ⌈ L ⌉ , ρ 1 = 1 / 4 \rho_1=1/4 ρ 1 = 1/4 , ℓ 2 = ⌈ d 1 / 4 ⌉ \ell_2=\lceil d^{1/4}\rceil ℓ 2 = ⌈ d 1/4 ⌉ , and ρ 2 = d − 1 / 8 \rho_2=d^{-1/8} ρ 2 = d − 1/8 . In J × J_\times J × greedily extract the edges between high and low sets of order ℓ 1 \ell_1 ℓ 1 of current cross density at least ρ 1 \rho_1 ρ 1 . After exhaustion do the same at order ℓ 2 \ell_2 ℓ 2 and density ρ 2 \rho_2 ρ 2 . The extracted blocks partition their edge union K K K , with possibly overlapping vertex supports. Put J 0 = J × − K J_0=J_\times-K J 0 = J × − K . It has neither kind of dense rectangle. The total target capacity of blocks at scale i i i is at most 2 B L m / ( ρ i ℓ i ) 2BLm/(\rho_i\ell_i) 2 B L m / ( ρ i ℓ i ) , because each has at least ρ i ℓ i 2 \rho_i\ell_i^2 ρ i ℓ i 2 host edges and a target can use at most 2 B L ℓ i 2BL\ell_i 2 B L ℓ i edges there. All support orders are at most d d d for large d d d .
By Proposition 6.2 , some class of target components of order k k k and edge count f f f has at least exp ( f ( ln d − ln ln ln d − O ( 1 ) ) ) \exp(f(\ln d-\ln\ln\ln d-O(1))) exp ( f ( ln d − ln ln ln d − O ( 1 ))) distinct types. Each has right order b = f / d b=f/d b = f / d and left order a = k − b a=k-b a = k − b . The left minimum degree implies b / a ≥ L τ b/a\ge L^\tau b / a ≥ L τ , so k ≤ 2 b k\le2b k ≤ 2 b for large d d d . In particular D R k / f = O M ( d ) D_Rk/f=O_M(d) D R k / f = O M ( d ) , and the baseline type count on one image set is exp ( f ( ln d + O M ( 1 ) ) ) \exp(f(\ln d+O_M(1))) exp ( f ( ln d + O M ( 1 ))) . The number of connected image sets of order k k k through a fixed host edge is at most D 2 k D^{2k} D 2 k , whose logarithm is o ( f ) o(f) o ( f ) .
Three entropy strips.
Call a copy orientation-bad if at least f / 64 f/64 f /64 edges have a left image of low host degree. Specify the left image set on its connected image set, at cost at most 2 k 2^k 2 k . Edges at low left images lie in a pool of at most D R a D_Ra D R a host edges. If there are g g g such edges, the logarithm of the two-pool binomial count is at most f ln ( D R k / f ) + O ( f ) − g ln ( k / a ) f\ln(D_Rk/f)+O(f)-g\ln(k/a) f ln ( D R k / f ) + O ( f ) − g ln ( k / a ) . This follows from the exponential binomial bound and the two-bin entropy bound. Since ln ( k / a ) ≥ τ ln L \ln(k/a)\ge\tau\ln L ln ( k / a ) ≥ τ ln L , the loss for an orientation-bad copy is Ω τ ( f ln L ) \Omega_\tau(f\ln L) Ω τ ( f ln L ) , which beats the class threshold. The number of choices of g g g contributes only o ( f ) o(f) o ( f ) to the exponent. Every orientation-good copy has at most b / 32 b/32 b /32 right roles with fewer than d / 2 d/2 d /2 high left image neighbors.
Put θ = C 1 ln L / L \theta=C_1\ln L/L θ = C 1 ln L / L for large fixed C 1 C_1 C 1 . Call a copy repeat-bad if at least θ f / 2 \theta f/2 θ f /2 of its edges lie in blocks containing two or more edges of that copy. Proposition 6.1 supplies j = ⌈ θ f / 12 ⌉ j=\lceil\theta f/12\rceil j = ⌈ θ f /12 ⌉ disjoint pairs inside individual blocks. The number of available pairs on one image set is at most D R k ℓ 2 2 D_Rk\ell_2^2 D R k ℓ 2 2 . Choosing these pairs and the remaining single edges gives a logarithmic count at most f ln ( D R k / f ) + O ( f ) − j ln ( D R k / ( f ℓ 2 2 ) ) f\ln(D_Rk/f)+O(f)-j\ln(D_Rk/(f\ell_2^2)) f ln ( D R k / f ) + O ( f ) − j ln ( D R k / ( f ℓ 2 2 )) . The uniform O ( f ) O(f) O ( f ) error follows from j ln ( f / j ) = O ( f ) j\ln(f/j)=O(f) j ln ( f / j ) = O ( f ) . The last ratio is at least d 1 / 2 + o ( 1 ) d^{1/2+o(1)} d 1/2 + o ( 1 ) . Thus this strip pays Ω ( f ln L ) \Omega(f\ln L) Ω ( f ln L ) beyond the baseline.
For the final strip take ϵ = L − 1 / 4 \epsilon=L^{-1/4} ϵ = L − 1/4 , s = ⌈ ( 20 ϵ ) − 1 ⌉ s=\lceil(20\epsilon)^{-1}\rceil s = ⌈( 20 ϵ ) − 1 ⌉ , and T = D R / U B 0 T=D_R/U^{B_0} T = D R / U B 0 for a large fixed B 0 B_0 B 0 . Call a right role defective if some tuple of one to s s s distinct low vertices has a common J 0 J_0 J 0 neighborhood of size at most T T T containing at least d / 8 d/8 d /8 actual left image neighbors of the role. Call the copy tuple-bad if at least b / 8 b/8 b /8 roles are defective. Every defective role supplies at least d / 8 d/8 d /8 edges restricted to the designated common neighborhood. The role restrictions have distinct right endpoints. Specify the role image, the witness tuple, and the restricted edge counts as in Lemma 2.4 . Each tuple vertex lies within distance two in J J J of the actual right image, or coincides with it. The logarithmic cost of witness designations and counts is O ( k s ln D ) = o ( f ) O(ks\ln D)=o(f) O ( k s ln D ) = o ( f ) . The restricted edges pay penalty at least ( f / 64 ) ln ( D R / T ) = ( B 0 / 64 ) f ln U (f/64)\ln(D_R/T)=(B_0/64)f\ln U ( f /64 ) ln ( D R / T ) = ( B 0 /64 ) f ln U in the binomial count relative to f ln ( D R k / f ) + O ( f ) f\ln(D_Rk/f)+O(f) f ln ( D R k / f ) + O ( f ) . In fact the restricted choices at a role with common size C C C and designated count g v g_v g v are bounded by ( C g v ) \binom{C}{g_v} ( g v C ) , and the unrestricted term by ( D R k f − ∑ g v ) \binom{D_R k}{f-\sum g_v} ( f − ∑ g v D R k ) . The entropy estimate for the g v g_v g v distributes their common D R D_R D R baseline over at most k k k roles. This gives the deficit ∑ v g v ln ( D R / C ) \sum_v g_v\ln(D_R/C) ∑ v g v ln ( D R / C ) for singleton witnesses as well. Take B 0 B_0 B 0 large enough to beat the gap f ln U f\ln U f ln U in the class threshold.
For a type in the class, its bad support is the set of all edges occurring in one of these three kinds of bad copy. The bounds through any fixed host edge, divided by the number of class types, are exponentially small in f ln U f\ln U f ln U . Average the support size over the class. Since m / e ≤ M d m/e\le Md m / e ≤ M d , some fixed component type F F F has bad support at most e / 16 e/16 e /16 . Delete it from J J J to get J 1 J_1 J 1 . The strip predicates still use the original J J J and J 0 J_0 J 0 and the original assigned blocks. Every embedding of F F F into J 1 J_1 J 1 is good for all three tests.
Exclude the block-rich red branch.
Mark blocks independently with probability C 2 ln D / ( θ d ) C_2\ln D/(\theta d) C 2 ln D / ( θ d ) for large fixed C 2 C_2 C 2 . For each embedding of F F F in J 1 J_1 J 1 using at least θ f \theta f θ f edges of K K K , its red event requires at least θ f / 2 \theta f/2 θ f /2 distinct blocks unmarked, by repeat-goodness. Through one block the logarithm of the embedding count is O ( k ln D ) O(k\ln D) O ( k ln D ) by pinning a target edge and its image in that block, then traversing a spanning tree. The red exponent can exceed this count by an arbitrary fixed factor since f ≥ d k / 2 f\ge dk/2 f ≥ d k /2 . The asymmetric local lemma with half-exponent weights avoids these events and raises each mark probability by at most two. The conditional expected marked target capacity at each scale divided by e e e is O ( B L ln D / ( ρ i ℓ i θ ) ) = o ( 1 ) O(BL\ln D/(\rho_i\ell_i\theta))=o(1) O ( B L ln D / ( ρ i ℓ i θ )) = o ( 1 ) .
Select the oriented roles using an adaptive sample.
Consider an embedding ϕ \phi ϕ of F F F into J 1 J_1 J 1 using fewer than θ f \theta f θ f edges of K K K . For each right role v v v let A v A_v A v be its actual high left neighbor image set. Sample target vertices independently at rate p s = C 3 ε − 2 ln ( D + 1 ) / d p_s=C_3\varepsilon^{-2}\ln(D+1)/d p s = C 3 ε − 2 ln ( D + 1 ) / d . A sampled target vertex is flagged, including its host image as part of the seed data. In particular the data show which flagged left images are high. At each right role require that the number of sampled vertices corresponding to A v A_v A v differ from p s ∣ A v ∣ p_s|A_v| p s ∣ A v ∣ by at most $p_sd/16. If ∣ A v ∣ ≥ d / 4 |A_v|\ge d/4 ∣ A v ∣ ≥ d /4 , also require simultaneous additive accuracy at most ε \varepsilon ε for the sampled fraction of J 0 J_0 J 0 neighbors of every low host candidate that meets A v A_v A v in J 0 J_0 J 0 , relative to its fraction on all of A v A_v A v . There are at most D 2 D^2 D 2 such candidates. For the accuracy require deviations at most ε p s ∣ A v ∣ / 4 \varepsilon p_s|A_v|/4 ε p s ∣ A v ∣/4 for both numerator and denominator. The binomial additive tails have exponent Ω ( ε 2 p s d ) \Omega(\varepsilon^2p_sd) Ω ( ε 2 p s d ) and their ratio error is less than ε \varepsilon ε . The union of the count and accuracy failures has probability at most $1/(2d)$ at each right role for large fixed C 3 C_3 C 3 . A candidate with no adjacency to A v A_v A v cannot pass a positive sampled-fraction threshold. Also require at every role of either side at least one sampled neighbor, with failure probability at most 1 / ( 2 d ) 1/(2d) 1/ ( 2 d ) by minimum degree d d d .
Add all failed roles to the seed and connect the resulting dominating set by paths of length at most three along a spanning tree of its distance-three graph. Leave only the original sample flagged. Taking an outcome of no more than the expected number of sampled and added roles gives a connected seed of order O ( k ε − 2 ln ( D + 1 ) / d ) O(k\varepsilon^{-2}\ln(D+1)/d) O ( k ε − 2 ln ( D + 1 ) / d ) . Its size is o ( b ) o(b) o ( b ) , since k ≤ 2 b k\le2b k ≤ 2 b .
From the seed data, test each right role outside the connected seed whose number of flagged high left image neighbors is at least p s d / 3 p_sd/3 p s d /3 . Every tested role has ∣ A v ∣ ≥ d / 4 |A_v|\ge d/4 ∣ A v ∣ ≥ d /4 , by the sample count accuracy. Every role outside the seed with ∣ A v ∣ ≥ d / 2 |A_v|\ge d/2 ∣ A v ∣ ≥ d /2 is tested. Thus all but at most b / 32 + o ( b ) b/32+o(b) b /32 + o ( b ) right roles are tested. The true host image of every tested role is low, since it has a flagged high actual neighbor and J J J has no high-high edge.
For a tested role take the list of low host candidates adjacent in J 0 J_0 J 0 to at least a ( 1 − 4 ε ) (1-4\varepsilon) ( 1 − 4 ε ) fraction of its flagged high left neighbor images. Each candidate sees at least a ( 1 − 5 ε ) (1-5\varepsilon) ( 1 − 5 ε ) fraction of A v A_v A v in J 0 J_0 J 0 . A list with at least ℓ 1 \ell_1 ℓ 1 members gives a prohibited first-scale rectangle, by averaging ℓ 1 \ell_1 ℓ 1 vertices of A v A_v A v against ℓ 1 \ell_1 ℓ 1 candidates. Its two sides are disjoint by high and low host degrees. The true image belongs to the list except possibly when more than 2 ε ∣ A v ∣ ≥ ε d / 2 2\varepsilon|A_v|\ge\varepsilon d/2 2 ε ∣ A v ∣ ≥ ε d /2 of the role’s high-left edges are in K K K . In fact the true image has all the other high-left edges in J 0 J_0 J 0 , so the fraction test follows from the sampling estimate. There are at most u = 2 θ b / ε u=2\theta b/\varepsilon u = 2 θ b / ε such exceptions, since right roles partition the edges and the embedding uses fewer than θ f \theta f θ f edges in K K K .
Ignore empty lists and lists containing a tuple of between one and s s s members with common J 0 J_0 J 0 neighborhood at most T T T . Empty lists are exceptional. A tuple from a tested list shares at least ( 1 − 5 ε s ) ∣ A v ∣ ≥ 3 d / 16 > d / 8 (1-5\varepsilon s)|A_v|\ge3d/16>d/8 ( 1 − 5 ε s ) ∣ A v ∣ ≥ 3 d /16 > d /8 actual left neighbors, so a nonempty ignored list is at a defective role. Fewer than b / 8 b/8 b /8 roles are defective by the strip. Therefore at least 3 b / 4 3b/4 3 b /4 tested roles have nonempty lists left after ignoring, for large d d d . Every nonempty subset of up to s s s candidates of such a list has more than T T T common neighbors in J 0 J_0 J 0 . In particular even a singleton candidate has J 0 J_0 J 0 degree above T T T .
Small intersections of host neighborhoods.
Put T ′ = T d − 1 / 16 T'=Td^{-1/16} T ′ = T d − 1/16 and q = ℓ 2 q=\ell_2 q = ℓ 2 . Join two low host vertices in Q Q Q when they have J 0 J_0 J 0 -codegree greater than T ′ T' T ′ . Its maximum degree is below q q q . Otherwise q q q low partners of x x x each have more than T ′ T' T ′ neighbors in N J 0 ( x ) N_{J_0}(x) N J 0 ( x ) , a set of at most D R D_R D R high vertices. Choose q q q of those high vertices by averaging. The resulting cross density is at least T ′ / D R > ρ 2 T'/D_R>\rho_2 T ′ / D R > ρ 2 , a prohibited rectangle. Here T ′ ≫ q T'\gg q T ′ ≫ q , so there are enough high vertices to choose from. Set X = { x low : deg J 0 ( x ) ≥ T } X=\{x\text{ low}:\deg_{J_0}(x)\ge T\} X = { x low : deg J 0 ( x ) ≥ T } .
Fix an integer t > 32 ( A + 3 ) t>32(A+3) t > 32 ( A + 3 ) and let h = 32 h=32 h = 32 . For each t t t -set S S S of high host centers let B S B_S B S be the set of x ∈ X x\in X x ∈ X adjacent in J 0 J_0 J 0 to every member of S S S . Retain variables only for 1 ≤ ∣ B S ∣ ≤ q 1\le|B_S|\le q 1 ≤ ∣ B S ∣ ≤ q . In each of h h h independent rounds mark each with probability p = c 0 T / ( h Λ d D R t ) p=c_0T/(h\Lambda dD_R^t) p = c 0 T / ( h Λ d D R t ) for small fixed c 0 c_0 c 0 . A mark colors all retained cross edges of J 1 J_1 J 1 incident to B S B_S B S blue. The oriented target capacity of a mark, counting edges whose right image is low, is at most d ∣ B S ∣ d|B_S| d ∣ B S ∣ . Every x ∈ X x\in X x ∈ X belongs to at most D R t D_R^t D R t variables per round and ∣ X ∣ ≤ 2 m / T |X|\le2m/T ∣ X ∣ ≤ 2 m / T . Consequently the unconditional expected marked oriented capacity is at most 2 c 0 e 2c_0e 2 c 0 e . All cross edges in any target copy with right image high number at most d ( 2 m / D R ) ≤ e / 16 d(2m/D_R)\le e/16 d ( 2 m / D R ) ≤ e /16 , an allowance used only once across these marks.
Take any remaining list and any nonempty subset Y Y Y of still uncovered candidates. If ∣ Y ∣ ≤ s |Y|\le s ∣ Y ∣ ≤ s , at least T T T centers cover all of Y Y Y . Otherwise let a w = ∣ N J 0 ( w ) ∩ Y ∣ a_w=|N_{J_0}(w)\cap Y| a w = ∣ N J 0 ( w ) ∩ Y ∣ . Counting common neighbors of the s s s -sets of Y Y Y gives ∑ w ( a w / ∣ Y ∣ ) s ≥ T \sum_w(a_w/|Y|)^s\ge T ∑ w ( a w /∣ Y ∣ ) s ≥ T , while ∑ w a w / ∣ Y ∣ ≤ D R \sum_w a_w/|Y|\le D_R ∑ w a w /∣ Y ∣ ≤ D R . Thus at least T / 2 T/2 T /2 centers each cover at least a ( 1 − ϑ ) (1-\vartheta) ( 1 − ϑ ) fraction of Y Y Y , with ϑ = ln ( 2 D R / T ) / ( s − 1 ) \vartheta=\ln(2D_R/T)/(s-1) ϑ = ln ( 2 D R / T ) / ( s − 1 ) . Indeed the smaller terms together contribute at most D R ( 1 − ϑ ) s − 1 ≤ T / 2 D_R(1-\vartheta)^{s-1}\le T/2 D R ( 1 − ϑ ) s − 1 ≤ T /2 . Some candidate x ∈ Y x\in Y x ∈ Y meets at least T / 4 T/4 T /4 of the indicated centers. A uniform t t t -set of those centers gives a block containing x x x . Any vertex outside { x } ∪ N Q ( x ) \{x\}\cup N_Q(x) { x } ∪ N Q ( x ) belongs to it with probability at most ( 4 T ′ / T ) t (4T'/T)^t ( 4 T ′ / T ) t . At most D 2 D^2 D 2 vertices share any neighbor with x x x . Our fixed t t t and D ≤ d A + 2 D\le d^{A+2} D ≤ d A + 2 make the union bound o ( 1 ) o(1) o ( 1 ) . Hence Ω t ( T ′ ) \Omega_t(T') Ω t ( T ′ ) such variables are retained and cover all but a t ϑ t\vartheta tϑ fraction of Y Y Y , or all of it in the small-list case.
In a fresh round, conditional on all previous rounds, the chance of at least one such mark is Ω ( min ( 1 , p T t ) ) = Ω ( U − B 0 ( t + 1 ) ) \Omega(\min(1,pT^t))=\Omega(U^{-B_0(t+1)}) Ω ( min ( 1 , p T t )) = Ω ( U − B 0 ( t + 1 ) ) . For large d d d , t ϑ ≤ L − 1 / 5 t\vartheta\le L^{-1/5} tϑ ≤ L − 1/5 . A list starts below ℓ 1 \ell_1 ℓ 1 , so h h h successful rounds cover it, with the final round covering the last at most s s s candidates together. This works for a singleton from the first round onward. The probability that a list is fully blocked is at least β = U − C 4 \beta=U^{-C_4} β = U − C 4 for a fixed constant C 4 C_4 C 4 depending on the stated parameters. This lower bound exceeds u / b = O ( L − 3 / 4 ln L ) u/b=O(L^{-3/4}\ln L) u / b = O ( L − 3/4 ln L ) by an unbounded factor.
Robust red event and blue budget.
For each seed configuration arising from one of the low-block-usage embeddings, choose a maximum matching of the remaining roles to their lists, deterministically. At most u u u go unmatched because the nonexceptional true images are distinct. There are at least b / 2 b/2 b /2 matched roles for large d d d . Every list is a clique in Q Q Q by its pair condition when it has at least two members. For any candidate y y y , at most q q q matched lists contain it, since their matched images lie in { y } ∪ N Q ( y ) \{y\}\cup N_Q(y) { y } ∪ N Q ( y ) and are distinct. Thus a mark variable affects at most q 2 q^2 q 2 blocked-role indicators, including when it removes only part of a list.
Each matched role is fully blocked with probability at least β \beta β . By Lemma 2.2, blocking at most u u u roles has probability at most exp ( − Ω ( β b / q 2 ) ) \exp(-\Omega(\beta b/q^2)) exp ( − Ω ( β b / q 2 )) . A red extension with this seed would require that event. For a nonexceptional role its true image is on the list, and a block mark covering that image paints its edges to flagged high left neighbors blue. Thus a fully blocked role in a red extension must be exceptional, without any specification of their identities.
At a variable B S B_S B S , one of its at most q q q members lies in a tested candidate list of an event using it. That member sees at least one flagged high left neighbor image in J 0 J_0 J 0 . Choose and pin that seed image, counting at most a fixed polynomial in k k k , D D D , q q q choices. Count connected target seeds by spanning-tree walks, their rooted images in J 1 J_1 J 1 , and their flag subsets. The logarithm of the number of events at the variable is O ( k ε − 2 ( ln ( D + 1 ) ) 2 / d ) O(k\varepsilon^{-2}(\ln(D+1))^2/d) O ( k ε − 2 ( ln ( D + 1 ) ) 2 / d ) , including the anchor choices since k ≥ d + 1 k \ge d+1 k ≥ d + 1 . It is o ( β b / q 2 ) o(\beta b/q^2) o ( β b / q 2 ) since q = O ( d 1 / 4 ) q=O(d^{1/4}) q = O ( d 1/4 ) , k ≤ 2 b k \le2b k ≤ 2 b , and β \beta β is an inverse fixed power of U U U . An event uses at most h b ℓ 1 D R t hb\ell_1D_R^t hb ℓ 1 D R t variables. The half-exponent asymmetric local lemma applies, with per-variable weight sum exponentially small in β b / q 2 \beta b/q^2 β b / q 2 and hence smaller than any fixed inverse power of d d d since b ≥ d b \ge d b ≥ d . The conditioning raises each intersection mark probability by at most two.
The block-rich and intersection tests use independent variable families, and each excludes its red events without reference to the other marks. Condition both on their respective avoidances. Their combined expected marked oriented capacity is at most o ( e ) + 4 c 0 e o(e)+4c_0e o ( e ) + 4 c 0 e , with the extra e / 16 e/16 e /16 right-high allowance for the intersection marks. Fix an outcome with marked oriented capacity at most e / 8 e/8 e /8 for small c 0 c_0 c 0 . Color all marked and all pruned edges blue. A red G G G contains the excluded F F F . A blue G G G would have at most 3 e / 16 + e / 16 3e/16+e/16 3 e /16 + e /16 edges in the degree pruning and bad-support deletion, at most e / 8 e/8 e /8 edges charged to marked capacity, and at most e / 16 e/16 e /16 additional edges at right-high images for the cross star marks. This is less than e e e . The contradiction proves the lemma.
Proof of the main theorem
Proof of Theorem 1.1. Suppose the theorem fails. The polynomial maximum-degree and local-sparsity reductions give fixed constants B B B , M 0 ≥ 1 M_0 \ge1 M 0 ≥ 1 , arbitrarily large integers d 0 d_0 d 0 , targets G 0 G_0 G 0 , and hosts H H H such that
δ ( G 0 ) ≥ d 0 , Δ ( G 0 ) ≤ d 0 B , H → G 0 , m = e ( H ) ≤ M 0 d 0 e ( G 0 ) . (35) \delta(G_0) \ge d_0,\qquad\Delta(G_0) \le d_0^B,\qquad H \to G_0,\qquad m=e(H) \le M_0d_0e(G_0). \tag*{(35)} δ ( G 0 ) ≥ d 0 , Δ ( G 0 ) ≤ d 0 B , H → G 0 , m = e ( H ) ≤ M 0 d 0 e ( G 0 ) . (35)
Fix K > 10 ( B + 2 ) 2 K>10(B+2)^2 K > 10 ( B + 2 ) 2 . The targets may also be required to satisfy e G 0 ( U ) ≤ B K log d 0 ∣ U ∣ e_{G_0}(U) \le B_K\log d_0\lvert U\rvert e G 0 ( U ) ≤ B K log d 0 ∣ U ∣ for ∣ U ∣ ≤ d 0 K \lvert U\rvert\le d_0^K ∣ U ∣ ≤ d 0 K , with fixed B K B_K B K . In each G 0 G_0 G 0 orient edges from the endpoint of larger original degree to the other endpoint, breaking ties by any fixed vertex order. Independently label vertices left or right and keep an edge only when its orientation is from a left label to a right label. Every edge survives with probability 1 / 4 1/4 1/4 , so a choice keeps at least e ( G 0 ) / 4 e(G_0)/4 e ( G 0 ) /4 edges. Denote this bipartite graph by F 0 F_0 F 0 .
For every dyadic integer q q q put the right vertices of F 0 F_0 F 0 whose degree in G 0 G_0 G 0 is in [ q , 2 q ) [q,2q) [ q , 2 q ) into one band and keep all their F 0 F_0 F 0 incident edges. Every band is a subgraph of G 0 G_0 G 0 and q ≥ d 0 / 2 q \ge d_0/2 q ≥ d 0 /2 . The left vertices appearing in a band have original degree at least q q q . In each band repeatedly peel vertices of current degree below q / 128 q/128 q /128 . At a left vertex v v v , the total possible loss over all bands is at most
∑ q ≤ deg G 0 ( v ) q d y a d i c q / 128 ≤ 2 deg G 0 ( v ) / 128. (36) \sum_{\substack{q\le\deg_{G_0}(v)\\ q\ \mathrm{dyadic}}} q/128 \le2\deg_{G_0}(v)/128. \tag*{(36)} q ≤ d e g G 0 ( v ) q dyadic ∑ q /128 ≤ 2 deg G 0 ( v ) /128. (36)
A right vertex belongs to only one band, and its loss is at most its original degree divided by 128. Sum these bounds over vertices. They cost at most 6 e ( G 0 ) / 128 6e(G_0)/128 6 e ( G 0 ) /128 , leaving a total of at least 13 e ( G 0 ) / 64 13e(G_0)/64 13 e ( G 0 ) /64 edges. Every nonempty band has minimum degree at least q / 128 q/128 q /128 and right maximum degree below 2 q 2q 2 q . Write E q E_q E q for its edge count, so its right order is at most 128 E q / q 128E_q/q 128 E q / q .
In each band split the left vertices at current degree q ( ln q ) k q(\ln q)^k q ( ln q ) k . Make a low group of those at or below this threshold and a high group of those above it, keeping their incident edges as two subtargets. In each subtarget peel any left vertex whose current degree is below one eighth of its degree just before this split, and any right vertex whose current degree is below q / 2 16 q/2^{16} q / 2 16 . The total left loss across both groups is at most E q / 8 E_q/8 E q /8 , while total right loss is at most 2 ( 128 / 2 16 ) E q 2(128/2^{16})E_q 2 ( 128/ 2 16 ) E q since each right vertex can appear in at most two groups. The surviving subgraphs therefore keep an absolute positive fraction of the band’s edges.
Set d ′ = ⌊ q / 2 16 ⌋ d'=\lfloor q/2^{16}\rfloor d ′ = ⌊ q / 2 16 ⌋ . Keep the low-group subgraph as it is. It has minimum degree at least d ′ d' d ′ and maximum degree at most A ∗ d ′ ( ln d ′ ) κ A_*d'(\ln d')^\kappa A ∗ d ′ ( ln d ′ ) κ for a fixed A ∗ A_* A ∗ , since the original right degrees in this band were below 2 q 2q 2 q and q / d ′ q/d' q / d ′ is bounded. It satisfies the hypotheses of Theorem 7.1 .
For the high group independently retain exactly d ′ d' d ′ edges at each right vertex, uniformly among its currently incident edges. Every left vertex keeps, in expectation, at least d ′ / ( 2 q ) d'/(2q) d ′ / ( 2 q ) of its current degree, a fixed positive fraction. Each left degree before this step is at least q ( ln q ) κ / 8 q(\ln q)^\kappa/8 q ( ln q ) κ /8 . The probability of dropping below half its mean is exp ( − Ω ( q ) ) \exp(-\Omega(q)) exp ( − Ω ( q )) by the binomial-type Chernoff bound. A left bad event shares variables with at most 2 q d 0 B 2qd_0^B 2 q d 0 B others, since each selected right vertex had fewer than 2 q 2q 2 q neighbors and each left degree is at most d 0 B d_0^B d 0 B . The symmetric local lemma gives a choice retaining the required fraction at every left vertex. The final edge count is at least d ′ / ( 2 q ) d'/(2q) d ′ / ( 2 q ) of that before this step. The normalized subtarget has exact right degree d ′ d' d ′ and left minimum at least c ∗ d ′ ( ln d ′ ) κ c_*d'(\ln d')^\kappa c ∗ d ′ ( ln d ′ ) κ , for a fixed c ∗ > 0 c_*>0 c ∗ > 0 . For all sufficiently large d ′ d' d ′ this is at least d ′ ( ln d ′ ) κ / 2 d'(\ln d')^{\kappa/2} d ′ ( ln d ′ ) κ /2 . Its maximum degree is at most ( d ′ ) B + 1 (d')^{B+1} ( d ′ ) B + 1 , since q ≥ d 0 / 2 q\ge d_0/2 q ≥ d 0 /2 . Because d ′ ≤ d 0 B d'\le d_0^B d ′ ≤ d 0 B and ln d 0 = O ( ln d ′ ) \ln d_0=O(\ln d') ln d 0 = O ( ln d ′ ) , the local density assumption of the incidence estimate is inherited, with a fixed constant B 1 B_1 B 1 . It satisfies the hypotheses of Theorem 8.1 with τ = κ / 2 \tau=\kappa/2 τ = κ /2 .
Sum the edge masses.
The subtargets W W W produced by the banding and split have total edge count at least c e ( G 0 ) ce(G_0) ce ( G 0 ) for an absolute c > 0 c>0 c > 0 . They need only be subgraphs of the original target. Their vertices may overlap across bands or across the two groups, which does not affect monotonicity of the Ramsey property. The same host arrows every W W W . For some W W W it has m = e ( H ) ≤ M 1 d ′ ( W ) e ( W ) m=e(H)\le M_1d'(W)e(W) m = e ( H ) ≤ M 1 d ′ ( W ) e ( W ) , for a fixed sufficiently large M 1 M_1 M 1 depending on M 0 M_0 M 0 . Otherwise we would have
c e ( G 0 ) ≤ ∑ W e ( W ) < m M 1 ∑ W 1 d ′ ( W ) = O ( m M 1 d 0 ) ≤ O ( M 0 M 1 e ( G 0 ) ) (37) ce(G_0)\le\sum_W e(W)<\frac{m}{M_1}\sum_W\frac{1}{d'(W)}=O\left(\frac{m}{M_1d_0}\right)\le O\left(\frac{M_0}{M_1}e(G_0)\right) \tag*{(37)} ce ( G 0 ) ≤ W ∑ e ( W ) < M 1 m W ∑ d ′ ( W ) 1 = O ( M 1 d 0 m ) ≤ O ( M 1 M 0 e ( G 0 ) ) (37)
contradicting large enough M 1 M_1 M 1 . The sum is geometric, since there are at most two subtargets per dyadic q q q and d ′ ( W ) ≥ q / 2 17 d'(W)\ge q/2^{17} d ′ ( W ) ≥ q / 2 17 for sufficiently large d 0 d_0 d 0 . The near-regular or incidence estimate contradicts the cheap host of this W W W because d ′ ( W ) → ∞ d'(W)\to\infty d ′ ( W ) → ∞ . This rules out every sequence at a fixed linear multiplier.
Finally let I ( C ) I(C) I ( C ) be the infimum of R ^ ( G ) / ( C e ( G ) ) \widehat{R}(G)/(Ce(G)) R ( G ) / ( C e ( G )) over the target class at density at least C C C . It is finite, since the class is nonempty and each finite graph has a finite size Ramsey number. The excluded sequences show I ( C ) → ∞ I(C)\to\infty I ( C ) → ∞ . For all sufficiently large C C C , take f ( C ) = C I ( C ) / 2 f(C)=CI(C)/2 f ( C ) = C I ( C ) /2 to obtain the strict claimed inequality. Isolated vertices cause no difficulty in taking subtargets. The original condition forces e ( G ) > 0 e(G)>0 e ( G ) > 0 for C > 0 C>0 C > 0 , and the lower bound on any subtarget is a lower bound on the original graph.
Extend f f f to smaller real arguments arbitrarily.
Acknowledgments
The authors acknowledge assistance from OpenAI’s ChatGPT and Codex in mathematical exploration and preparation of the manuscript. The authors are responsible for the results and exposition.
Email address , Will Howe: howew@purdue.edu
Email address , Grant Huffman: huffma97@purdue.edu
Email address , Jensen Kohlmeyer: jenwin@purdue.edu
Email address , Liam Kruer: kruerl@purdue.edu