Erdős problem #567 — wave 6d

Date: 2026-07-27 UTC

Claim labels

• [A] elementary-rigorous: proved here from elementary graph arguments.
• [B] rigorous-modulo-named-theorem: the only external mathematical input is explicitly named.
• [C] plausible/structural-unverified: an observation or possible route, not a theorem.
• [D] computational-only: established only for the finite range actually enumerated.

No claim below closes Erdős #567. The verified progress is an exact answer for the infinite target family of matchings, together with a finite obstruction reduction and a precise account of why the standard general routes stop.

0. Mandatory live-page check

I fetched the live page, its

discussion, and its LaTeX-source

endpoint through the Bright Data browser path, not datacenter curl, on 2026-07-27.

The exact current statement from the page's “View the LaTeX source” endpoint is:

> Let $G$ be either $Q_3$ or $K_{3,3}$ or $H_5$ (the last formed by adding two vertex-disjoint chords to $C_5$). Is it true that, if $H$ has $m$ edges and no isolated vertices, then\[R(G,H)\ll m?\]

Live status and collision markers:

• Status: OPEN.
• Claimed proofs: 0 claimed proofs for this problem.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• The page was last edited 18 January 2026.
• There is one comment, by Alfaiz at 05:26 on 7 November 2025: “Correction: [BGS23] is not loading any reference here. (The site has been updated to address this comment.)” It makes no mathematical claim.

Thus none of the mandatory stop conditions applied.

The page additionally records:

• this is a special case of problem #566;
• Erdős specifically asked about $G=K_{3,3}$ in [Er95, p.177];
• $H_5$ is also $K_4^*$, obtained by subdividing one edge of $K_4$;
• Bradač, Gishboliner, and Sudakov proved that every subdivision of $K_4$ on at least six vertices is Ramsey size-linear, and proved $R(H_5,H)=O(e(H))$ when the target $H$ is bipartite and has no isolated vertices.

The problem concerns the ordinary vertex Ramsey number $R(G,H)$, despite the terminology “Ramsey size-linear”; it is not a size-Ramsey-number question.

1. Primary-source literature audit

1. [B] Erdős–Faudree–Rousseau–Schelp, Ramsey Size Linear Graphs, Combinatorics, Probability and Computing 2 (1993), 389–399, DOI 10.1017/S096354830000078X, defines the property and proves, among other results, that connected $G$ with $e(G)\leq v(G)+1$ are Ramsey size-linear. Its publisher abstract also states the non-linearity result for $e(G)\geq2v(G)-2$.

2. [B] Balister–Schelp–Simonovits, A note on Ramsey size-linear graphs, Journal of Graph Theory 39 (2002), 1–5, author-hosted full text, records the EFRS sufficient criterion that a bipartite $G$ with $\operatorname{ex}(N,G)=O(N^{3/2})$ is Ramsey size-linear, and proves a long-path extension theorem. It does not settle any of the three graphs here.

3. [B] Bradač–Gishboliner–Sudakov, On Ramsey size-linear graphs and related questions, arXiv:2202.10388v2, published as DOI 10.1137/22M1481713, proves exactly the two results quoted on the live page: Theorem 3 handles $K_4^=H_5$ against bipartite targets, and Theorem 4 handles all subdivisions of $K_4$ with at least six vertices. The introduction explicitly says it cannot answer whether $K_4^$ itself is Ramsey size-linear.

4. [B] Cambie–Freschi–Morawski–Petrova–Pokrovskiy, Ramsey number of a cycle versus a graph of a given size, arXiv:2601.10238 (January 2026), is a current primary source. Its introduction says that a full answer is still unavailable even for subdivisions of $K_4$. Its Proposition 9 uses the Tutte–Berge formula to solve the matching-target case for cycles. The proof below adapts that mechanism to the three graphs in #567.

5. [B] For the extremal-number route, the primary bounds are:

• Füredi, On a theorem of Erdős and Simonovits on graphs not containing the cube, arXiv:1307.1062, proves

