betaFeedback

WorksMathematics

Size Ramsey numbers at high average degree

Abstract

We prove that there is a function ff with f(C)/C→∞f(C)/C\to\infty such that every finite simple graph GG of positive order with e(G)≥Cv(G)e(G)\ge C v(G) satisfies R^(G)>f(C)e(G)\widehat{R}(G)>f(C)e(G) for all sufficiently large CC. The estimate is uniform in the order, number of components, and component multiplicities of the target. The proof combines an entropy estimate for connected component types with adaptive sampling and sparse marks on intersections of host neighborhoods. Separate arguments handle targets with a narrow degree range and strongly unbalanced incidence targets. Dyadic degree reductions assemble the estimates without a loss depending on the number of degree scales.

Introduction

For finite simple graphs HH and GG, write H→GH \to G if every red-blue coloring of E(H)E(H) contains a monochromatic subgraph isomorphic to GG. 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\}.

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) must grow faster than the edge-to-vertex ratio of GG, uniformly over all graphs of large density. We establish this assertion.

Theorem 1.1. There exists a function f:R→Rf : \mathbb{R} \to\mathbb{R} such that

lim⁡C→∞f(C)C=∞\lim_{C \to\infty} \frac{f(C)}{C} = \infty

and, for every sufficiently large CC, every finite simple graph GG with v(G)>0v(G) > 0 and e(G)≥Cv(G)e(G) \ge Cv(G) satisfies

R^(G)>f(C)e(G).\widehat{R}(G) > f(C)e(G).

Equivalently, for every fixed M>0M > 0 there is CMC_M such that R^(G)>MCe(G)\widehat{R}(G) > MC e(G) whenever C≥CMC \ge C_M and e(G)≥Cv(G)>0e(G) \ge Cv(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 r2e(H)r^2e(H) for non-star connected targets when rr 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) 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) and e(G)e(G), and its minimum and maximum degrees by δ(G)\delta(G) and Δ(G)\Delta(G). All auxiliary target graphs have at least one edge. Entropy formulas use the continuous convention 0log⁡0=00\log0=0; terms with a zero coefficient in tlog⁡(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 hh host vertices meets at most Δ(G)h\Delta(G)h edges of a target copy. If every target set of order hh spans at most σh\sigma h edges, a host-edge set supported on hh vertices has capacity at most σh\sigma 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 AiA_i are determined by subsets of a finite family of independent variables. Join two events when their variable sets intersect. If 0<xi<10<x_i<1 and

Pr⁡(Ai)≤xi∏j∼i(1−xj),\Pr(A_i)\leq x_i\prod_{j\sim i}(1-x_j),

then there is positive probability that no AiA_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 BB is determined by a variable set SS, then

Pr⁡(B∣⋂iAic)≤Pr⁡(B)∏i:S∩Si≠∅(1−xi)−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}.

In particular, if every variable occurs in events of total weight at most q≤1/2q\leq1/2, a condition on uu variables incurs a factor at most exp⁡(2qu)\exp(2qu).

Proof. The usual induction proving the asymmetric local lemma also gives Pr⁡(Ai∣⋂j∈JAjc)≤xi\Pr(A_i\mid\bigcap_{j\in J}A_j^c)\leq x_i for any set JJ excluding ii. The event BB is independent of the joint family whose variable sets avoid SS. Condition first on their avoidance. Dividing by the conditional probability of avoiding the remaining events gives the displayed product. Finally, −log⁡(1−xi)≤2xi-\log(1-x_i)\leq2x_i when xi≤1/2x_i\leq1/2, and the sum of the weights of events touching SS is at most ququ. □

Lemma 2.2 (A read bound). Let X1,…,XNX_1,\ldots,X_N be indicators determined by independent variables, with each variable affecting at most rr indicators. If μ=∑iEXi\mu=\sum_i\mathbb{E}X_i, then

Pr⁡(∑iXi≤μ2)≤exp⁡(−μ8r).\Pr\left(\sum_i X_i\leq\frac{\mu}{2}\right)\leq\exp\left(-\frac{\mu}{8r}\right).

