Does there exist a constant C > 0 such that the following holds?
Statement
Does there exist a constant C > 0 such that the following holds? Mubayi and Verstraete [3] noticed that Theorem 15 gives, via sampling from an appropriate C4 -free graph, a lower bound of Ω(t3/2 / log t) on the cycle-complete Ramsey number r(C4 , t), which matches the result of the C4 -free process. The following question asks for an improvement on Theorem 15. A positive answer to Question 16 would give a quick proof that R(C3 , t) \geq Ω(t2 / log t) by sampling from optimally pseudorandom triangle-free graphs con- structed by Alon [1], and improve by logarithms some of the even cycle-complete Ramsey numbers. Moreover, if true it is nearly tight: the example of random d-regular graphs shows that C must be at least 2. The bound in Question 16 certainly holds true for random d-regular graphs. It’s worth asking as well whether it can be proven for specific (n, d, \lambda)-graphs.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.