Zarankiewicz’s problem for semilinear hypergraphs
Zarankiewicz’s problem for semilinear hypergraphs
复制标题
半线性超图的 Zarankiewicz 问题
DOI：
10.1017/fms.2021.52
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tran, Chieu-Minh
中科院分区：
文献类型：
--
作者：
Basit, Abdul;Chernikov, Artem;Starchenko, Sergei;Tao, Terence;Tran, Chieu-Minh
一个二部图是半线性的，如果对于某些，边关系E由满足s个线性等式和变量不等式的固定布尔组合的点对组成。本文证明了对k为固定值，-free半线性超图H的边数在n中几乎是线性的，即对任意的-free半线性r-部r-一致超图H的边数几乎是线性的.作为应用，我们得到了如下的关联界：给定点和开盒，其平行边为轴，且其关联图为-free，则至多有关联.同样的界也成立，如果不是盒子，而是由任意固定的有限半空间集的平移切出的多面体。我们还得到了匹配的上界和下界。（超线性）下界在平面上的并元盒的情况下，并指出了o-极小结构与模型论可剖性的一些联系（表明对于某些可定义图的几乎线性界限的失败允许以可定义的方式从该图恢复字段操作）。
A bipartite graph with is semilinear if for some and the edge relation E consists of the pairs of points satisfying a fixed Boolean combination of s linear equalities and inequalities in variables for some s. We show that for a fixed k, the number of edges in a -free semilinear H is almost linear in n, namely for any ; and more generally, for a -free semilinear r-partite r-uniform hypergraph.As an application, we obtain the following incidence bound: given points and open boxes with axis-parallel sides in such that their incidence graph is -free, there can be at most incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces.We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o-minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).
登录
查看更多内容
关于相交超图的 Zarankiewicz 问题
DOI：
--
发表时间：
2015
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
Nabil H. Mustafa;J. Pach
通讯作者：
J. Pach
o 最小结构的三分定理
DOI：
--
发表时间：
1998
期刊：
影响因子：
--
作者：
Y. Peterzil;S. Starchenko
通讯作者：
S. Starchenko
半代数超图的扎兰凯维奇问题
DOI：
10.1016/j.jcta.2018.04.007
发表时间：
2017
期刊：
J. Comb. Theory A
影响因子：
--
作者：
Thao T. Do
通讯作者：
Thao T. Do
方框交集图的 Turán 型结果
DOI：
--
发表时间：
2020
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
István Tomon;D. Zakharov
通讯作者：
D. Zakharov
影响因子：
0.8
作者：
N. Alon;Manu Basavaraju;L. Chandran;Rogers Mathew;D. Rajendraprasad
通讯作者：
D. Rajendraprasad