Reused writeup on Math-5741 (gpt pro 5.2)

Erdős Problem 566 --- collection record

PROVENANCE AND STATUS

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

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

REUSED SOURCE 1

Original attribution: codex_5.2_extra_high. Original file: attacks/erdos/codex_5.2_extra_high/566.tex.

FORMAL RESTATEMENT

Let $G$ be a fixed (simple) graph such that every subgraph $G'\subseteq G$ on $k$ vertices has at most $2k-3$ edges. (Equivalently, every induced subgraph on $k$ vertices has at most $2k-3$ edges, since deleting edges only decreases the edge count.) The question asks whether $G$ is Ramsey size linear: does there exist a constant $C_G>0$ such that for every graph $H$ with $m$ edges and no isolated vertices, \[ R(G,H) \le C_G m ? \] Here $R(G,H)$ is the usual graph Ramsey number: the least $N$ such that every red/blue colouring of $E(K_N)$ contains a red copy of $G$ or a blue copy of $H$.

QUICK LITERATURE/CONTEXT CHECK

The file states: (i) the statement fails if $G$ has $n$ vertices and $2n-2$ edges (e.g. with $H=K_n$); (ii) Erdős--Faudree--Rousseau--Schelp $1993$ proved that any graph with $n$ vertices and at most $n+1$ edges is Ramsey size linear. No other results are used here.

ATTACK PLAN

Proof track: Try to exploit the sparsity condition (edge bound $2k-3$ for all $k$) to derive structural constraints (degeneracy/arboricity/treewidth) and then attempt to embed $G$ into a large monochromatic subgraph with bounded average degree.

Disproof track: Try to construct a sparse $G$ (satisfying the condition) for which $R(G,K_t)$ grows superlinearly in $|E(K_t)|\asymp t^2$, or choose a family of $H$ with $m$ edges and see if $R(G,H)$ must grow faster than $m$. No such construction is obtained below.

WORK

Lemma 566.1 (degeneracy consequence of the $2k-3$ condition). If every $k$-vertex subgraph of $G$ has at most $2k-3$ edges, then $G$ is $3$-degenerate: every nonempty subgraph of $G$ has a vertex of degree at most $3$.

Proof. Let $G'$ be a nonempty subgraph of $G$ on $k\ge 1$ vertices and $e$ edges. If $k=1$ then the unique vertex has degree $0$. If $k\ge 2$, the hypothesis gives $e\le 2k-3$, so the average degree of $G'$ is $\bar d = 2e/k \le 2(2k-3)/k = 4 - 6/k < 4$. In a finite graph, if all vertices had degree at least $4$ then the average degree would be at least $4$. Thus $G'$ contains a vertex of degree at most $3$. Since $G'$ was an arbitrary nonempty subgraph, $G$ is $3$-degenerate. $\square$

Lemma 566.2 (no isolated vertices implies $v(H)\le 2m$). If $H$ has $m$ edges and no isolated vertices, then the number of vertices $v(H)$ satisfies $v(H)\le 2m$.

Proof. Let the vertex degrees be $d_1,\dots,d_{v(H)}$. Since $H$ has no isolated vertices, each $d_i\ge 1$. By the handshaking lemma, $\sum_i d_i = 2m$. Thus $v(H)\le\sum_i d_i = 2m$. $\square$

Lemma 566.3 (general polynomial bound in terms of $m$ for fixed $G$). Let $G$ be any fixed graph on $s$ vertices and let $H$ be any graph with $m$ edges and no isolated vertices. Then \[ R(G,H) \le O_s(m^{s-1}). \] More explicitly, \[ R(G,H) \le R(K_s, K_{v(H)}) \le \binom{s+v(H)-2}{s-1} \le \binom{s+2m-2}{s-1}. \]

