Erdős Problem #911

Erdős Problem 911 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/911.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT.
All graphs are finite, simple, undirected. For graphs $G,H$ write $H\to (G,G)$ if for every red/blue coloring of $E(H)$ there is a monochromatic copy of $G$ in $H$. The size Ramsey number of $G$ is \[ \hat R(G):=\min\{|E(H)|: H\to (G,G)\}. \] The question asks whether there exists a function $f:(0,\infty)\to (0,\infty)$ with $\lim_{x\to\infty} f(x)/x=\infty$ such that for all sufficiently large real $C$, every graph $G$ with $n:=|V(G)|$ and $e:=|E(G)|\ge Cn$ satisfies \[ \hat R(G) > f(C)\, e. \]

QUICK LITERATURE/CONTEXT CHECK.
No literature is quoted in the problem text. I will not import external results about size Ramsey numbers.

ATTACK PLAN.
Proof track. Derive general lower bounds on $\hat R(G)$ in terms of $n,e$ and (possibly) other parameters controlled by the hypothesis $e\ge Cn$.

Disproof track. Try to find, for arbitrarily large $C$, graphs $G$ with $e\ge Cn$ but with size Ramsey number $\hat R(G)$ only on the order of $C\,e$ (or smaller). Any universal upper bound of the form $\hat R(G)\le K C e$ for such a family would contradict the desired superlinear $f(C)$.

WORK.
Phase 1: fast reality check (small instance). For $G=K_3$ one can brute-force check that the smallest triangle-Ramsey graph has $6$ vertices and $15$ edges (namely $K_6$), i.e. $\hat R(K_3)=15$. (I verified this by enumerating all graphs on at most $6$ vertices and checking all $2^{|E(H)|}$ two-colorings for a monochromatic triangle.) This sanity-check is consistent with the trivial lower bound $\hat R(G)\ge e(G)$ below.

Lemma 911.1 (trivial edge-count lower bound). For every graph $G$, $\hat R(G)\ge |E(G)|$.

Proof. Let $e=|E(G)|$. If a graph $H$ has $|E(H)|<e$, then $H$ cannot contain a copy of $G$ as a (not-necessarily-induced) subgraph because any copy of $G$ uses $e$ distinct edges. Color the edges of $H$ arbitrarily red/blue; then there is no monochromatic copy of $G$ (indeed no copy at all). Hence no such $H$ is Ramsey for $G$, so the minimum defining $\hat R(G)$ is at least $e$. $\square$

Lemma 911.2 (vertex Ramsey lower bound). Let $R(G)$ denote the usual (two-color) Ramsey number of $G$, i.e. the least integer $N$ such that $K_N\to (G,G)$. If $H\to (G,G)$ then $|V(H)|\ge R(G)$.

Proof. Let $N:=|V(H)|$. Suppose for contradiction that $N<R(G)$. By the definition of $R(G)$, there exists a red/blue coloring of the complete graph $K_N$ with no monochromatic copy of $G$. Restrict this coloring to the edge set $E(H)\subseteq E(K_N)$; since any monochromatic copy of $G$ in $H$ would also be a monochromatic copy of $G$ in $K_N$, the restricted coloring has no monochromatic copy of $G$ in $H$. This contradicts $H\to (G,G)$. $\square$

Lemma 911.3 (first-moment obstruction via random coloring). Fix graphs $G$ and $H$. Let $e:=|E(G)|$ and let $N_G(H)$ be the number of (labeled) subgraphs of $H$ isomorphic to $G$ (equivalently, the number of injections $\varphi:V(G)\hookrightarrow V(H)$ such that $\varphi$ maps edges of $G$ to edges of $H$).

In a uniformly random red/blue coloring of $E(H)$, the expected number of monochromatic copies of $G$ equals $N_G(H)\,2^{1-e}$. In particular, if $N_G(H)<2^{e-1}$ then $H\not\to (G,G)$.

Proof. Color each edge of $H$ independently red/blue with probability $1/2$. Fix a labeled copy $\varphi$ of $G$ in $H$. The event that this copy is monochromatic is the event that all $e$ edges of $\varphi(G)$ are red or all are blue. Each has probability $(1/2)^e$, and the two events are disjoint, so \[\mathbb{P}(\varphi(G)\text{ is monochromatic}) = 2\cdot (1/2)^e = 2^{1-e}. \] Let $X$ be the random variable counting monochromatic labeled copies of $G$ in $H$. Then \[\mathbb{E}X = \sum_{\varphi} \mathbb{P}(\varphi(G)\text{ is monochromatic}) = N_G(H)\,2^{1-e} \] by linearity of expectation. If $N_G(H)<2^{e-1}$ then $\mathbb{E}X<1$, hence there exists at least one coloring with $X=0$, i.e. with no monochromatic copy of $G$; thus $H$ is not Ramsey for $G$. $\square$

