The vertex sets of subtrees of a tree

2025/06/04 by Chudnovsky, Maria, Nguyen, Tung, Scott, Alex +1 · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.03603

Abstract

Let F be a set of subsets of a set W. When is there a tree T with vertex set W such that each member of F is the set of vertices of a subtree of T? It is necessary that F has the Helly property and the intersection graph of F is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of W belongs to infinitely many infinite sets in F.

Citations

• Asymptotic structure. III. Excluding a fat tree
• Asymptotic structure. II. Path-width and additive quasi-isometry

Cited by

• Line-width and path-width
• Asymptotic structure. III. Excluding a fat tree
• Asymptotic structure. II. Path-width and additive quasi-isometry

Related

• Hypertrees and their host trees: a survey
• Invariant subsets of scattered trees. An application to the tree alternative property of Bonato and Tardif
• Strongly chordal graphs as intersection graphs of trees (Farber's proof revisited)
• Tree sets
• Graphs of bounded chordality