Proof. Monotonicity of Ramsey numbers gives $R(G,H)\le R(K_s,K_{v(H)})$ because any blue $K_{v(H)}$ contains $H$ as a subgraph on the same vertex set. It remains to upper bound $R(K_s,K_t)$ for $t=v(H)$. Let $R(s,t):=R(K_s,K_t)$. Pick a vertex $v$ in a red/blue colouring of $K_N$. Let $A$ be the set of red neighbours of $v$ and $B$ the blue neighbours. If $|A|\ge R(s-1,t)$ then the induced colouring on $A$ contains either a red $K_{s-1}$ (which together with $v$ forms a red $K_s$) or a blue $K_t$. If $|A|<R(s-1,t)$ then $|B|\ge N-1-(R(s-1,t)-1)$; if in addition $N\ge R(s-1,t)+R(s,t-1)$ then $|B|\ge R(s,t-1)$ and similarly we get a red $K_s$ or blue $K_t$. Thus the recursion \[ R(s,t) \le R(s-1,t)+R(s,t-1) \] holds for all $s,t\ge 2$, with $R(1,t)=R(s,1)=1$. A standard induction on $s+t$ yields the closed-form upper bound \[ R(s,t) \le \binom{s+t-2}{s-1}. \] Finally apply Lemma 566.2 to bound $t=v(H)\le 2m$, and use $\binom{s+2m-2}{s-1}=O_s(m^{s-1})$. $\square$

Lemma 566.4 (linear bound when $G$ is a tree). Let $T$ be a tree on $t\ge 1$ vertices and let $H$ be a graph with $m$ edges and no isolated vertices. Then \[ R(T,H) \le (t-1)(2m-1)+1. \]

Proof. Let $q=v(H)\le 2m$ by Lemma 566.2. Since a blue $K_q$ contains $H$, we have $R(T,H)\le R(T,K_q)$. We prove by induction on $t+q$ the bound \[ R(T,K_q) \le (t-1)(q-1)+1. \tag{$**$} \] This is enough because $(t-1)(q-1)+1\le (t-1)(2m-1)+1$.

Base cases: if $t=1$ then $T$ is a single vertex and $R(T,K_q)=1$, matching ($**$). If $q=1$ then $K_1$ is a single vertex and $R(T,K_1)=1$, also matching ($**$).

Inductive step: assume $t,q\ge 2$. Let $u$ be a leaf of $T$ and let $T':=T\setminus\{u\}$ (a tree on $t-1$ vertices). We claim the recursion \[ R(T,K_q) \le R(T',K_q)+R(T,K_{q-1}). \tag{$***$} \] To prove ($***$), let $N = R(T',K_q)+R(T,K_{q-1})$ and consider any red/blue colouring of $K_N$. Pick a vertex $v$. Let $A$ be the set of red neighbours of $v$ and $B$ the set of blue neighbours. If $|A|\ge R(T',K_q)$, then in the induced colouring on $A$ there is either a blue $K_q$ (done) or a red copy of $T'$. In the latter case, since $v$ is red-adjacent to every vertex of $A$, we can map the deleted leaf $u$ to $v$ and keep the copy of $T'$ on $A$, obtaining a red copy of $T$. If $|A|<R(T',K_q)$ then $|B|\ge N-1-(R(T',K_q)-1)=R(T,K_{q-1})$. Applying the definition of $R(T,K_{q-1})$ to the induced colouring on $B$ yields either a red $T$ (done) or a blue $K_{q-1}$, which together with $v$ forms a blue $K_q$. This proves ($***$).

Now apply the induction hypothesis to $R(T',K_q)$ and $R(T,K_{q-1})$: \[ R(T',K_q) \le (t-2)(q-1)+1, \qquad R(T,K_{q-1}) \le (t-1)(q-2)+1. \] Summing and using ($***$) gives \[ R(T,K_q) \le [(t-2)(q-1)+1] + [(t-1)(q-2)+1] = (t-1)(q-1)+1, \] which is exactly ($**$) and completes the induction. Therefore $R(T,H)\le (t-1)(2m-1)+1$. $\square$

VERIFICATION

$1$ Lemma 566.1 correctly uses the hypothesis for all subgraphs, not just induced. Since maximum average degree $<4$ in every subgraph, degeneracy $\le 3$ follows.

