论文标题
关于Erdős-Hajnal Hypergraph Ramsey问题的注释
A note on the Erdős-Hajnal hypergraph Ramsey problem
论文作者
论文摘要
我们证明有一个绝对常数$ c> 0 $，以便以下内容保留。对于每$ n> 1 $，至少有一个5均匀的超图，至少$ 2^{2^{2^{cn^{1/4}}} $ vertices $ vertices具有独立数字的最多$ n $，其中每组6套顶点最多在3个边缘引起。顶点数量的双重指数增长率很清晰。通过应用前两位作者建立的加速引理，证明了$ K $均匀的超图的类似结果。这回答了1972年Erdős和Hajnal提出的Ramsey理论中猜想的倒数第二个公开案例。
We show that there is an absolute constant $c>0$ such that the following holds. For every $n > 1$, there is a 5-uniform hypergraph on at least $2^{2^{cn^{1/4}}}$ vertices with independence number at most $n$, where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for $k$-uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.
