Sparse Strong EH-property Characterizes Forests

Status solved high confidence

Conjecture 1.5 is fully resolved. The 'only if' direction — that the sparse strong EH-property forces H to be a forest — was already known from Erdős's construction. The converse — that every forest H has the sparse strong EH-property — was proved by Chudnovsky, Scott, Seymour, and Spirkl in 'Pure Pairs. I. Trees and Linear Anticomplete Pairs' (arXiv:1809.00919), which appeared as an arXiv preprint in September 2018 (one month before the caterpillar paper) and was published in Advances in Mathematics in 2020; Seymour and Spirkl are co-authors on both papers.

Cited literature (1)

• proof Pure pairs. I. Trees and linear anticomplete pairs (2020)
  Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · Advances in Mathematics · arXiv:1809.00919

  Proves that for every forest H there exists c > 0 such that every H-free graph G with |V(G)| > 1 either has a vertex of degree at least c|V(G)| or contains two disjoint anticomplete sets each of size at least c|V(G)|, establishing the 'if H is a forest' direction and thereby completing the proof of Conjecture 1.5.

Reviewer notes. arXiv:1809.00919 was submitted in September 2018, one month before arXiv:1810.00811 (October 2018). Seymour and Spirkl are co-authors of both papers; the caterpillar paper may have been written concurrently and states the conjecture for context. The journal publication (Advances in Mathematics, 2020) is the post-2018 venue cited here. The URL https://arxiv.org/abs/1809.00919 was confirmed by multiple independent search results but was not directly WebFetched due to the call-count limit.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).