$2$ Lemma 566.4 is checked carefully: the recursion ($***$) uses the fact that a red copy of $T'$ in $A$ can be extended by mapping the missing leaf to $v$. This is valid because the leaf has exactly one neighbour in $T$ and $v$ is red-adjacent to the entire copy of $T'$; in particular it is red-adjacent to the image of the neighbour of $u$.

$3$ Fast reality check: if $H$ has $m$ edges and no isolates then indeed $v(H)\le 2m$ is tight for a matching. For a tree $T$ on $t$ vertices, the bound $R(T,H)\le (t-1)(2m-1)+1$ is linear in $m$ as claimed.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: - The sparsity hypothesis forces $G$ to be $3$-degenerate (Lemma 566.1). - For any fixed $G$ on $s$ vertices and any $H$ with $m$ edges and no isolates, one always has the polynomial bound $R(G,H)=O_s(m^{s-1})$ (Lemma 566.3). - If $G$ is a tree then $G$ is Ramsey size linear (Lemma 566.4), with the explicit bound $R(G,H)\le (t-1)(2m-1)+1$.

(ii) First gap (crisp): prove (or disprove) that every $3$-degenerate graph $G$ satisfying the stronger hereditary edge bound $e(G')\le 2v(G')-3$ has \[ R(G,H) = O_G(|E(H)|) \] for all $H$ with no isolated vertices.

(iii) Top 3 next moves: $1$ Identify a structural characterization of graphs with $e(G')\le 2v(G')-3$ for all subgraphs $G'$ (e.g. bounded treewidth/series-parallel) and try to prove linear Ramsey size for that entire class. $2$ Try to extend the tree argument (Lemma 566.4) to graphs obtained by adding one extra edge to a tree (unicyclic) and then to the full class. $3$ Attempt to construct counterexamples by choosing candidate $G$ in this class and testing $R(G,K_t)$ experimentally for moderate $t$ against linear-in-$m=\binom{t}{2}$ growth.

(iv) Minimal counterexample structure: a counterexample would be a fixed graph $G$ with the hereditary bound $e(G')\le 2v(G')-3$ and a family $H_m$ with $m$ edges/no isolates such that $R(G,H_m)/m\to\infty$. Since $v(H_m)\le 2m$, any such family must force growth beyond the trivial $O(m^{v(G)-1})$ bound, likely via $H_m$ being relatively dense (e.g. cliques) while $G$ encodes a difficult sparse obstruction.

REUSED SOURCE 2

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

1) FORMAL RESTATEMENT

Conventions

* All graphs are finite, simple, undirected (no loops or multiple edges). * For a graph (X), write $v(X)=|V(X)|$ and $e(X)=|E(X)|$. * A “subgraph on (k) vertices” means: choose a subset $S\subseteq V(G)$ with $|S|=k$, and take any subgraph whose vertex set is (S) (equivalently: any graph $J\subseteq G[S]$). Then $v(J)=k$ and $e(J)\le e(G[S])$.

Ramsey number

For graphs (G,H), the (two–color) Ramsey number (R(G,H)) is the least integer (N) such that every red/blue coloring of the edges of $K_N$ contains either:

* a red (not necessarily induced) copy of (G), or * a blue (not necessarily induced) copy of (H).

Equivalently: for every graph (X) on (N) vertices, either (X) contains (G) as a (not necessarily induced) subgraph, or $\overline{X}$ contains (H) as a subgraph.

The sparsity hypothesis on (G)

The literal condition “every subgraph on (k) vertices has at most $2k-3$ edges” is nonsensical for $k=1$ because it would demand $0\le -1$. Standard convention in this area is that such inequalities are intended for $k\ge 2$.

So the minimal corrected statement is:

$\forall k\in\mathbb{Z}$ with $2\le k\le v(G)$, every subgraph $J\subseteq G$ with $v(J)=k$ satisfies \[ e(J)\le 2k-3. \]

“Ramsey size-linear”

“$R(G,H)\ll m$” means: there exists a constant $C_G>0$ (depending only on (G)) such that for every graph (H) with

* $e(H)=m$, and * no isolated vertices (i.e. every vertex has degree $\ge 1$, hence $v(H)\le 2m$ and $m\ge 1$),

