The isoperimetric peak of complete trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911256395382784 |
|---|---|
| author | Bonato, Anthony Mandic, Lazar Marbach, Trent G. Ritchie, Matthew |
| author_facet | Bonato, Anthony Mandic, Lazar Marbach, Trent G. Ritchie, Matthew |
| contents | We give exact values and bounds on the isoperimetric peak of complete trees, improving on known results. For the complete $q$-ary tree of depth $d$, if $q\ge 5$, then we find that the isoperimetric peak equals $d$, completing an open problem. In the case that $q$ is 3 or 4, we determine the value up to three values, and in the case $q=2$, up to a logarithmic additive factor. Our proofs use novel compression techniques, including left, down, and aeolian compressions. We apply our results to show that the vertex separation number and the isoperimetric peak of a graph may be arbitrarily far apart as a function of the order of the graph and give new bounds on the pathwidth and pursuit-evasion parameters on complete trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12989 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The isoperimetric peak of complete trees Bonato, Anthony Mandic, Lazar Marbach, Trent G. Ritchie, Matthew Combinatorics We give exact values and bounds on the isoperimetric peak of complete trees, improving on known results. For the complete $q$-ary tree of depth $d$, if $q\ge 5$, then we find that the isoperimetric peak equals $d$, completing an open problem. In the case that $q$ is 3 or 4, we determine the value up to three values, and in the case $q=2$, up to a logarithmic additive factor. Our proofs use novel compression techniques, including left, down, and aeolian compressions. We apply our results to show that the vertex separation number and the isoperimetric peak of a graph may be arbitrarily far apart as a function of the order of the graph and give new bounds on the pathwidth and pursuit-evasion parameters on complete trees. |
| title | The isoperimetric peak of complete trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.12989 |