Traces of hypergraphs
Traces of hypergraphs
复制标题
超图的踪迹
DOI：
10.1112/jlms.12233
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Solomon, Noam
中科院分区：
文献类型：
--
作者：
Alon, Noga;Moshkovitz, Guy;Solomon, Noam
用表示在任何长度为的二元向量族中保证的在坐标上不同投影的最大数目。经典的Sauer-Perles-Shelah引理暗示了对于。虽然精确地确定一般和似乎无望，估计它仍然是一个广泛开放的问题，连接到计算机科学和组合学的重要问题。例如，Kahn-Kalai-Linial的一个有影响力的结果给出了关于和的非平凡界。在这里，我们证明了，对于，它成立，对于，因此，我们（本质上）确定了对于，并且提到了。为了证明，我们建立了另一个经典结果Kruskal-Katona定理的“稀疏”版本，当超图不诱导稠密子超图时，它给出了更强的保证。此外，我们证明了我们的稀疏Kruskal-Katona定理中的参数基本上是最好的可能。最后，我们提到两个简单的应用程序，这可能是独立的利益。
Letdenote the largest number of distinct projections ontocoordinates guaranteed in any family ofbinary vectors of length. The classical Sauer–Perles–Shelah Lemma implies thatfor. Although determiningprecisely for generalandseems hopeless, estimating it remains a widely open problem with connections to important questions in computer science and combinatorics. For example, an influential result of Kahn–Kalai–Linial gives non‐trivial bounds onforand. Here, we prove that, for, it holds thatwithThus, we (essentially) determineforand allup to.For the proof, we establish a ‘sparse’ version of another classical result, the Kruskal–Katona Theorem, which gives a stronger guarantee when the hypergraph does not induce dense sub‐hypergraphs. Furthermore, we prove that the parameters in our sparse Kruskal–Katona theorem are essentially best possible. Finally, we mention two simple applications which may be of independent interest.
登录
查看更多内容
布尔函数的有影响力的联盟
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
J. Bourgain;J. Kahn;G. Kalai
通讯作者：
G. Kalai
由超平面引起的 k 维中的 N 个点集的分区数
影响因子：
0.7
作者：
E. Harding
通讯作者：
E. Harding
DOI：
--
发表时间：
2009
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
O. Cheong;X. Goaoc;C. Nicaud
通讯作者：
C. Nicaud
缺陷绍尔结果
DOI：
--
发表时间：
1995
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
B. Bollobás;A.J Radcliffe
通讯作者：
A.J Radcliffe