论文标题
刺穿和着色盒的下限
Lower bounds for piercing and coloring boxes
论文作者
论文摘要
给定$ \ mathbb {r}^d $中的axis-paralallel框的nameres $ \ mathcal {b} $，让$τ$表示其刺穿数字，而其独立号码为$ν$。对于给定的$ d \ geq 2 $，$τ/ν$是否可以任意大，这是一个古老的问题。在这里，对于每一个$ν$，我们都会构建一个轴平行的盒子的家族，以实现$$τ\ geqω_d（ν）\ cdot \ left（\ frac {\ frac {\ log logvν} {\ log log \ log log log log n log log log log log log log log log log log log c =双重因素。 我们的主要结构对盒子配置的Ramsey和着色属性也具有进一步的影响。我们在$ \ mathbb {r}^{d} $中展示了一个$ n $ box的家族，其相交图的存在和独立性数字$ o_d（n^{1/2}）\ cdot \ left（\ frac {\ frac {\ log n}微不足道的上限$ o_d（n^{1/2}）$，并将最著名的下限与双层型因子相匹配。最后，对于满足$ \ frac {\ log n} {\ log \ log \ log n} \ llω\ ll n^{1- \ varepsilon} $的每一个$ω$，我们构建了一个与$ n $ box的相交图，最多$ n $ $ n $ $ω$，和彩色的$ω____________\ cds \ cds d， \ left（\ frac {\ log n} {\ log \ log n} \ right）^{d-2}。$这与$ o_d（（\ log w）（\ log log \ log \ log \ log \ log n）^{d-2-2}）匹配，最著名的上限与$ o_d（\ log w）的因子匹配。
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})$.
