标题： 多少随机边可以使一个稠密的超图不可2-着色？ 显示英文标题

标题： How many random edges make a dense hypergraph non-2-colorable?

摘要： 我们研究了一个随机均匀超图的模型，其中随机实例是通过向给定密度的大超图添加随机边得到的。 我们得到了确保非2-可着色所需的随机边数的紧界。 我们证明了对于任何k-均匀超图，当边数为Ω(n^{k-epsilon})时，添加ω(n^{k 紊流粘性/2})随机边会使超图几乎肯定不可2-着色。 这基本上是紧的，因为存在一个2-可着色的超图，其边数为Ω(n^{k-\epsilon })，即使在添加o(n^{k \epsilon / 2})随机边后，它几乎肯定仍保持2-可着色。 显示英文摘要

摘要： We study a model of random uniform hypergraphs, where a random instance is obtained by adding random edges to a large hypergraph of a given density. We obtain a tight bound on the number of random edges required to ensure non-2-colorability. We prove that for any k-uniform hypergraph with Omega(n^{k-epsilon}) edges, adding omega(n^{k epsilon/2}) random edges makes the hypergraph almost surely non-2-colorable. This is essentially tight, since there is a 2-colorable hypergraph with Omega(n^{k-\epsilon}) edges which almost surely remains 2-colorable even after adding o(n^{k \epsilon / 2}) random edges.