The feasible region of hypergraphs
The feasible region of hypergraphs
复制标题
超图的可行域
DOI：
10.1016/j.jctb.2020.12.004
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Mubayi, Dhruv
中科院分区：
文献类型：
--
作者：
Liu, Xizhi;Mubayi, Dhruv
设F是一类r-一致超图。F的可行域Ω（F）是单位正方形中的点（x，y）的集合，使得存在一列无F的r-一致超图，其阴影密度接近x，边密度接近y。可行域提供了大量的组合信息，例如，y在所有（x，y）∈ Ω（F）上的上确界是Turán密度π（F），Ω（F）给出了Kruskal-Katona定理。本文对Ω（F）进行了系统的研究，证明了Ω（F）完全由一个左连续的几乎处处可微函数决定，并且存在一个函数对它不连续的F.我们也推广了一些旧的相关定理。例如，我们将Fisher和Ryan的一个结果推广到超图，并通过几乎完全确定可消三元系的可行域来扩展Bollobás的一个经典结果。
Let F be a family of r-uniform hypergraphs. The feasible region Ω (F) of F is the set of points (x, y) in the unit square such that there exists a sequence of F-free r-uniform hypergraphs whose shadow density approaches x and whose edge density approaches y. The feasible region provides a lot of combinatorial information, for example, the supremum of y over all (x, y)∈ Ω (F) is the Turán density π (F), and Ω (∅) gives the Kruskal-Katona theorem. We undertake a systematic study of Ω (F), and prove that Ω (F) is completely determined by a left-continuous almost everywhere differentiable function; and moreover, there exists an F for which this function is not continuous. We also extend some old related theorems. For example, we generalize a result of Fisher and Ryan to hypergraphs and extend a classical result of Bollobás by almost completely determining the feasible region for cancellative triple systems.
登录
查看更多内容
不稳定的超图图兰问题
DOI：
--
发表时间：
2019
期刊：
Comb.
影响因子：
--
作者：
Xizhi Liu;D. Mubayi
通讯作者：
D. Mubayi
DOI：
10.1016/0012-365x(92)90323-8
发表时间：
1992-05
期刊：
Discret. Math.
影响因子：
--
作者：
David C. Fisher;J. Ryan
通讯作者：
David C. Fisher;J. Ryan
扩展完整 2 图的超图 Turán 函数的精确计算
DOI：
10.1016/j.jctb.2012.09.005
发表时间：
2005
期刊：
J. Comb. Theory B
影响因子：
--
作者：
O. Pikhurko
通讯作者：
O. Pikhurko
关于图中三角形的最小密度
DOI：
10.1017/s0963548308009085
发表时间：
2008
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
A. Razborov
通讯作者：
A. Razborov
影响因子：
0.3
作者：
Hamed Hatami;S. Norin
通讯作者：
S. Norin