Previous work on Ramsey multiplicity focused primarily on the multiplicity of complete graphs of constant size. We study the question for larger complete graphs, specifically showing that in every 2-coloring of a complete graph on @math vertices, there are at least @math monochromatic complete subgraphs of size between @math and @math . We also study bounds on the ratio between a maximum and a random red clique in a graph, and the ratio between a maximum and a random monochromatic clique in a graph.
The latest improvement for @math -free graphs is due to Bansal, Gupta and Guruganesh @cite_2 , proving that @math . There is still a gap in this question, the upper bound being @math for @math -free graphs (also given in @cite_2 ). All three of these papers actually prove that a random independent set in @math is of the given size, and then conclude that therefore the maximum independent set must be at least that size as well.
@cite_2
2950908404
We consider the maximum independent set problem on graphs with maximum degree @math . We show that the integrality gap of the Lov 'asz @math -function based SDP is @math . This improves on the previous best result of @math , and almost matches the integrality gap of @math recently shown for stronger SDPs, namely those obtained using poly- @math levels of the @math semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of @math -free graphs for large values of @math . We also show how to obtain an algorithmic version of the above-mentioned @math -based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of @math matches the best unique-games-based hardness result up to lower-order poly- @math factors.