ERDŐS/DAILY ▸

← back to the ledger

ERDőS #568 · PARTIAL

Erdős problem #568: quadratic clique-Ramsey versus Ramsey size-linearity

Date of audit: 2026-07-27

Claim labels used below:

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser path and visually checked the rendered page. I then separately checked its LaTeX view. The live page was marked OPEN on 2026-07-27. It showed:

Thus the mandatory stop condition was not triggered.

The following is the verbatim mathematical text from the page’s LaTeX view:

> Let \(G\) be a graph such that \(R(G,T_n)\ll n\) for any tree \(T_n\) on \(n\) vertices and \(R(G,K_n)\ll n^2\). Is it true that, for any \(H\) with \(m\) edges and no isolated vertices,

> \[ > R(G,H)\ll m? > \]

The only additional mathematical sentence on the live page is:

> In other words, is \(G\) Ramsey size linear?

1. Outcome

I did not prove or disprove the full assertion. I obtained two exact reductions and one exhaustive small-\(G\) frontier.

1. (a) The tree hypothesis is redundant for every fixed \(G\).

2. (a) It is enough to prove the desired estimate for connected target graphs of minimum degree at least two. More precisely, if \(C_2(H)\) is the 2-core of \(H\), \(g=v(G)\), and \(h=v(H)\), then

\[ R(G,H)\le R(G,C_2(H))+(g-1)(h-1) \tag{1} \]

whenever \(C_2(H)\ne\varnothing\); forests satisfy the analogous bound

\[ R(G,H)\le (g-1)(h-1)+1. \tag{2} \]

3. (b)+(a) The quadratic clique hypothesis forces \(m_2(G)\le2\). Among connected graphs on at most five vertices satisfying this necessary density condition, every graph is certified Ramsey size-linear by the 1993 Erdős–Faudree–Rousseau–Schelp results except one isomorphism class: \(K_4^*\), obtained by subdividing one edge of \(K_4\) once. This does not resolve the order-five case: the sources checked do not establish that \(R(K_4^*,K_n)=O(n^2)\), and \(K_4^*\) itself is still not known to be Ramsey size-linear.

The standalone verifier is erdos568_wave6e_verify.py.

2. What the two hypotheses really say

2.1 The tree test is automatic

(b) Let \(g=v(G)\). Since \(G\subseteq K_g\), monotonicity and Chvátal’s exact tree–clique theorem give, for every \(n\)-vertex tree \(T_n\),

\[ R(G,T_n)\le R(K_g,T_n)=(g-1)(n-1)+1. \tag{3} \]

Thus \(R(G,T_n)=O_G(n)\) holds for every fixed graph \(G\), independently of the second hypothesis. Chvátal’s one-page paper states exactly

\[ R(T_m,K_n)=1+(m-1)(n-1): \]

V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.

Consequently, the live question is exactly:

> If a fixed \(G\) satisfies \(R(G,K_n)=O_G(n^2)\), must \(G\) be Ramsey size-linear?

2.2 The quadratic test forces the EFRS density condition

For a graph \(J\) with at least three vertices, put

\[ m_2(J)=\max_{\substack{J'\subseteq J\\v(J')\ge3}} \frac{e(J')-1}{v(J')-2}. \]

(b) Spencer’s off-diagonal lower bound, in the form recorded by Bradač–Gishboliner–Sudakov, is

\[ R(J,K_n)=\widetilde{\Omega}_J\!\left(n^{m_2(J)}\right). \tag{4} \]

If \(R(G,K_n)=O_G(n^2)\) and some \(J\subseteq G\) had

\[ \frac{e(J)-1}{v(J)-2}>2, \]

then monotonicity \(R(J,K_n)\le R(G,K_n)\) and (4) would contradict one another: a fixed positive power of \(n\) eventually dominates every polylogarithm. Hence

\[ \boxed{\quad e(J)\le2v(J)-3\quad \text{for every }J\subseteq G\text{ with }v(J)\ge3,\quad} \tag{5} \]

or equivalently \(m_2(G)\le2\).

The primary references checked were:

(a) Conversely, Ramsey size-linearity immediately implies the quadratic test, since \(e(K_n)=\binom n2\). Therefore the only nontrivial direction of problem #568 is the proposed converse.

