Erdős Problem #638

Erdős Problem 638 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/638

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/638.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/638.tex.

Problem 638

1) FORMAL RESTATEMENT

Let $\mathcal S$ be a family of finite (simple, undirected) graphs. Assume that for every integer $n\ge 1$ there exists a graph $G_n\in\mathcal S$ such that \[ G_n \to (K_3)^{e}_n, \] meaning: for every edge-colouring $c:E(G_n)\to\{1,\dots,n\}$ there is a monochromatic triangle.

Question (as written). Must it then be true that for every infinite cardinal $\kappa$ there exists a graph $G$ such that

1. every finite subgraph of $G$ belongs to $\mathcal S$, and
2. $G\to (K_3)^{e}_\kappa$ (every $\kappa$-edge-colouring of $G$ contains a monochromatic triangle)?

2) QUICK LITERATURE/CONTEXT CHECK

The formulation is ambiguous/degenerate unless one assumes additional closure properties of $\mathcal S$ (e.g. being hereditary under taking finite subgraphs). Under the literal reading (no closure assumptions), there are immediate counterexamples (below). A natural "minimal correction" is to add that $\mathcal S$ is closed under taking finite subgraphs (and perhaps has a joint-embedding property so that some infinite $G$ with age contained in $\mathcal S$ even exists); under such strengthened hypotheses the question becomes nontrivial.

3) ATTACK PLAN

Give a concrete family $\mathcal S$ satisfying the hypothesis (Ramsey-for-$K_3$ graphs exist for every $n$), but such that no graph $G$ can have all its finite subgraphs in $\mathcal S$. This disproves the conclusion already at clause (a), hence answers the literal question in the negative.

4) WORK

Step 1: Fix Ramsey witnesses.

For each $n\ge 1$, let $R_3(n)$ denote the (finite) Ramsey number for monochromatic triangles under $n$ edge-colours; i.e. $R_3(n)$ is the least integer $N$ such that \[K_N \to (K_3)^e_n.\] Existence of such $R_3(n)$ follows from the classical finite Ramsey theorem.

Step 2: Define the family $\mathcal S$.

Set \[ \mathcal S := \{\,K_{R_3(n)} : n\in\mathbb N,\ n\ge 1\,\}. \] Then for each $n$ we may take $G_n := K_{R_3(n)}\in\mathcal S$, and by definition $G_n\to (K_3)^e_n$. So the hypothesis of the problem holds.

Step 3: Show the conclusion fails.

Suppose (for contradiction) that there exists some graph $G$ such that every finite subgraph of $G$ belongs to $\mathcal S$. Pick any vertex $v\in V(G)$. The one-vertex graph $K_1$ is a finite subgraph of $G$ (take vertex set $\{v\}$ and no edges), hence $K_1\in\mathcal S$. But by construction $\mathcal S$ consists only of complete graphs $K_{R_3(n)}$ with $R_3(n)\ge 3$, so $K_1\notin\mathcal S$. This contradiction shows that no such $G$ exists.

Therefore the asserted implication is false already at the level of (a), so the answer to the question as written is no.

5) VERIFICATION / SANITY CHECKS

• For each $n$, $G_n:=K_{R_3(n)}\in\mathcal S$ satisfies $G_n\to (K_3)^e_n$ by the definition of $R_3(n)$.
• Any graph $G$ has a finite subgraph on one vertex (and also on two vertices, etc.). Since $K_1\notin\mathcal S$, no graph can have all finite subgraphs in $\mathcal S$.
• Hence the conclusion "for every infinite $\kappa$ there exists $G$ with (a) and (b)" fails.

6) FINAL

LABEL: FULL SOLUTION
SUBLABEL: COUNTEREXAMPLE/DISPROOF
Taking $\mathcal S=\{K_{R_3(n)}:n\ge 1\}$ satisfies the hypothesis, but there is no graph $G$ all of whose finite subgraphs lie in $\mathcal S$ (since $K_1\notin\mathcal S$). Thus the implication is false as stated.

7) COMPLETION ESTIMATE

COMPLETION: 100%

---

COMPLETION ESTIMATE

