An algorithmic framework for obtaining lower bounds for random Ramsey problems

作者：Nenadov Rajko^*; Person Yury; Skoric Nemanja; Steger Angelika

来源：Journal of Combinatorial Theory - Series B, 2017, 124: 1-38.

DOI：10.1016/j.jctb.2016.12.007

• Ramsey-type problems
• Random graphs
• O-statement
• Rainbow and properly colored graphs
• Anti-Ramsey
• Hypergraphs

In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algorithmic perspective: we aim at providing an algorithm that finds the desired coloring with high probability. Our framework allows to reduce the probabilistic problem of whether the Ramsey property at hand holds for random (hyper)graphs with edge probability p to a deterministic question of whether there exists a finite graph that forms an obstruction.
In the second part of the paper we apply this framework to address and solve various open problems. In particular, we extend the result of Bohman, Frieze, Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs to the case of 2 colors and to hypergraph cliques. As a corollary, this proves a matching lower bound for the result of Friedgut, Radl and Schacht (2010) and, independently, Conlon and Cowers (2016) for the classical Ramsey problem for hypergraphs in the case of cliques. Finally, we provide matching lower bounds for a proper-coloring version of anti-Ramsey problems introduced by Kohayakawa, Konstadinidis and Mota (2014) in the case of cliques and cycles.

• 出版日期2017-5