Partitioning ordered hypergraphs
Partitioning ordered hypergraphs
复制标题
划分有序超图
DOI：
10.1016/j.jcta.2020.105300
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Verstraëte, Jacques
中科院分区：
文献类型：
--
作者：
Füredi, Zoltán;Jiang, Tao;Kostochka, Alexandr;Mubayi, Dhruv;Verstraëte, Jacques
有序r-图是顶点集是线性有序的r-一致超图。给定2≤ k≤ r，一个有序r-图H是区间k-部的，如果在有序中至少存在k个不交区间，使得H的每条边与每个区间都有非空交，并且包含在它们的并中.我们的主要结果是：如果α> k− 1，则对任意d> 0，每个n-顶点α边的n-序r-图对某个m≤ n都有一个m-顶点区间k-部Ω（dm α）边的子图.这是对Erdens和Kleitman的观察的有序r-图的一个推广，即每个r-图包含一个边的比例为常数的r-部子图。限制α> k− 1是尖锐的。我们还提出了应用程序的主要结果的几个极值问题的有序超图。
An ordered r-graph is an r-uniform hypergraph whose vertex set is linearly ordered. Given 2≤ k≤ r, an ordered r-graph H is interval k-partite if there exist at least k disjoint intervals in the ordering such that every edge of H has nonempty intersection with each of the intervals and is contained in their union. Our main result implies that if α> k− 1, then for each d> 0 every n-vertex ordered r-graph with d n α edges has for some m≤ n an m-vertex interval k-partite subgraph with Ω (d m α) edges. This is an extension to ordered r-graphs of the observation by Erdős and Kleitman that every r-graph contains an r-partite subgraph with a constant proportion of the edges. The restriction α> k− 1 is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs.
登录
查看更多内容
集合系统中三角形的 Erdős 猜想的证明
影响因子：
1.1
作者：
D. Mubayi;Jacques Verstraëte
通讯作者：
Jacques Verstraëte
Stanley-Wilf 极限通常是指数级的
DOI：
--
发表时间：
2013
期刊：
arXiv.org
影响因子：
--
作者：
J. Fox
通讯作者：
J. Fox
禁止子矩阵
影响因子：
0.8
作者：
R. Anstee;Z. Füredi
通讯作者：
Z. Füredi
集合系统中单纯形簇的新结果
影响因子：
1.1
作者：
Gabriel Currier
通讯作者：
Gabriel Currier
Füredi-Hajnal 猜想中线性界的扩展
DOI：
10.1016/j.aam.2006.05.002
发表时间：
2005
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
Martin Klazar;A. Marcus
通讯作者：
A. Marcus