Inherited primary-source estimate: $100\%$. This is the original source's unverified estimate, not a new assessment or confirmation that the problem is solved.

Problem 638

1) FORMAL RESTATEMENT

Let $\mathcal S$ be a family of finite (simple, undirected) graphs. Assume that for every integer $n\ge 1$ there exists a graph $G_n\in\mathcal S$ such that \[ G_n \to (K_3)^{e}_n, \] meaning: for every edge-colouring $c:E(G_n)\to\{1,\dots,n\}$ there is a monochromatic triangle.

Question (as written). Must it then be true that for every infinite cardinal $\kappa$ there exists a graph $G$ such that

1. every finite subgraph of $G$ belongs to $\mathcal S$, and
2. $G\to (K_3)^{e}_\kappa$ (every $\kappa$-edge-colouring of $G$ contains a monochromatic triangle)?

2) QUICK LITERATURE/CONTEXT CHECK

The formulation is ambiguous/degenerate unless one assumes additional closure properties of $\mathcal S$ (e.g. being hereditary under taking finite subgraphs). Under the literal reading (no closure assumptions), there are immediate counterexamples (below). A natural "minimal correction" is to add that $\mathcal S$ is closed under taking finite subgraphs (and perhaps has a joint-embedding property so that some infinite $G$ with age contained in $\mathcal S$ even exists); under such strengthened hypotheses the question becomes nontrivial.

3) ATTACK PLAN

Give a concrete family $\mathcal S$ satisfying the hypothesis (Ramsey-for-$K_3$ graphs exist for every $n$), but such that no graph $G$ can have all its finite subgraphs in $\mathcal S$. This disproves the conclusion already at clause (a), hence answers the literal question in the negative.

4) WORK

Step 1: Fix Ramsey witnesses.

For each $n\ge 1$, let $R_3(n)$ denote the (finite) Ramsey number for monochromatic triangles under $n$ edge-colours; i.e. $R_3(n)$ is the least integer $N$ such that \[K_N \to (K_3)^e_n.\] Existence of such $R_3(n)$ follows from the classical finite Ramsey theorem.

Step 2: Define the family $\mathcal S$.

Set \[ \mathcal S := \{\,K_{R_3(n)} : n\in\mathbb N,\ n\ge 1\,\}. \] Then for each $n$ we may take $G_n := K_{R_3(n)}\in\mathcal S$, and by definition $G_n\to (K_3)^e_n$. So the hypothesis of the problem holds.

Step 3: Show the conclusion fails.

Suppose (for contradiction) that there exists some graph $G$ such that every finite subgraph of $G$ belongs to $\mathcal S$. Pick any vertex $v\in V(G)$. The one-vertex graph $K_1$ is a finite subgraph of $G$ (take vertex set $\{v\}$ and no edges), hence $K_1\in\mathcal S$. But by construction $\mathcal S$ consists only of complete graphs $K_{R_3(n)}$ with $R_3(n)\ge 3$, so $K_1\notin\mathcal S$. This contradiction shows that no such $G$ exists.

Therefore the asserted implication is false already at the level of (a), so the answer to the question as written is no.

5) VERIFICATION / SANITY CHECKS

• For each $n$, $G_n:=K_{R_3(n)}\in\mathcal S$ satisfies $G_n\to (K_3)^e_n$ by the definition of $R_3(n)$.
• Any graph $G$ has a finite subgraph on one vertex (and also on two vertices, etc.). Since $K_1\notin\mathcal S$, no graph can have all finite subgraphs in $\mathcal S$.
• Hence the conclusion "for every infinite $\kappa$ there exists $G$ with (a) and (b)" fails.

6) FINAL

LABEL: FULL SOLUTION
SUBLABEL: COUNTEREXAMPLE/DISPROOF
Taking $\mathcal S=\{K_{R_3(n)}:n\ge 1\}$ satisfies the hypothesis, but there is no graph $G$ all of whose finite subgraphs lie in $\mathcal S$ (since $K_1\notin\mathcal S$). Thus the implication is false as stated.

7) COMPLETION ESTIMATE

COMPLETION: 100%

---