Clean H-free classes from finite families
Question: finite families yielding clean H-free classes · arXiv:2212.02737
Status partial high confidence
The companion paper (arXiv:2311.05066, published in Advances in Combinatorics) by Alecu, Chudnovsky, Hajebi, and Spirkl proves Theorem 1.4: for a finite set $\mathcal{H}$ of graphs, the class of all $\mathcal{H}$-free graphs is clean if and only if there are only finitely many $n \in \mathbb{N}$ for which an $\mathcal{H}$-free $n$-array exists. This provides a complete necessary and sufficient condition in terms of $n$-arrays and reduces the question to understanding when $\mathcal{H}$-free arrays can be constructed for all large $n$. A direct structural characterization of exactly which families $\mathcal{H}$ satisfy this array condition — analogous to the single-graph case where $H$ must be a subdivided star forest — does not appear to follow immediately from these results.
Cited literature (1)
-
partial Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$ (2024)
Proves Theorem 1.4: the class of $\mathcal{H}$-free graphs is clean if and only if only finitely many $n$ admit an $\mathcal{H}$-free $n$-array; this is the companion paper [6] promised in arXiv:2212.02737, addressing the finite-family question via an array-based characterization.
Reviewer notes. The companion paper [6] referenced in arXiv:2212.02737 is arXiv:2311.05066 (Part XIII of the series), by four of the five original authors (Alecu, Chudnovsky, Hajebi, Spirkl — without Abrishami), submitted to arXiv on November 9, 2023 and published in Advances in Combinatorics. It fully resolves the question in terms of $n$-arrays (Theorem 1.4), but the status is classified 'partial' because the array condition itself may not admit a simple structural description of $\mathcal{H}$; Theorem 1.6 additionally connects the condition to 'tasselled' families. A purely structural characterization of the clean finite families analogous to the single-graph case appears to remain open.
Context
After proving Theorem 1.5 — which characterizes all single graphs $H$ for which the class $\mathcal{F}_H$ of $H$-free graphs is clean (precisely the subdivided star forests) — the authors pose the next natural step. They observe that any finite set $\mathcal{H}$ containing a subdivided star forest yields a clean class, but note that the converse fails (e.g., $\mathcal{H}=\{H, K_3\}$ for the unique double star on six vertices is also clean). A full description is deferred to a companion paper [6] by four of the five authors.
Notes. Posed as a natural next step in running prose (no labelled theorem environment). The companion paper [6] is announced to resolve it; PDF source is truncated after Section 2, so later sections may contain additional items not captured here.
Source paper
Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2023-11-07
https://arxiv.org/abs/2212.02737
PDF source