we have \[ R(G,H)\le C_G,m. \]

Problem

Assuming the corrected sparsity hypothesis on (G) (for all $k\ge 2$), decide whether:

(Claim) Every such graph (G) is Ramsey size-linear, i.e. \[ \exists C_G>0\ \forall H\text{ with no isolates}:\ R(G,H)\le C_G,e(H). \]

---

2) QUICK LITERATURE/CONTEXT CHECK

Web check shows that this question is explicitly recorded as open in recent work.

* Bradač–Gishboliner–Sudakov (SIAM DM 2024; author PDF) state that Erdős et al. asked whether every graph (H) with $m_2(H)\le 2$ is Ramsey size-linear, and that this “seem[s] to be still out of reach.” ([ETH Zurich Math People][1]) They also highlight the specific unresolved case $K_4^*$ (subdivide one edge of $K_4$ once) and say they cannot answer it, though they prove a partial result for bipartite (F): $R(K_4^*,F)=O(e(F))$. ([ETH Zurich Math People][1]) They prove that every subdivision of $K_4$ on at least 6 vertices is Ramsey size-linear. ([ETH Zurich Math People][1])

* Wigderson (arXiv v2, May 2025) repeats the definition of Ramsey size-linear and notes $K_4$ is not Ramsey size-linear. He also cites the known sufficient condition that if $e(G)>2v(G)-2$ then (G) is not Ramsey size-linear.

So: as of 2024–2025 literature, the general claim you ask for is not resolved, and even the specific graph $K_4^*$ remains a key open instance. ([ETH Zurich Math People][1])

---

3) ATTACK PLAN

Proof-track ideas

1. Exploit the “2-density” condition. The inequality $e(J)\le 2v(J)-3$ is equivalent to $m_2(G)\le 2$ (definition below). One might try to prove a general embedding/DRC lemma: in any (G)-free red graph on $N=O(m)$ vertices, the blue graph must contain any (H) with (m) edges.

2. Reduce to biconnected/components. There are known decompositions for Ramsey numbers along biconnected components (Bradač–Gishboliner–Sudakov record such a corollary). One might hope to reduce to a finite list of “2-connected obstructions,” ideally down to the $K_4^*$-type cases.

3. Handle extremal obstructions (Ramsey–Turán viewpoint). For $H=K_n$, $R(G,K_n)$ is controlled by the largest (G)-free graphs with small independence number. For size-linearity it would suffice to show $R(G,K_n)=O(n^2)$ for all $m_2(G)\le 2$ and then extend from cliques to all (H) by a general “$H\subseteq K_{2m}$” bootstrapping plus structural arguments.

Disproof-track ideas

1. Attack $K_4^*$. If one can show $R(K_4^*,K_n)=\omega(n^2)$, then taking $H=K_n$ (with $e(H)=\Theta(n^2)$) would immediately refute size-linearity for a (G) satisfying your local $2k-3$ bound.

2. Construct (H) sparse but Ramsey-hard against a candidate (G). Find a family $H_m$ with $e(H_m)=m$ but such that one can 2-color $K_{c m}$ avoiding both a red (G) and a blue $H_m$ for every fixed (c). This would require designing “$H_m$-free” blue graphs of density close to 1 while keeping red (G)-free.

Best path to try first: check whether the problem is already solved (it isn’t, per sources), and then see whether we can either (i) prove size-linearity for the key open case $K_4^*$ or (ii) build a counterexample already for $K_4^*$. If neither succeeds, we will have to stop at UNRESOLVED.

---

4) WORK

4.1 Clarifying the sparsity condition: equivalence to $m_2(G)\le 2$

Define the 2-density of a graph (F) by \[ m_2(F):=\max\left\{\frac{e(J)-1}{v(J)-2}:\ J\subseteq F,\ v(J)\ge 3\right\}, \] as in Bradač–Gishboliner–Sudakov.

Lemma 4.1. For a graph (G), the following are equivalent:

