论文标题
Turán类型的盒子交点图的结果
Turán-type results for intersection graphs of boxes
论文作者
论文摘要
在此简短的说明中，我们证明了KőVári-Sós-Turán定理的以下类似物用于盒子的交叉图。 If $G$ is the intersection graph of $n$ axis-parallel boxes in $\mathbb{R}^{d}$ such that $G$ contains no copy of $K_{t,t}$, then $G$ has at most $ctn(\log n)^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$.我们的证明是基于探索框架，分离维度和POSET维度之间的连接。 使用这种方法，我们还表明了Basit等人的构造。 $ k_ {2,2} $ - 飞机上的点和矩形的自由入射图可用于反驳Alon等人的猜想。我们证明存在具有超线性边缘数的分离维度4的图。
In this short note, we prove the following analog of the Kővári-Sós-Turán theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in $\mathbb{R}^{d}$ such that $G$ contains no copy of $K_{t,t}$, then $G$ has at most $ctn(\log n)^{2d+3}$ edges, where $c=c(d)>0$ only depends on $d$. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit et al. of $K_{2,2}$-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.