(a) There is also a useful host-graph translation. The bound \(R(G,K_n)=O(n^2)\) says that every \(N\)-vertex \(G\)-free graph has an independent set of order \(\Omega_G(\sqrt N)\). Ramsey size-linearity asks for much more: the complement of every \(G\)-free graph on \(O_G(m)\) vertices must contain every \(m\)-edge graph without isolates. The gap is an upgrade from one large independent set to sparse-graph universality.

3. New elementary reduction to 2-core targets

Proposition

(a) Let \(G,H\) be finite simple graphs, \(g=v(G)\), \(h=v(H)\), and let \(F=C_2(H)\) be the 2-core of \(H\).

\[ R(G,H)\le R(G,F)+(g-1)(h-1). \tag{6} \]

\[ R(G,H)\le(g-1)(h-1)+1. \tag{7} \]

Proof of (6)

Set

\[ r=R(G,F),\qquad N=r+(g-1)(h-1). \]

Consider a red/blue colouring of \(K_N\) having no red \(G\), and write \(B\) for its blue graph.

Iteratively delete a vertex whose current blue degree is less than \(h-1\). Let the deletion sequence be

\[ x_1,x_2,\ldots,x_L. \]

I claim that

\[ L\le(g-1)(h-1). \tag{8} \]

Indeed, if \(L>(g-1)(h-1)\), greedily choose vertices in deletion order. After choosing a vertex, discard it and its later blue neighbours. At most

\[ 1+(h-2)=h-1 \]

vertices are discarded at each choice. After \(g-1\) choices, fewer than \(L\) vertices have been discarded, so a \(g\)-th choice is possible. Every pair of chosen vertices is red, giving a red \(K_g\), and hence a red copy of \(G\), a contradiction. This proves (8).

The surviving graph \(B'\) therefore has at least \(r\) vertices and minimum blue degree at least \(h-1\). It contains no red \(G\), so its blue edges contain a copy of \(F\).

Now recover \(H\) from \(F\). Run the usual 2-core deletion on \(H\), recording vertices

\[ y_1,y_2,\ldots,y_t. \]

At the instant \(y_i\) was deleted, it had at most one neighbour among

\[ V(F)\cup\{y_{i+1},\ldots,y_t\}. \tag{9} \]

Starting with the blue copy of \(F\), embed \(y_t,y_{t-1},\ldots,y_1\). If the next vertex has no already embedded neighbour, choose any unused vertex of \(B'\). If it has one already embedded neighbour \(z\), choose an unused blue neighbour of the image of \(z\). At that moment at most \(h-2\) other vertices are already used, while every vertex of \(B'\) has at least \(h-1\) blue neighbours. Thus a choice always exists. Property (9) ensures that every edge of \(H\) is respected. This proves (6).

Proof of (7)

(b) Every \(h\)-vertex forest is a subgraph of an \(h\)-vertex tree \(T_h\). Hence

\[ R(G,H)\le R(K_g,T_h)=(g-1)(h-1)+1 \]

by Chvátal’s theorem.

Corollary: exact remaining target family

(a) For fixed \(G\), Ramsey size-linearity is equivalent to having a uniform linear bound only for connected graphs \(F\) with \(\delta(F)\ge2\).

To see this, first note that for disjoint target components,

\[ R\!\left(G,F_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}F_s\right) \le\sum_{i=1}^s R(G,F_i). \tag{10} \]

Partition a clique into parts of those sizes. If there is no red \(G\), each part supplies its corresponding blue \(F_i\), and the copies are disjoint.

Now suppose

\[ R(G,F)\le C_G e(F) \tag{11} \]

for every connected \(F\) of minimum degree at least two. The components of \(C_2(H)\) all have minimum degree at least two, so (10) gives

\[ R(G,C_2(H))\le C_G e(C_2(H))\le C_Gm. \]

If \(H\) has no isolated vertices and \(m=e(H)\), then \(h\le2m\). Substitution into (6) gives

\[ R(G,H)\le \bigl(C_G+2(g-1)\bigr)m. \tag{12} \]

Forests are covered by (7). Necessity of (11) is immediate from the definition.

This reduction removes all tree components and all pendant forests, with an explicit loss of only \(2(g-1)m\).

4. Exact small-\(G\) frontier

Reduction to connected \(G\)

(a) If \(G=G_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}G_s\), then

\[ R(G,H)\le\sum_i R(G_i,H). \tag{13} \]

The proof is the same partition argument as for (10). Also, every component \(G_i\) is a subgraph of \(G\), so the quadratic clique hypothesis passes from \(G\) to \(G_i\). Thus a counterexample to #568 would have a connected counterexample component.

Orders at most five

