Erdős Problem #87

Erdős Problem 87: Ramsey numbers versus chromatic number

1. Statement and scope

2. A critical subgraph and a uniform random-coloring estimate

3. An explicit range of the requested comparison

A useful conditional implication is also precise: if $\limsup_kR(K_k)^{1/k}=\sqrt2$, then the first question has an affirmative answer. Indeed, for any fixed $\epsilon>0$ choose $\eta>0$ so that $\sqrt2/(\sqrt2+\eta)>1-\epsilon$. Eventually $R(K_k)\le(\sqrt2+\eta)^k$, while $2$ is a fixed positive factor times $(\sqrt2)^k$. Their ratio exceeds $(1-\epsilon)^k$ for all sufficiently large $k$. The hypothesis on diagonal Ramsey numbers is not assumed known.

4. Scope of the missing argument

5. Assessment and attribution

Completion rate estimate: 25%.

OUTPUT 1) FORMAL RESTATEMENT For a graph $H$, let $R(H)$ denote the diagonal Ramsey number $r(H,H)$. For $k\ge 2$, let $R(k)=R(K_k)$. The questions are: $Q1$ For every $\epsilon>0$, does there exist $k_0$ such that for all $k\ge k_0$ and all graphs $G$ with $\chi(G)=k$, we have $R(G)>(1-\epsilon)^k R(k)$? $Q2$ Does there exist $c>0$ and $k_0$ such that for all $k\ge k_0$ and all $k$-chromatic $G$, $R(G)>cR(k)$?

2) QUICK LITERATURE/CONTEXT CHECK Browsing is not available. I only record what the problem statement itself claims, without proof.

3) ATTACK PLAN Proof strategies: 1. Prove a universal lower bound on $R(G)$ in terms of $\chi(G)$ via random colouring. 2. Compare this bound to the best available lower bounds on $R(k)$ (not proved here).

Disproof strategies: 1. Construct $k$-chromatic graphs with Ramsey numbers far smaller than $R(k)$.

Chosen path: provide a complete proof of the Wigderson-type bound $R(G)\ge 2^{(k-3)/2}$ and isolate the gap to the conjectured ratio $R(G)/R(k)$.

4) WORK Lemma 1 (Subgraph monotonicity). If $H$ is a subgraph of $G$, then $R(H)\le R(G)$.

Proof. Every two-colouring of $K_{R(G)}$ contains a monochromatic copy of $G$, hence also of $H$. ∎

Lemma 2 (Existence of a $k$-critical subgraph). If $\chi(G)=k$, then $G$ contains an induced subgraph $H$ with $\chi(H)=k$ and $\chi(H-v)\le k-1$ for every vertex $v$.

Proof. Iteratively delete vertices that do not reduce chromatic number. The process terminates with a minimal induced subgraph of chromatic number $k$. ∎

Lemma 3 (Minimum degree in a $k$-critical graph). If $H$ is $k$-vertex-critical, then $\delta(H)\ge k-1$.

Proof. If a vertex $v$ has degree at most $k-2$, then a $(k-1)$-colouring of $H-v$ can be extended to $v$, contradicting $\chi(H)=k$. ∎

Theorem 4 (Wigderson-type lower bound). If $\chi(G)=k\ge 2$, then \[R(G)\ge 2^{(k-3)/2}.\]

Proof. Let $H$ be a $k$-critical induced subgraph of $G$ (Lemma 2). Let $v=|V(H)|$ and $e=|E(H)|$. By Lemma 3, $2e\ge v(k-1)$, so $e\ge v(k-1)/2$. Let $N=\lfloor 2^{(k-1)/2-1}\rfloor$. Consider a random red/blue colouring of $K_N$. For a fixed injective map $\varphi:V(H)\hookrightarrow [N]$, the probability that all $e$ edges of $\varphi(H)$ are monochromatic is $2\cdot 2^{-e}=2^{1-e}$. The number of injective maps is at most $N^v$. Hence \[\mathbb{E}[X]\le N^v 2^{1-e}\le 2\left(\frac{N}{2^{(k-1)/2}}\right)^v\le 2\left(\frac12\right)^v<1. \] Therefore there exists a colouring with no monochromatic copy of $H$, so $R(H)>N$ and hence $R(G)\ge R(H)>N\ge 2^{(k-3)/2}$. ∎

