๐ฎ
๐ฎ
The Ethereal
Faithful universal graphs for minor-closed classes
April 28, 2025 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Paul Bastide, Louis Esperet, Carla Groenland, Claire Hilaire, Clรฉment Rambaud, Alexandra Wesolek
arXiv ID
2504.19582
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
1
Venue
arXiv.org
Last Checked
3 months ago
Abstract
It was proved by Huynh, Mohar, ล รกmal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed $t$, if a graph $G$ is $K_t$-minor-free and contains every $n$-vertex planar graph as a subgraph, then $G$ has $2^{ฮฉ(n)}$ vertices. On the other hand, we construct a polynomial size $K_4$-minor-free graph containing every $n$-vertex tree as an induced subgraph, and a polynomial size $K_7$-minor-free graph containing every $n$-vertex $K_4$-minor-free graph as induced subgraph. This answers several problems raised recently by Bergold, Irลกiฤ, Lauff, Orthaber, Scheucher and Wesolek. We study more generally the order of universal graphs for various classes (of graphs of bounded degree, treedepth, pathwidth, or treewidth), if the universal graphs retain some of the structure of the original class.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal