The Local Structure Theorem for Graph Minors with finite index
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911553979154432 |
|---|---|
| author | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian |
| author_facet | Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian |
| contents | The Local Structure Theorem (LST) for Graph Minors roughly states that for every $H$-minor-free graph $G$ that contains a sufficiently large wall $W$, there is a small vertex subset $A,$ whose removal yields a graph that admits an "almost embedding" $δ$ on a surface $Σ$ on which $H$ does not embed. By almost embedding, we mean that there exists a hypergraph $\mathcal{H}$ whose vertex set is a subset of the vertex set of $G - A$ and an embedding of $\mathcal{H}$ on $Σ$ such that the drawing of each hyperedge of $\mathcal{H}$ corresponds to a cell of $δ,$ the boundary of each cell intersects only the vertices of the corresponding hyperedge, and all remaining vertices and edges of $G - A$ are drawn in the interior of cells. The cells corresponding to hyperedges of arity at least $4$, called vortices, are few in number and have small "depth", while "most" of the wall $W$ is disjoint from the vortices and is "grounded" in the embedding $δ$.
Suppose that the subgraphs drawn inside each of the non-vortex cells are equipped with some finite index, i.e., each such cell is assigned a color from a finite set. We prove a version of the LST in which the set $C$ of colors assigned to the non-vortex cells exhibits "large" bidimensionality: $G - A$ contains a minor model of a large grid $Γ$ such that, for every color $α\in C$, the model of each vertex of $Γ$ contains the subgraph drawn within an $α$-colored cell. Moreover, $Γ$ can be chosen in a way that is "well-connected" to the original wall $W$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02769 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Local Structure Theorem for Graph Minors with finite index Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian Combinatorics Discrete Mathematics 05C83, 05C85, 05C10, 05C75, 68R10 G.2.2 The Local Structure Theorem (LST) for Graph Minors roughly states that for every $H$-minor-free graph $G$ that contains a sufficiently large wall $W$, there is a small vertex subset $A,$ whose removal yields a graph that admits an "almost embedding" $δ$ on a surface $Σ$ on which $H$ does not embed. By almost embedding, we mean that there exists a hypergraph $\mathcal{H}$ whose vertex set is a subset of the vertex set of $G - A$ and an embedding of $\mathcal{H}$ on $Σ$ such that the drawing of each hyperedge of $\mathcal{H}$ corresponds to a cell of $δ,$ the boundary of each cell intersects only the vertices of the corresponding hyperedge, and all remaining vertices and edges of $G - A$ are drawn in the interior of cells. The cells corresponding to hyperedges of arity at least $4$, called vortices, are few in number and have small "depth", while "most" of the wall $W$ is disjoint from the vortices and is "grounded" in the embedding $δ$. Suppose that the subgraphs drawn inside each of the non-vortex cells are equipped with some finite index, i.e., each such cell is assigned a color from a finite set. We prove a version of the LST in which the set $C$ of colors assigned to the non-vortex cells exhibits "large" bidimensionality: $G - A$ contains a minor model of a large grid $Γ$ such that, for every color $α\in C$, the model of each vertex of $Γ$ contains the subgraph drawn within an $α$-colored cell. Moreover, $Γ$ can be chosen in a way that is "well-connected" to the original wall $W$. |
| title | The Local Structure Theorem for Graph Minors with finite index |
| topic | Combinatorics Discrete Mathematics 05C83, 05C85, 05C10, 05C75, 68R10 G.2.2 |
| url | https://arxiv.org/abs/2507.02769 |