1. For every subgraph $J\subseteq G$ with $v(J)=k\ge 2$, $e(J)\le 2k-3$. 2. $m_2(G)\le 2$.

Proof. $1$$\Rightarrow$$2$: Let $J\subseteq G$ with $v(J)\ge 3$. Then $e(J)\le 2v(J)-3$, so \[ \frac{e(J)-1}{v(J)-2}\le \frac{(2v(J)-3)-1}{v(J)-2}=\frac{2v(J)-4}{v(J)-2}=2. \] Taking the maximum over all such (J) gives $m_2(G)\le 2$.

$2$$\Rightarrow$$1$: Let $J\subseteq G$ with $v(J)=k\ge 3$. Then \[ \frac{e(J)-1}{k-2}\le m_2(G)\le 2 \quad\Rightarrow\quad e(J)-1\le 2(k-2) \quad\Rightarrow\quad e(J)\le 2k-3. \] For $k=2$, any simple graph has at most one edge, and $1=2\cdot 2-3$, so the inequality holds as well. ∎

So your hypothesis on (G) is exactly $m_2(G)\le 2$.

This aligns with the statement in Bradač–Gishboliner–Sudakov that Erdős et al. asked whether every graph (H) with $m_2(H)\le 2$ is Ramsey size-linear. ([ETH Zurich Math People][1])

---

4.2 A fully proved partial result: forests are Ramsey size-linear

This is a standard and fully provable special case.

Lemma 4.2. If (G) is a forest, then (G) is Ramsey size-linear: there exists $C_G$ such that for every (H) with no isolated vertices, \[ R(G,H)\le C_G,e(H). \]

Proof. Let (G) be a forest. Then (G) is a subgraph of some tree (T) on $t:=v(G)$ vertices (take any spanning tree of each component and connect components by adding edges; the resulting tree has at most (t) vertices; if it uses fewer, add isolated vertices and then connect—details omitted because we can simply take a tree (T) on exactly (t) vertices that contains (G) as a subgraph; such a tree always exists by taking a tree spanning (t) labeled vertices and embedding (G) by mapping components into disjoint subtrees).

Monotonicity of Ramsey numbers in the first argument: if $G\subseteq T$, then \[ R(G,H)\le R(T,H) \] because any red copy of (T) contains a red copy of (G).

Now let (H) be a graph with no isolated vertices and $m:=e(H)$. Then $v(H)\le 2m$. Hence (H) is a subgraph of the complete graph $K_{2m}$. Monotonicity in the second argument gives \[ R(T,H)\le R(T,K_{2m}). \]

Chvátal’s theorem $1977$ states that for every tree (T) on (t) vertices and every $n\ge 1$, \[ R(T,K_n) = (t-1)(n-1)+1. \] (See also the statement quoted in Wigderson’s note. )

Applying this with $n=2m$, we get \[ R(T,K_{2m})=(t-1)(2m-1)+1 \le (t-1)(2m)+1 = 2(t-1)m+1. \]

Putting everything together: \[ R(G,H)\le R(T,H)\le R(T,K_{2m})\le 2(t-1)m+1. \] Thus $C_G:=2(t-1)+1$ works (or simply $C_G:=2(t-1)+2$ to absorb the “$+1$” uniformly for $m\ge 1$). ∎

This matches the folklore lemma quoted by Wigderson.

---

4.3 What remains: the main claim is not resolved by known results, and the obstruction $K_4^*$

From the literature check, the central open question is exactly:

Are all graphs (G) with $m_2(G)\le 2$ Ramsey size-linear?

Bradač–Gishboliner–Sudakov explicitly state this remains out of reach and single out $K_4^*$ as an unresolved test case. ([ETH Zurich Math People][1])

Moreover, they prove:

* $R(K_4^*,F)=O(e(F))$ for every bipartite (F) with no isolates, ([ETH Zurich Math People][1]) * every subdivision of $K_4$ on at least 6 vertices is Ramsey size-linear, ([ETH Zurich Math People][1]) but they do not settle whether $K_4^*$ is Ramsey size-linear against arbitrary (possibly non-bipartite) (H). ([ETH Zurich Math People][1])

At this point, any complete proof of the posed claim would, in particular, have to prove that $K_4^*$ is Ramsey size-linear; and any counterexample would likely be found among graphs with $m_2=2$, with $K_4^*$ being the smallest prominent candidate. The current sources provide neither.

I attempted the two natural next steps (proof/disproof tracks) in a self-contained way:

* Proof attempt idea: use the condition $m_2(G)\le 2$ to force structural constraints on (G)-free red graphs strong enough to embed an arbitrary (m)-edge (H) in blue when $N=O(m)$. Failure point: I could not produce a correct general embedding lemma of the form “every (G)-free graph on (N) vertices has complement containing every (m)-edge (H)” with $N=O(m)$, even in the first open case $G=K_4^*$. This is consistent with the state-of-the-art statement that the question is still open. ([ETH Zurich Math People][1])

* Disproof attempt idea: exhibit a specific (G) with $m_2(G)\le 2$ (ideally $K_4^*$) and construct graphs $H_m$ with $e(H_m)=m$ such that $R(G,H_m)$ grows superlinearly in (m). Failure point: I did not find (and the cited sources do not provide) any explicit family $H_m$ proving superlinear growth for any (G) satisfying your hypothesis. In particular, proving $R(K_4^*,K_n)=\omega(n^2)$ (which would disprove size-linearity for $K_4^*$) appears to be exactly what is currently open. ([ETH Zurich Math People][1])

So no complete proof or counterexample emerged.

---

5) VERIFICATION

Quantifier/edge-case checks

* The corrected sparsity condition must be stated for $k\ge 2$; otherwise $k=1$ breaks it. I explicitly fixed this in the restatement. * Since (H) has no isolated vertices, $m=e(H)\ge 1$ and $v(H)\le 2m$, which makes the “$H\subseteq K_{2m}$” step in Lemma 4.2 valid.

Internal consistency

* Lemma 4.1 is purely algebraic and checks out. * Lemma 4.2 relies on: (i) monotonicity of Ramsey numbers under taking subgraphs, and (ii) Chvátal’s exact tree–clique Ramsey number, both standard and directly invoked in the cited note.

Adversarial attempts

* Could Lemma 4.2 fail because (H) might have more than $2m$ vertices? No: “no isolated vertices” forces $2m=\sum \deg(v)\ge v(H)$. * Does size-linearity for forests depend on any unverified conjecture? No; it is a direct consequence of Chvátal’s theorem.

Main goal

* I do not have a proof of the full claim, nor an explicit counterexample family. This matches the web-verified status that the general question and the $K_4^*$ case are open. ([ETH Zurich Math People][1])

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* If (G) is a forest, then (G) is Ramsey size-linear: $R(G,H)\le 2(v(G)-1)e(H)+1$ for all (H) with no isolated vertices (Lemma 4.2, proved above). * The hypothesis “every (k)-vertex subgraph has $\le 2k-3$ edges” is exactly the condition $m_2(G)\le 2$ (Lemma 4.1, proved above).

(ii) Exact first gap (crisp statement I could not prove).

* I could not prove (nor disprove) the following specific instance: \[ \exists C>0\ \forall H\text{ with no isolates}:\ R(K_4^*,H)\le C,e(H), \] where $K_4^*$ is $K_4$ with one edge subdivided once. This is explicitly identified as open in the recent literature. ([ETH Zurich Math People][1])

(iii) Top 3 next moves.

1. Resolve $K_4^*$: either show $R(K_4^*,K_n)=O(n^2)$ (and then extend beyond cliques), or construct $K_4^*$-free graphs with independence $<n$ on $\omega(n^2)$ vertices to get $R(K_4^*,K_n)=\omega(n^2)$. This is the central bottleneck highlighted by Bradač–Gishboliner–Sudakov. ([ETH Zurich Math People][1]) 2. Ramsey–Turán approach: study extremal density/structure of (G)-free graphs with bounded independence number when $m_2(G)=2$, aiming to force a large “blue-embeddable” structure with $N=O(m)$. 3. Embedding lemma for arbitrary (H): develop a general method (likely combining dependent random choice with a decomposition of (H) into a dense core + sparse attachments) that works in any host graph of size (O(e(H))) under the constraint “red avoids (G)” for $m_2(G)\le 2$.