\[ \operatorname{ex}(N,Q_3)

• Erdős–Rényi–T. Sós, On a problem of graph theory, Studia Scientiarum

Mathematicarum Hungarica 1 (1966), 215–235,

primary full text, gives finite-geometry

$C_4$-free graphs with $\Omega(N^{3/2})$ edges. Since $C_4\subset Q_3$, these are

also $Q_3$-free.

• Kővári–Sós–Turán, On a problem of K. Zarankiewicz, DOI 10.4064/cm-3-1-50-57, gives $\operatorname{ex}(N,K_{3,3})=O(N^{5/3})$.
• Alon–Rónyai–Szabó, Norm-Graphs: Variations and Applications, DOI 10.1006/jctb.1999.1906, constructs $K_{3,3}$-free graphs with $\Omega(N^{5/3})$ edges. Hence the $5/3$ order for $K_{3,3}$ is genuine.

Targeted searches for the three graph names together with “Ramsey size-linear”, their exact matching Ramsey numbers, and papers citing BGS found no claimed resolution of #567. This is a search report, not a proof of absence. It agrees with the live page and the January 2026 primary source.

2. Exact progress: all matching targets

Write $nK_2$ for a matching of $n$ edges. In the original problem this target has exactly $m=n$ edges and no isolated vertices.

2.1 A general matching lemma

For a connected graph $G$, let

• $v=v(G)$;
• $\alpha=\alpha(G)$, its independence number;
• $\tau=\tau(G)=v-\alpha$, its minimum vertex-cover number.

Assume the following finite multipartite property:

> (MP) Every complete multipartite graph with at least $\tau+1$ nonempty parts and at least $v$ vertices contains $G$ as a (not necessarily induced) subgraph.

Theorem. [B] If connected $G$ satisfies (MP), then for every integer $n\geq1$,

The only named input is the Tutte–Berge formula.

Lower bounds

First suppose $n\leq\alpha$, precisely the range in which

On $v+n-2$ vertices, let the red graph be

It has no red $G$, because $G$ is connected and both red components have fewer than $v$ vertices. The blue graph is $K_{v-1,n-1}$, whose matching number is $n-1$. Therefore

For every $n$, use $2n+\tau-2$ vertices. Let the blue graph be a clique $K_{2n-1}$ together with $\tau-1$ blue-isolated vertices. Its matching number is $n-1$. The red graph is

If it contained $G$, the vertices of $G$ mapped into the $K_{\tau-1}$ side would form a vertex cover of size at most $\tau-1$, contradicting the definition of $\tau$. Hence

Together these give the lower bound in (1).

Upper bound

Let

and consider a red-blue coloring of $K_N$ with no blue $nK_2$. Let $B$ be its blue graph. By the Tutte–Berge formula there is a set $S$ of size $s$ such that, if $r$ is the number of odd components of $B-S$, then

Since $N\geq2n+\tau-1$, (2) gives

Also $r\leq N-s$. Combining this with (2) gives $s\leq n-1$, and therefore

There are no blue edges between distinct components of $B-S$. Consequently, all edges between distinct components are red: the red graph contains a complete multipartite graph whose nonempty parts are all components of $B-S$. By (3) it has at least $\tau+1$ parts, and by (4) it has at least $v$ vertices. Property (MP) supplies a red $G$, proving (1).

2.2 Verifying (MP) for the three graphs

[A] The graph parameters are

• $H_5$. [A] Five vertices spread over at least four nonempty multipartite parts span either $K_5$ or a graph containing $K_5-e$. Since $H_5$ has a nonedge, it embeds in $K_5-e$. Thus (MP) holds with $\tau+1=4$.

• $K_{3,3}$. [A] Choose six vertices while retaining at least four nonempty parts. The possible part-size profiles are refinements of

\[ (3,1,1,1),\quad(2,2,1,1),\quad(2,1,1,1,1),\quad(1,1,1,1,1,1). \]

In every case the parts can be divided into two groups of total capacity at least three each. Map the two sides of $K_{3,3}$ into those groups. Thus (MP) holds with $\tau+1=4$.

• $Q_3$. [A] Choose eight vertices while retaining at least five nonempty parts. Every partition of $8$ into at least five positive parts can be divided into two groups of sum $4$; the only coarsest cases are

\[ (4,1,1,1,1),\quad(3,2,1,1,1),\quad(2,2,2,1,1), \]

and their refinements. Map the two four-vertex bipartition classes of $Q_3$ into the two groups. Thus (MP) holds with $\tau+1=5$.

2.3 Closed forms

Substitution into (1) gives the following exact formulas for every $n\geq1$:

At the overlapping endpoints the two displayed branches agree.

These are uniform theorems for all $n$, not extrapolations from a computed list. In particular, the leading coefficient $2$ is sharp for matching targets.

3. Exact finite obstruction reduction and independent computation

There is also an exact finite characterization behind the checker.

Proposition. [B] Let $G$ be connected and have at least one edge. There is a coloring of $K_N$ with no red $G$ and no blue $nK_2$ if and only if there are

• an integer $0\leq s\leq N$, and
• a positive-integer partition $p=(p_1,\ldots,p_q)$ of $N-s$

such that

and the complete multipartite graph $K_{p_1,\ldots,p_q}$ is $G$-free.

For the forward implication, take a Tutte–Berge set $S$ in the blue graph and let the $p_i$ be the orders of all components after deleting $S$. Edges between distinct components are red, so the associated complete multipartite graph must be $G$-free.

Conversely, given $(s,p)$, make the blue graph

In any matching, at most $s$ odd clique-components can have their otherwise-unmatched vertex paired to $K_s$. Thus at least

vertices remain unmatched, and (5) prevents a blue $n$-matching. Its red complement consists of $s$ isolated vertices plus $K_{p_1,\ldots,p_q}$, so it has no red connected $G$.

The standalone verifier is:

It uses only the Python standard library and does all of the following from scratch:

1. constructs the three graphs and recomputes $v,e$, all degrees, $\alpha$, and $\tau$;

2. checks by all $5!$ relabelings that the page's $C_5$-plus-two-chords graph is isomorphic to $K_4$ with one edge subdivided;

3. independently checks multipartite containment using two different proper-coloring backtrackers;

4. enumerates every integer partition allowed by (5), producing exact Ramsey values and an explicit $(s,p)$ witness at $R-1$;

5. compares the computed values with the closed forms above.

Command run:

/usr/bin/time -f 'elapsed=%e sec, maxrss=%M KB' \
  python runs/erdos567_wave6d_verify.py

Result:

ALL CHECKS PASSED
elapsed=3.78 sec, maxrss=145360 KB

SHA-256:

e57cb1b1d041ad14594d390ecaf0ded1266e221e31b46001de3bbcc118355028

[D] The exhaustive recomputation covered $1\leq n\leq12$ for $H_5$, $1\leq n\leq15$ for $K_{3,3}$, and $1\leq n\leq20$ for $Q_3$. Its first eight rows are:

The computation verifies a finite prefix; the proof in Section 2 supplies the required uniformity for all $n$.

4. What remains, and the exact walls

1. $H_5$. [B] BGS Theorem 3 already handles every bipartite target. Its key extension lemma (Lemma 2.5) embeds the two sides of a bipartite target from two suitably anticomplete reservoirs. For a nonbipartite target, those two reservoirs do not encode the edges inside a third or higher color class. A sufficient missing ingredient is an arbitrary-target analogue of that extension lemma which embeds the high-degree core of $H$ into the complement of an $H_5$-free host while retaining the $O(e(H))$ vertex budget. No such lemma appears in BGS, and their proof does not imply it.

2. $Q_3$. [B] The EFRS extremal-number criterion would settle this case if one proved

\[ \operatorname{ex}(N,Q_3)=O(N^{3/2}). \]

The verified primary upper bound is only $O(N^{8/5})$, while $C_4$-free constructions give the lower order $\Omega(N^{3/2})$. Thus the exact sufficient missing lemma on this route is the longstanding sharp cube Turán bound. A finite search cannot provide its uniform asymptotic quantifier.

3. $K_{3,3}$. [B] Here the EFRS extremal route cannot be repaired by sharpening constants: primary constructions and KST give

\[ \operatorname{ex}(N,K_{3,3})=\Theta(N^{5/3}), \]

genuinely above the $N^{3/2}$ sufficient threshold. Any proof must exploit more than the global extremal edge count of a $K_{3,3}$-free red graph.

4. [A] The matching proof succeeds because excluding a blue matching has the Tutte–Berge component decomposition, which immediately creates a large red complete multipartite graph. Excluding an arbitrary $m$-edge target has no comparable decomposition. The exact formulas above therefore constitute a sharp concrete regime, but do not imply Ramsey size-linearity for all targets.

No finite computation reported here is presented as resolving the original universal question.

PARTIAL: Proved exact all-n formulas for R(H5,nK2), R(K3,3,nK2), and R(Q3,nK2), with an exhaustive standalone verifier; the full arbitrary-target problem remains open.