























A graph $G$ is $m$-minor-universal if every graph with at most $m$ edges (and no isolated vertices) is a minor of $G$. We prove that the $d$-dimensional hypercube, $Q_d$, is $Ω\left(\frac{2^d}{d}\right)$-minor-universal, and that there exists an absolute constant $C >0$ such that $Q_d$ is not $\frac{C2^d}{\sqrt{d}}$-minor-universal. Similar results are obtained in a more generalized setting, where we bound the size of minors in a product of finite connected graphs. A key component of our proof is the following claim regarding the decomposition of a permutation of a box into simpler, one-dimensional permutations: Let $n_1, \dots, n_d$ be positive integers, and define $X := [n_1] \times \dots \times [n_d]$. We prove that every permutation $σ: X \to X$ can be expressed as $σ= σ_1 \circ \dots \circ σ_{2d-1}$, where each $σ_i$ is a one-dimensional permutation, meaning it fixes all coordinates except possibly one. We discuss future directions and pose open problems.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。