(iv) What a minimal counterexample would likely look like (structural guess, not a proof). If the claim is false, a minimal counterexample (G) (minimal under taking subgraphs) would likely satisfy:

* $m_2(G)=2$ and be “edge-tight” (many subgraphs meeting $e=2v-3$), * 2-connected (otherwise one could reduce to blocks), * and plausibly contain a small “$K_4$-subdivision core,” with $K_4^*$ being the smallest such candidate singled out in the literature. ([ETH Zurich Math People][1])

[1]: https://people.math.ethz.ch/~sudakovb/ramsey-size-linear-graphs.pdf "On Ramsey Size-Linear Graphs and Related Questions | SIAM Journal on Discrete Mathematics | Vol. 38, No. 1 | Society for Industrial and Applied Mathematics"

Your “([ETH Zurich Math People][1])” is pointing at the Bradač–Gishboliner–Sudakov paper whose PDF is hosted on an ETH Zürich page (Sudakov’s site). Here is the clean bibliographic identification, plus the exact places in the paper that justify the two claims you attached that footnote to.

What $[1]$ should be

[1] D. Bradač, L. Gishboliner, B. Sudakov, On Ramsey size-linear graphs and related questions, SIAM Journal on Discrete Mathematics 38$1$ $2024$, 225–242. DOI: 10.1137/22M1481713. ([ETH Zurich Math People][1])

If you want an arXiv identifier as well: the preprint version is arXiv:2202.10388. ([arXiv][2])

Why this is the right citation for your “central bottleneck” sentence

In their introduction they explicitly say:

* the general question “every (H) with $m_2(H)\le 2$ is Ramsey size-linear” is still out of reach, and * they single out $K_4^*$ (their notation $K_4^*$ / $K_4^\ast$) as a specific asked-open case, and * they state they cannot answer it affirmatively, but prove it at least when (F) is bipartite.

All of that is in the block around their Theorem 3. ([ETH Zurich Math People][1])

So your line

“This is the central bottleneck highlighted by Bradač–Gishboliner–Sudakov.”

is accurately supported by that passage. ([ETH Zurich Math People][1])

---

A second reference you may want to cite alongside $[1]$

Balister already stated the “subdivide one edge once” question very explicitly in 2001:

[2] P. N. Balister, A note on Ramsey size-linear graphs $2001$.

He writes (paraphrasing): it is an open question whether $K_4$ with one edge subdivided just once is Ramsey size-linear, and he labels this as “Question 1.”

This is also where the “minimal counterexample” heuristics you wrote down line up nicely with Balister’s own structural questions: he asks whether adding a 2-edge path between two vertices preserves size-linearity (Question 2) and then discusses graphs with no cut vertex and minimum degree at least 3 as potential obstructions (Question 3).

That supports your “2-connected / tight” guess theme much more directly than the Bradač–Gishboliner–Sudakov paper does.

---

If you want the actual URLs for your footnote list

(Per your bracket style, here they are in a code block so they’re easy to paste.)

"`text [1] https://people.math.ethz.ch/~sudakovb/ramsey-size-linear-graphs.pdf (SIAM J. Discrete Math. 38$1$, 2024; DOI 10.1137/22M1481713)

[2] https://www.memphis.edu/msci/people/pbalistr/ramsl.pdf "`

If you want, I can also format $[1]$ and $[2]$ as BibTeX entries (journal + arXiv + DOI) in your exact style.

[1]: https://people.math.ethz.ch/~sudakovb/ramsey-size-linear-graphs.pdf "On Ramsey Size-Linear Graphs and Related Questions | SIAM Journal on Discrete Mathematics | Vol. 38, No. 1 | Society for Industrial and Applied Mathematics" [2]: https://arxiv.org/pdf/2202.10388?utm_source=chatgpt.com "On Ramsey size-linear graphs and related questions"

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

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