The following two sufficient results are from Erdős–Faudree–Rousseau–Schelp:

1. (b) Every connected graph \(G\) with \(e(G)\le v(G)+1\) is Ramsey size-linear.

2. (b) Every graph \(K_1+T\), where \(T\) is a forest and \(+\) denotes the graph join, is Ramsey size-linear. By monotonicity, the same is true of every graph having a vertex \(x\) for which \(G-x\) is a forest.

These statements are recorded verbatim as results of the 1993 paper in the author-hosted version of P. N. Balister, R. H. Schelp, and M. Simonovits, A note on Ramsey size-linear graphs, J. Graph Theory 39 (2002), 1–5, DOI. The original source is P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Ramsey size linear graphs, Combin. Probab. Comput. 2 (1993), 389–399.

(a)+(b) Suppose connected \(G\) satisfies the live quadratic hypothesis and \(v(G)=g\le4\). By (5),

\[ e(G)\le2g-3\le g+1, \]

so EFRS certifies \(G\) as Ramsey size-linear.

Now let \(g=5\). Again \(e(G)\le7\). If \(e(G)\le6=g+1\), EFRS applies. It remains to inspect \(e(G)=7\). Condition (5) excludes a \(K_4\) subgraph. The complement \(\overline G\) has three edges, and those three edges cannot all be incident with one vertex, since that would leave a \(K_4\) in \(G\). Up to isomorphism there are exactly three possibilities:

| \(\overline G\) | \(G\) | rigorous status |

|---|---|---|

| \(K_3\dot\cup2K_1\) | \(K_1+K_{1,3}\) | EFRS \(K_1+\)forest class |

| \(P_4\dot\cup K_1\) | \(K_1+P_4\) | EFRS \(K_1+\)forest class |

| \(P_3\dot\cup K_2\) | \(K_4^*\) | not certified; the remaining frontier |

Here \(K_4^*\) is \(K_4\) with one edge replaced by a two-edge path. Direct calculation gives

\[ v(K_4^*)=5,\qquad e(K_4^*)=7,\qquad m_2(K_4^*)=2. \tag{14} \]

Therefore:

