Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2405.02049 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914186689249280 |
|---|---|
| author | Hylasová, Karolína Kaiser, Tomáš |
| author_facet | Hylasová, Karolína Kaiser, Tomáš |
| contents | The shrinking operation converts a hypergraph into a graph by choosing, from each hyperedge, two endvertices of a corresponding graph edge. A hypertree is a hypergraph which can be shrunk to a tree on the same vertex set. Klimošová and Thomassé [J. Combin. Theory Ser. B 156 (2022), 250--293] proved (as a tool to obtain their main result on edge-decompositions of graphs into paths of equal length) that any rank $3$ hypertree $T$ can be shrunk to a tree where the degree of each vertex is at least $1/100$ times its degree in $T$. We prove a stronger and a more general bound, replacing the constant $1/100$ with $1/2k$ when the rank is $k$. In place of entropy compression (used by Klimošová and Thomassé), we use a hypergraph orientation lemma combined with a characterisation of edge-coloured graphs admitting rainbow spanning trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_02049 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hypertree shrinking avoiding low degree vertices Hylasová, Karolína Kaiser, Tomáš Combinatorics The shrinking operation converts a hypergraph into a graph by choosing, from each hyperedge, two endvertices of a corresponding graph edge. A hypertree is a hypergraph which can be shrunk to a tree on the same vertex set. Klimošová and Thomassé [J. Combin. Theory Ser. B 156 (2022), 250--293] proved (as a tool to obtain their main result on edge-decompositions of graphs into paths of equal length) that any rank $3$ hypertree $T$ can be shrunk to a tree where the degree of each vertex is at least $1/100$ times its degree in $T$. We prove a stronger and a more general bound, replacing the constant $1/100$ with $1/2k$ when the rank is $k$. In place of entropy compression (used by Klimošová and Thomassé), we use a hypergraph orientation lemma combined with a characterisation of edge-coloured graphs admitting rainbow spanning trees. |
| title | Hypertree shrinking avoiding low degree vertices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.02049 |