Proof. Product Hölder gives E∏igi≤∏i(Egir)1/r\mathbb{E}\prod_i g_i \le\prod_i(\mathbb{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 rr factors using that variable. Apply the inequality to gi=exp⁡(−Xi/r)g_i=\exp(-X_i/r). Markov’s inequality bounds the desired probability by

exp⁡(μ/(2r))∏i[1−(1−e−1)EXi]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).

Now 1−e−1−1/2>1/81-e^{-1}-1/2>1/8. This is a standard read-rr 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 J0J_0 is a subgraph of a graph JJ with e(J0)>0e(J_0)>0, then

R^(J)≥Δ(J)τ(J0)2≥Δ(J)e(J0)2Δ(J0).\widehat{R}(J)\ge\frac{\Delta(J)\tau(J_0)}{2}\ge\frac{\Delta(J)e(J_0)}{2\Delta(J_0)}.

where τ\tau is the vertex-cover number.

Proof. In a host with fewer than Δ(J)τ(J0)/2\Delta(J)\tau(J_0)/2 edges, fewer than τ(J0)\tau(J_0) vertices have degree at least Δ(J)\Delta(J). Color all edges meeting those vertices blue and the remaining edges red. The red graph has maximum degree below Δ(J)\Delta(J), and the blue graph has a vertex cover too small to contain J0J_0. The second inequality follows because a vertex cover of J0J_0 meets at most Δ(J0)\Delta(J_0) edges per vertex. □

Lemma 2.4 (Restricted-star count). Let P,k,aP,k,a be positive integers. Let a host vertex set UU have order kk and span at most PkPk edges. For some vertices v∈Uv\in U, designate a pool of at most CvC_v possible neighbors, where 1≤Cv≤P1\le C_v\le P. Suppose tvt_v selected edges are assigned to vv from that pool, with each edge assigned at most once, and put t=∑vtv≤at=\sum_v t_v\le a. For fixed pools and counts, the number of possible aa-edge subsets is at most

(Pka−t)∏v(Cvtv).\binom{Pk}{a-t}\prod_v\binom{C_v}{t_v}.

If this number is positive, its logarithm is at most

alog⁡(Pk/a)+2a−∑vtvlog⁡(P/Cv).a\log(Pk/a)+2a-\sum_v t_v\log(P/C_v).

Terms with tv=0t_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 ∑vtvlog⁡(t/tv)≤tlog⁡k\sum_v t_v\log(t/t_v)\le t\log k bound the assigned choices by tlog⁡(ePk/t)−∑vtvlog⁡(P/Cv)t\log(ePk/t)-\sum_v t_v\log(P/C_v). Combining this with the unassigned choices costs at most a log⁡2\log2 beyond alog⁡(ePk/a)a\log(ePk/a). □

Lemma 2.5 (Centers for a candidate list). Let D,T>0D,T>0, let s≥2s\ge2 be an integer, and let YY be a finite set of vertices, each of degree at most DD in a graph. Suppose every subset of YY of order at most ss has more than TT common neighbors. If ∣Y∣>s|Y|>s and ϑ=log⁡(2D/T)/(s−1)<1\vartheta=\log(2D/T)/(s-1)<1, at least T/2T/2 vertices are adjacent to a (1−ϑ)(1-\vartheta) fraction of YY.

Proof. Put az=∣N(z)∩Y∣a_z=|N(z)\cap Y|. Counting pairs of an ss-subset of YY and a common neighbor gives

∑z(az/∣Y∣)s≥T,∑zaz/∣Y∣≤D.\sum_z(a_z/|Y|)^s\ge T,\qquad\sum_z a_z/|Y|\le D.

The first inequality uses (azs)/(∣Y∣s)≤(az/∣Y∣)s\binom{a_z}{s}/\binom{|Y|}{s}\le(a_z/|Y|)^s. The terms with az<(1−ϑ)∣Y∣a_z<(1-\vartheta)|Y| contribute at most D(1−ϑ)s−1≤T/2D(1-\vartheta)^{s-1}\le T/2. Each remaining term is at most one. □

References

  1. [1]D. Conlon, J. Fox and Y. Wigderson, Three early problems on size Ramsey numbers, Combinatorica 43 (2023), 743–768. doi:10.1007/s00493-023-00034-7.DOI
  2. [2]L. DeBiasio, A new multicolor size-Ramsey numbers of connected graphs, arXiv:2404.05856v3, 2026. Version of April 8, 2026.arxiv.org/abs/2404.05856
  3. [3]P. Erdős, Some of my favourite problems which recently have been solved, in Proceedings of the International Mathematical Conference, Singapore, 1981, North-Holland Mathematics Studies 74, North-Holland, Amsterdam, 1982, 59–79. doi:10.1016/S0304-0208(08)70415-8.DOI
  4. [4]P. Erdős and R. J. Faudree, Size Ramsey functions, in Sets, Graphs and Numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam, 1992, 219–238.
  5. [5]P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–161. doi:10.1007/BF02018930.DOI
  6. [6]P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. János Bolyai 10, North-Holland, Amsterdam, 1975, 609–627.
  7. [7]Erdős Problem a Day, Erdős problem 911: working report, July 27, 2026, accessed November 5, 2026. https://erdosproble m aday.com/report/911.
  8. [8]D. Gavinsky, S. Lovett, M. Saks and S. Srinivasan, A tail bound for read-k families of functions, Random Structures Algorithms 47 (2015), 99–108. arXiv:1205.1478.arxiv.org/abs/1205.1478
  9. [9]C. Karoubi, Erdős problem 911: public working notes, contribution to the GPT-Erdos project, January 19, 2026.
  10. [10]O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs, SIAM J. Discrete Math. 16 (2002), 99–113. doi:10.1137/S0895480101384086.DOI

Paper details

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

views · 10

downloads · 0

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

  • Mathematics

ChatGPT, Codex

View statement
Looking for related papers…
Contents