Tight Bounds for Hypercube Minor-Universality
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910820334567424 |
|---|---|
| author | Hogan, Emma Michel, Lukas Scott, Alex Tamitegama, Youri Tan, Jane Tsarev, Dmitry |
| author_facet | Hogan, Emma Michel, Lukas Scott, Alex Tamitegama, Youri Tan, Jane Tsarev, Dmitry |
| contents | Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant $c>0$ such that any graph with at most $c\cdot2^d/d$ edges and no isolated vertices is a minor of the $d$-dimensional hypercube $Q_d$, while there is an absolute constant $K > 0$ such that $Q_d$ is not $(K\cdot2^d/\sqrt{d})$-minor-universal. We show that $Q_d$ does not contain 3-uniform expander graphs with $C\cdot2^d/d$ edges as minors. This matches the lower bound up to a constant factor and answers one of their questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06629 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Hypercube Minor-Universality Hogan, Emma Michel, Lukas Scott, Alex Tamitegama, Youri Tan, Jane Tsarev, Dmitry Combinatorics 05C83 Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant $c>0$ such that any graph with at most $c\cdot2^d/d$ edges and no isolated vertices is a minor of the $d$-dimensional hypercube $Q_d$, while there is an absolute constant $K > 0$ such that $Q_d$ is not $(K\cdot2^d/\sqrt{d})$-minor-universal. We show that $Q_d$ does not contain 3-uniform expander graphs with $C\cdot2^d/d$ edges as minors. This matches the lower bound up to a constant factor and answers one of their questions. |
| title | Tight Bounds for Hypercube Minor-Universality |
| topic | Combinatorics 05C83 |
| url | https://arxiv.org/abs/2502.06629 |