5) VERIFICATION Edge cases: - $k=2$: $R(G)\ge 2$ is trivial. - $k=3$: the bound gives $R(G)\ge 1$, still consistent.

Quantifier checks: The theorem is unconditional and applies to every $k$-chromatic graph. It does not imply the ratio bounds in $Q1$--$Q2$ without additional information about $R(k)$.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: For any $k$-chromatic graph $G$, $R(G)\ge 2^{(k-3)/2}$ (Theorem 4).

(ii) First gap: Relating $R(G)$ to $R(k)$ multiplicatively requires sharper lower bounds on $R(k)$ or sharper upper bounds on $R(G)$ for special $G$; neither is achieved here.

(iii) Top 3 next moves: 1. Improve the universal lower bound on $R(G)$ beyond $2^{k/2}$. 2. Establish better explicit lower bounds for $R(k)$ to compare with Theorem 4. 3. Identify families of $k$-chromatic graphs with particularly small Ramsey numbers.

(iv) Minimal counterexample structure (if $Q1$ is false): An infinite sequence of $k$-chromatic graphs $G_k$ with $R(G_k)$ asymptotically much smaller than $R(k)$, showing the ratio $R(G_k)/R(k)$ tends to $0$.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - For a graph $H$, let $R(H)$ be its (2-color) Ramsey number: the least $n$ such that every red/blue coloring of $E(K_n)$ contains a monochromatic copy of $H$. - Let $R(k):=R(K_k)$. - Fix $k\ge 3$ and consider graphs $G$ with $\chi(G)=k$.

Questions. 1. For each $\varepsilon>0$, for all large $k$ does every $k$-chromatic graph $G$ satisfy \[R(G)>(1-\varepsilon)^k R(k)?\] 2. Is there an absolute constant $c>0$ such that for all large $k$ and all $k$-chromatic $G$, \[R(G)>c\,R(k)?\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the statement: - The naive conjecture $R(G)\ge R(k)$ is false at $k=4$ (wheel example). - Wigderson's observation gives $R(G)\gg 2^{k/2}$ for any $k$-chromatic $G$. I re-prove the $2^{k/2}$-type lower bound below (with explicit constants).

3) ATTACK PLAN Proof track ideas: 1. Prove a universal exponential lower bound on $R(G)$ in terms of $\chi(G)$ by extracting a dense critical subgraph and using the probabilistic method. 2. Compare that universal bound to known bounds for $R(k)$ to approach the ratios in the question.

Disproof track ideas: 1. Attempt to construct families of $k$-chromatic graphs $G_k$ with unusually small Ramsey numbers compared to $R(k)$.

Chosen path in this attempt: prove Wigderson's universal lower bound $R(G)\ge 2^{\Theta(k)}$ using two problem-specific lemmas.

4) WORK Lemma 1 (Critical subgraph has large minimum degree). If $\chi(G)=k$, then $G$ contains a subgraph $H\subseteq G$ with $\chi(H)=k$ and minimum degree \[\delta(H)\ge k-1.\]

Proof. Choose $H\subseteq G$ with $\chi(H)=k$ and with $|V(H)|$ minimal among such subgraphs (a $k$-critical subgraph). Then for every vertex $v\in V(H)$, the graph $H-v$ has chromatic number at most $k-1$ by minimality. If $d_H(v)\le k-2$ for some $v$, then take a proper $(k-1)$-coloring of $H-v$. Among the neighbors of $v$ there are at most $k-2$ vertices, so they use at most $k-2$ colors. Therefore there is at least one color unused by the neighbors of $v$; assign that color to $v$ to obtain a proper $(k-1)$-coloring of $H$. This contradicts $\chi(H)=k$. Hence $d_H(v)\ge k-1$ for all $v$, i.e. $\delta(H)\ge k-1$. $\square$

