




















Given a family $\mathcal{B}$ of axis-parallel boxes in $\mathbb{R}^d$, let $τ$ denote its piercing number, and $ν$ its independence number. It is an old question whether $τ/ν$ can be arbitrarily large for given $d\geq 2$. Here, for every $ν$, we construct a family of axis-parallel boxes achieving $$τ\geq Ω_d(ν)\cdot\left(\frac{\log ν}{\log\log ν}\right)^{d-2}.$$ This not only answers the previous question for every $d\geq 3$ positively, but also matches the best known upper bound up to double-logarithmic factors. Our main construction has further implications about the Ramsey and coloring properties of configurations of boxes as well. We show the existence of a family of $n$ boxes in $\mathbb{R}^{d}$, whose intersection graph has clique and independence number $O_d(n^{1/2})\cdot \left(\frac{\log n}{\log\log n}\right)^{-(d-2)/2}.$ This is the first improvement over the trivial upper bound $O_d(n^{1/2})$, and matches the best known lower bound up to double-logarithmic factors. Finally, for every $ω$ satisfying $\frac{\log n}{\log\log n}\ll ω\ll n^{1-\varepsilon}$, we construct an intersection graph of $n$ boxes with clique number at most $ω$, and chromatic number $Ω_{d,\varepsilon}(ω)\cdot \left(\frac{\log n}{\log\log n}\right)^{d-2}.$ This matches the best known upper bound up to a factor of $O_d((\log w)(\log \log n)^{d-2})$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。