VERIFICATION.

• Lemma 911.1 uses only the subgraph containment requirement implicit in $H\to (G,G)$.
• Lemma 911.2 correctly handles the "sparser host" issue by extending a coloring to the complete graph and then restricting.
• Lemma 911.3 uses a labeled copy count; unlabeled versions differ by $|\mathrm{Aut}(G)|$ but the conclusion "$\mathbb{E}X<1$ implies existence of a coloring with $X=0$" is unaffected.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: general lower bounds $\hat R(G)\ge |E(G)|$ (Lemma 911.1) and $|V(H)|\ge R(G)$ for any Ramsey host $H$ (Lemma 911.2). Also, Lemma 911.3 gives a clean probabilistic criterion: any candidate host $H$ with too few copies of $G$ (specifically $N_G(H)<2^{e-1}$) cannot be Ramsey for $G$.

(ii) First gap (crisp): Prove or disprove the existence of a function $f(C)$ with $f(C)/C\to\infty$ such that every graph $G$ with $e(G)\ge C|V(G)|$ satisfies $\hat R(G) > f(C)\,|E(G)|$ for all sufficiently large $C$.

(iii) Top 3 next moves:

1. Disproof attempt: Construct, for arbitrarily large $C$, explicit graphs $G_C$ with $|E(G_C)|\ge C|V(G_C)|$ and prove an upper bound $\hat R(G_C)\le K\,C\,|E(G_C)|$ with an absolute constant $K$. Any such family would rule out superlinear $f$.
2. Proof attempt: Fix $C$ and attempt to show that every $H$ with $|E(H)|\le g(C)\,e$ has $N_G(H)<2^{e-1}$ for some $g(C)$ growing faster than $C$. Combining with Lemma 911.3 would imply the desired lower bound.
3. Computation: For small $C$ and moderate $n$, brute-force search for graphs $G$ with $e\approx Cn$ and compute/estimate $\hat R(G)$ to guess scaling in $C$ (even partial data could suggest whether $\hat R(G)/e$ can stay $O(C)$).

(iv) Minimal counterexample structure:

• To the existence of such $f$: a family $\{G_C\}$ with average degree $\Theta(C)$ but with $\hat R(G_C)=O(C\,e(G_C))$.
• To the nonexistence: a fixed large $C$ and a graph $G$ with $e\ge Cn$ such that every Ramsey host has $\hat R(G)\ge f(C)e$ for some $f(C)\gg C$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT.
All graphs are finite, simple, undirected. For graphs $G,H$ write $H\to (G,G)$ if for every red/blue coloring of $E(H)$ there is a monochromatic copy of $G$ in $H$. The size Ramsey number of $G$ is \[ \hat R(G):=\min\{|E(H)|: H\to (G,G)\}. \] The question asks whether there exists a function $f:(0,\infty)\to (0,\infty)$ with $\lim_{x\to\infty} f(x)/x=\infty$ such that for all sufficiently large real $C$, every graph $G$ with $n:=|V(G)|$ and $e:=|E(G)|\ge Cn$ satisfies \[ \hat R(G) > f(C)\, e. \]

QUICK LITERATURE/CONTEXT CHECK.
No literature is quoted in the problem text. I will not import external results about size Ramsey numbers.

ATTACK PLAN.
Proof track. Derive general lower bounds on $\hat R(G)$ in terms of $n,e$ and (possibly) other parameters controlled by the hypothesis $e\ge Cn$.

Disproof track. Try to find, for arbitrarily large $C$, graphs $G$ with $e\ge Cn$ but with size Ramsey number $\hat R(G)$ only on the order of $C\,e$ (or smaller). Any universal upper bound of the form $\hat R(G)\le K C e$ for such a family would contradict the desired superlinear $f(C)$.

WORK.
Phase 1: fast reality check (small instance). For $G=K_3$ one can brute-force check that the smallest triangle-Ramsey graph has $6$ vertices and $15$ edges (namely $K_6$), i.e. $\hat R(K_3)=15$. (I verified this by enumerating all graphs on at most $6$ vertices and checking all $2^{|E(H)|}$ two-colorings for a monochromatic triangle.) This sanity-check is consistent with the trivial lower bound $\hat R(G)\ge e(G)$ below.

Lemma 911.1 (trivial edge-count lower bound). For every graph $G$, $\hat R(G)\ge |E(G)|$.

Proof. Let $e=|E(G)|$. If a graph $H$ has $|E(H)|<e$, then $H$ cannot contain a copy of $G$ as a (not-necessarily-induced) subgraph because any copy of $G$ uses $e$ distinct edges. Color the edges of $H$ arbitrarily red/blue; then there is no monochromatic copy of $G$ (indeed no copy at all). Hence no such $H$ is Ramsey for $G$, so the minimum defining $\hat R(G)$ is at least $e$. $\square$

