Turán-type results for intersection graphs of boxes
Turán-type results for intersection graphs of boxes
复制标题
方框交集图的 Turán 型结果
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Zakharov
中科院分区：
文献类型：
--
作者：
István Tomon;D. Zakharov
在这篇简短的文章中，我们证明了盒交图的 Kővári-Sós-Turán 定理的以下模拟。如果 G 是 n 个轴平行框的交集
$${{mathbb{R}}^d}$$
使得 G 不包含 K 的副本
t,t
，则 G 至多有 ctn( log n)2d+3 条边，其中 c = c(d)>0 仅取决于 d。我们的证明基于探索盒子性、分离维数和偏序集维数之间的联系。使用这种方法，我们还表明，Basit、Chernikov、Starchenko、Tao 和 Tran 的平面中点和矩形的 K2,2 无关联图的构造可用于反驳 Alon、Basavaraju、Chandran、Mathew 和 Rajendraprasad 的猜想。我们证明存在具有超线性边数的分离维数为 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, Chernikov, Starchenko, Tao and Tran of K2,2-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon, Basavaraju, Chandran, Mathew and Rajendraprasad. We show that there exist graphs of separation dimension 4 having superlinear number of edges.
半线性超图的 Zarankiewicz 问题
DOI：
10.1017/fms.2021.52
发表时间：
2021
期刊：
Sigma
影响因子：
--
作者：
Basit, Abdul;Chernikov, Artem;Starchenko, Sergei;Tao, Terence;Tran, Chieu-Minh
通讯作者：
Tran, Chieu-Minh