论文标题
包装和着色R型轴平行矩形
Packing and coloring r-bounded axis-parallel rectangles
论文作者
论文摘要
令$ \ mathcal {r} $为飞机中的轴 - 平行矩形家族。横向数$τ（\ Mathcal {r}）$是刺穿所有矩形所需的最小点。独立数$ν（\ Mathcal {r}）$是成对分离矩形的最大数量。给定一个正实数$ r $，我们说$ \ mathcal {r} $是一个由R结合的家庭，如果对于$ \ Mathcal {r} $中的任何矩形，则最多$ r $的较短一侧的较长一侧的长宽比最多。 Gyárfás和Lehel询问是否可以将横向数字$τ（\ Mathcal {r}）限制为独立数$ν（\ Mathcal {r}）$的线性函数。 Ahlswede和Karapetyan对特定的$ r $结合家庭的特定案件提出了积极的答案，但没有提供证据。 Chudnovsky等。确认结果证明了绑定的$τ\ leq（14 + 2r^2）ν$。该注释旨在给出$τ\ leq 2（r + 1）（ν-1） + 1 $的简单证明，从而稍微改善了先前的结果。由于这种新方法，我们还推断出在$ r $结合的家族的情况下，对比率$ \fracχΩ$的恒定因素绑定。
Let $\mathcal{R}$ be a family of axis-parallel rectangles in the plane. The transversal number $τ(\mathcal{R})$ is the minimum number of points needed to pierce all the rectangles. The independence number $ν(\mathcal{R})$ is the maximum number of pairwise disjoint rectangles. Given a positive real number $r$, we say that $\mathcal{R}$ is an r-bounded family if, for any rectangle in $\mathcal{R}$, the aspect ratio of the longer side over the shorter side is at most $r$. Gyárfás and Lehel asked if it is possible to bound the transversal number $τ(\mathcal{R})$ with a linear function of the independence number $ν(\mathcal{R})$. Ahlswede and Karapetyan claimed a positive answer for the particular case of $r$-bounded families, but without providing proof. Chudnovsky et al. confirmed the result proving the bound $τ\leq (14 + 2r^2) ν$. This note aims at giving a simple proof of $τ\leq 2(r+1)(ν-1) + 1$, slightly improving the previous results. As a consequence of this new approach, we also deduce a constant factor bound for the ratio $\fracχω$ in the case of $r$-bounded family.