Lemma 911.2 (vertex Ramsey lower bound). Let $R(G)$ denote the usual (two-color) Ramsey number of $G$, i.e. the least integer $N$ such that $K_N\to (G,G)$. If $H\to (G,G)$ then $|V(H)|\ge R(G)$.

Proof. Let $N:=|V(H)|$. Suppose for contradiction that $N<R(G)$. By the definition of $R(G)$, there exists a red/blue coloring of the complete graph $K_N$ with no monochromatic copy of $G$. Restrict this coloring to the edge set $E(H)\subseteq E(K_N)$; since any monochromatic copy of $G$ in $H$ would also be a monochromatic copy of $G$ in $K_N$, the restricted coloring has no monochromatic copy of $G$ in $H$. This contradicts $H\to (G,G)$. $\square$

Lemma 911.3 (first-moment obstruction via random coloring). Fix graphs $G$ and $H$. Let $e:=|E(G)|$ and let $N_G(H)$ be the number of (labeled) subgraphs of $H$ isomorphic to $G$ (equivalently, the number of injections $\varphi:V(G)\hookrightarrow V(H)$ such that $\varphi$ maps edges of $G$ to edges of $H$).

In a uniformly random red/blue coloring of $E(H)$, the expected number of monochromatic copies of $G$ equals $N_G(H)\,2^{1-e}$. In particular, if $N_G(H)<2^{e-1}$ then $H\not\to (G,G)$.

Proof. Color each edge of $H$ independently red/blue with probability $1/2$. Fix a labeled copy $\varphi$ of $G$ in $H$. The event that this copy is monochromatic is the event that all $e$ edges of $\varphi(G)$ are red or all are blue. Each has probability $(1/2)^e$, and the two events are disjoint, so \[\mathbb{P}(\varphi(G)\text{ is monochromatic}) = 2\cdot (1/2)^e = 2^{1-e}. \] Let $X$ be the random variable counting monochromatic labeled copies of $G$ in $H$. Then \[\mathbb{E}X = \sum_{\varphi} \mathbb{P}(\varphi(G)\text{ is monochromatic}) = N_G(H)\,2^{1-e} \] by linearity of expectation. If $N_G(H)<2^{e-1}$ then $\mathbb{E}X<1$, hence there exists at least one coloring with $X=0$, i.e. with no monochromatic copy of $G$; thus $H$ is not Ramsey for $G$. $\square$

VERIFICATION.

• Lemma 911.1 uses only the subgraph containment requirement implicit in $H\to (G,G)$.
• Lemma 911.2 correctly handles the "sparser host" issue by extending a coloring to the complete graph and then restricting.
• Lemma 911.3 uses a labeled copy count; unlabeled versions differ by $|\mathrm{Aut}(G)|$ but the conclusion "$\mathbb{E}X<1$ implies existence of a coloring with $X=0$" is unaffected.

FINAL.
UNRESOLVED.

(i) Strongest proved partial result: general lower bounds $\hat R(G)\ge |E(G)|$ (Lemma 911.1) and $|V(H)|\ge R(G)$ for any Ramsey host $H$ (Lemma 911.2). Also, Lemma 911.3 gives a clean probabilistic criterion: any candidate host $H$ with too few copies of $G$ (specifically $N_G(H)<2^{e-1}$) cannot be Ramsey for $G$.

(ii) First gap (crisp): Prove or disprove the existence of a function $f(C)$ with $f(C)/C\to\infty$ such that every graph $G$ with $e(G)\ge C|V(G)|$ satisfies $\hat R(G) > f(C)\,|E(G)|$ for all sufficiently large $C$.

(iii) Top 3 next moves:

1. Disproof attempt: Construct, for arbitrarily large $C$, explicit graphs $G_C$ with $|E(G_C)|\ge C|V(G_C)|$ and prove an upper bound $\hat R(G_C)\le K\,C\,|E(G_C)|$ with an absolute constant $K$. Any such family would rule out superlinear $f$.
2. Proof attempt: Fix $C$ and attempt to show that every $H$ with $|E(H)|\le g(C)\,e$ has $N_G(H)<2^{e-1}$ for some $g(C)$ growing faster than $C$. Combining with Lemma 911.3 would imply the desired lower bound.
3. Computation: For small $C$ and moderate $n$, brute-force search for graphs $G$ with $e\approx Cn$ and compute/estimate $\hat R(G)$ to guess scaling in $C$ (even partial data could suggest whether $\hat R(G)/e$ can stay $O(C)$).

(iv) Minimal counterexample structure:

• To the existence of such $f$: a family $\{G_C\}$ with average degree $\Theta(C)$ but with $\hat R(G_C)=O(C\,e(G_C))$.
• To the nonexistence: a fixed large $C$ and a graph $G$ with $e\ge Cn$ such that every Ramsey host has $\hat R(G)\ge f(C)e$ for some $f(C)\gg C$.