Lemma 2 (Probabilistic lower bound: $R(G)\ge 2^{(k-1)/2}$ for $k$-chromatic $G$). Let $G$ be a graph with $\chi(G)=k\ge 3$. Then \[R(G) > 2^{(k-1)/2-1}\] for all sufficiently large $k$ (and in particular $R(G)\gg 2^{k/2}$).

Proof. Let $H\subseteq G$ be the $k$-chromatic subgraph from Lemma 1, so $\delta(H)\ge k-1$. Let $v:=|V(H)|$ and $e:=|E(H)|$. Since $H$ has minimum degree at least $k-1$, \[2e=\sum_{x\in V(H)} d_H(x)\ge v(k-1),\] so \[e\ge \frac{(k-1)v}{2}.\tag{1}\]

Now take $N$ vertices and color each edge of $K_N$ red/blue independently with probability $1/2$ each. Fix an injective map $\varphi:V(H)\hookrightarrow [N]$ (an embedding of vertices). The probability that all edges of $\varphi(H)$ are red is $2^{-e}$, and similarly for all blue, so the probability that $\varphi(H)$ is monochromatic is $2\cdot 2^{-e}=2^{1-e}$.

There are at most $N^v$ injective maps (crude bound). Let $X$ be the number of monochromatic labeled copies of $H$. By linearity of expectation, \[\mathbb E[X]\le N^v \cdot 2^{1-e}.\] Choose $N:=\left\lfloor 2^{(k-1)/2-1}\right\rfloor$. Then $N^v \le 2^{v((k-1)/2-1)}$. Using $1$, we obtain \[\mathbb E[X]\le 2^{v((k-1)/2-1)}\cdot 2^{1-e}\le 2^{v((k-1)/2-1)}\cdot 2^{1-(k-1)v/2}=2^{1-v}.\] Since $v\ge k\ge 3$, we have $2^{1-v}<1$. Therefore there exists a coloring with $X=0$, i.e. with no monochromatic copy of $H$, hence no monochromatic copy of $G$. So $R(G)>N\ge 2^{(k-1)/2-1}-1$, proving the claim. $\square$

FAST REALITY CHECK Lemma 2 gives $R(G)\ge 2^{\Theta(k)}$ uniformly over all $k$-chromatic graphs $G$. This matches the scale of the classic probabilistic lower bound for $R(k)$ (also $2^{\Theta(k)}$).

5) VERIFICATION - Lemma 1 is standard and the coloring-extension argument is explicit. - Lemma 2 uses only union bound and the edge lower bound $e\ge (k-1)v/2$ from minimum degree. - The crude bound "number of embeddings $\le N^v$" is valid and suffices.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: For every $k$-chromatic graph $G$, one has the uniform exponential lower bound \[R(G)\gg 2^{k/2}\] (Lemma 2, via the $k$-critical subgraph Lemma 1).

(ii) First gap: Compare $R(G)$ to $R(k)$ multiplicatively for all $k$-chromatic $G$: prove (or refute) that $R(G)$ is always within a factor $c^k$ or even a fixed factor of $R(k)$ as $k\to\infty$.

(iii) Top 3 next moves (concrete): 1. Identify extremal families of $k$-chromatic graphs (e.g. sparse $k$-chromatic graphs) and try to upper bound their Ramsey numbers to see how small $R(G)$ can get relative to $R(k)$. 2. Try to prove a lower bound $R(G)\ge R(k)^{1-o(1)}$ or $R(G)\ge cR(k)$ using structural properties forced by $\chi(G)=k$ beyond just minimum degree. 3. Compute/collect small-$k$ examples where $R(G)<R(k)$ (like the wheel) and study whether the deficit can grow exponentially in $k$.

(iv) What a minimal counterexample would likely look like (structure/parameters): A sequence of graphs $G_k$ with $\chi(G_k)=k$ such that $R(G_k)$ is exponentially smaller than $R(k)$, e.g. $R(G_k)\le (1-\varepsilon)^k R(k)$ for some fixed $\varepsilon>0$, which would falsify the first question.