\[ \boxed{\text{Any counterexample to #568 on at most five vertices must be }K_4^*.} \tag{15} \]

This is only a necessary-frontier statement. It does not assert that \(K_4^*\) satisfies the live quadratic premise.

Exhaustive recomputation

(d) The verifier generated all \(2^{\binom n2}\) labelled graphs for \(n\le5\), quotiented them by all \(n!\) vertex permutations, recomputed (5) on every vertex subset, and tested both quoted EFRS sufficient conditions. It used no stored graph atlas. The output was:

2-core deletion-order checks: 33868 labelled graphs passed
host-pruning checks:          1004340 graph/parameter cases passed

connected unlabeled small-G frontier
 v | all | density-eligible | not EFRS/apex-forest certified
 1 |   1 |                1 |                                0
 2 |   1 |                1 |                                0
 3 |   2 |                2 |                                0
 4 |   6 |                5 |                                0
 5 |  21 |               16 |                                1

5-vertex, 7-edge density-eligible isomorphism classes: 3
unique uncertified class: K4 with one edge subdivided once (K4*)
recomputed m2(K4*) = 2
recomputed treewidth(K4*) = 3
ALL CHECKS PASSED

The same program independently exhausts:

Two runs, the second with a different PYTHONHASHSEED, produced identical output. On this VM each full run took about nine seconds. The verifier SHA-256 at the time of this report was

c4f474583bccdcc76b882217e626142fc5b88344e7591d52f746506f14e616f6

Run it with:

python3 runs/erdos568_wave6e_verify.py

5. Literature audit through 2026-07-27

The original and later general results

(b) The Cambridge publisher record for EFRS93 says:

The 2002 Balister–Schelp–Simonovits paper proves that sufficiently long path additions preserve Ramsey size-linearity and records the additional EFRS classes used above.

(b) Bradač–Gishboliner–Sudakov (2024) explicitly state that whether every \(m_2(H)\le2\) graph is Ramsey size-linear “seem[s] to be still out of reach.” They prove:

They do not claim \(K_4^*\) Ramsey size-linear. Their treewidth bound gives only

\[ R(K_4^*,K_n)=O(n^3), \]

since \(K_4^*\) has treewidth three, while Spencer gives a polylogarithmically weakened quadratic lower bound from (14). I found no checked primary source establishing the \(O(n^2)\) premise for \(K_4^*\), so I do not assume it.

(b) Yuval Wigderson’s Infinitely many minimally non-Ramsey size-linear graphs, European J. Combin. 128 (2025), 104175, settles a different EFRS question: there are infinitely many graphs that are non-Ramsey-size-linear while every proper subgraph is Ramsey-size-linear. It does not claim the implication in #568.

2026 papers

I checked the two directly relevant 2026 arXiv papers returned by title/phrase and forward searches:

(b) These papers concern cycles (and related clique/multicolour extensions). The latter proves \(R(C_k,H)\le(k-1)e(H)+1\), so cycles form a positive class, but neither paper states or proves the quadratic-clique-to-size-linearity implication of #568.

Searches by the exact problem sentence, “Ramsey size-linear,” \(m_2\le2\), \(R(G,K_n)=O(n^2)\), and forward citations of EFRS93/BGS24 found no primary source claiming #568 solved. This is a search report, not a proof that no such paper exists.

6. Exact remaining obstruction and why standard machinery stalls

What remains after the reductions

(a) It now suffices—and is necessary—to prove the following:

> Fix \(G\) with \(R(G,K_n)=O_G(n^2)\). Show that

> \[ > R(G,H)=O_G(e(H)) > \]

> for every connected \(H\) with \(\delta(H)\ge2\).

All disconnected targets, tree components, and pendant forests then follow from (6), (7), and (10).

The missing local-to-universal lemma

(c) The clique premise guarantees an independent set of order \(\Omega_G(\sqrt N)\) in every \(N\)-vertex \(G\)-free red graph. This is enough to place roughly \(\sqrt m\) high-degree target vertices when \(N=\Theta(m)\). After deleting the \(k\) highest-degree target vertices, the remaining maximum degree is at most

\[ \frac{2m}{k+1}=O(\sqrt m). \]

However, standard graph-packing or greedy embedding then also needs control of red maximum degrees, or blue common neighbourhoods of already embedded pairs. A \(G\)-free red graph can still contain vertices of degree \(\Theta(N)\), and the quadratic clique premise alone supplies no known regularisation or codegree statement strong enough to finish the packing.

The 2-core proof works because every reinserted target vertex has at most one already embedded neighbour; minimum blue degree is enough. Passing from the 2-core to the 3-core would require reinserting vertices with two already embedded neighbours, hence unused common blue neighbours. The precise missing ingredient is a reservoir/embedding lemma that derives suitably large common blue neighbourhoods—at least for the pairs created by an adaptive target embedding—from only:

1. red \(G\)-freeness, and

2. \(R(G,K_n)=O_G(n^2)\).

No such lemma was found in the checked sources. Requiring large codegree for every pair would be unnecessarily strong and is not claimed here; the unresolved issue is to find an embedding whose required pairs are good.

Why a larger finite search does not close the gap

(a)+(d) A finite Ramsey SAT computation can test selected \(G,H,N\), but it cannot establish the uniform quantifier over all \(m\). A direct encoding at \(N=\Theta(m)\) has \(\binom N2=\Theta(m^2)\) colour variables and, without highly target-specific encodings, \(N^{v(H)}/|\operatorname{Aut}(H)|\) forbidden-blue-copy clauses; \(v(H)\) may be \(2m\). Thus the direct clause count is \(m^{\Theta(m)}\), beyond a few CPU-minutes even for modest \(m\), and no finite cutoff supplies the missing asymptotic uniformity. The needed next step is a structural lemma, not a larger brute-force sweep.

7. Claim audit

| Result | label |

|---|---|

| Tree hypothesis is automatic | (b), Chvátal |

| Quadratic clique bound implies \(m_2(G)\le2\) | (b), Spencer |

| 2-core Ramsey inequality (6) | (a) |

| Reduction to connected \(\delta\ge2\) targets | (a) |

| Unique order-\(\le5\) uncertified density frontier \(K_4^*\) | (a)+(b) |

| Counts through five vertices and 1,004,340 pruning checks | (d) |

| A pair-codegree/reservoir lemma is the natural missing step | (c) |

| Full Erdős problem #568 | not resolved |

PARTIAL: Proved the explicit 2-core reduction \(R(G,H)\le R(G,C_2(H))+(v(G)-1)(v(H)-1)\), reduced #568 to connected minimum-degree-two targets, and exhaustively isolated \(K_4^*\) as the unique order-at-most-five density frontier; the quadratic-to-universality step remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger