Finding dense minors using average degree
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915580142944256 |
|---|---|
| author | Hendrey, Kevin Norin, Sergey Steiner, Raphael Turcotte, Jérémie |
| author_facet | Hendrey, Kevin Norin, Sergey Steiner, Raphael Turcotte, Jérémie |
| contents | Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$-vertex minor in graphs of average degree at least $t-1$. We show that if $G$ has average degree at least $t-1$, it contains a minor on $t$ vertices with at least $(\sqrt{2}-1-o(1))\binom{t}{2}$ edges. We show that this cannot be improved beyond $\left(\frac{3}{4}+o(1)\right)\binom{t}{2}$. Finally, for $t\leq 6$ we exactly determine the number of edges we are guaranteed to find in the densest $t$-vertex minor in graphs of average degree at least $t-1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_01184 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Finding dense minors using average degree Hendrey, Kevin Norin, Sergey Steiner, Raphael Turcotte, Jérémie Combinatorics 05C07, 05C35, 05C83 Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$-vertex minor in graphs of average degree at least $t-1$. We show that if $G$ has average degree at least $t-1$, it contains a minor on $t$ vertices with at least $(\sqrt{2}-1-o(1))\binom{t}{2}$ edges. We show that this cannot be improved beyond $\left(\frac{3}{4}+o(1)\right)\binom{t}{2}$. Finally, for $t\leq 6$ we exactly determine the number of edges we are guaranteed to find in the densest $t$-vertex minor in graphs of average degree at least $t-1$. |
| title | Finding dense minors using average degree |
| topic | Combinatorics 05C07, 05C35, 05C83 |
| url | https://arxiv.org/abs/2307.01184 |