Conjecture 2. 2 1 k R(3, k) = + o(1) .
Statement
Conjecture 2. 2 1 k R(3, k) = + o(1) . 2 log k In fact, we have a conjectural construction, based on the Cayley sum graph generated by the sum-free process on Fd2 , that would imply the lower bound in this conjecture along an infinite sequence. The construction. Our construction is actually quite easy to describe: we first sample a random graph on n/(log n)2 vertices at density p0 = \alpha0 (log n/n)1/2 , clean out triangles, blow it up and then run a variant of the triangle-free process with the resulting graph. Interestingly, this supplies the desired graph: the blow up allows for more edges and the triangle-free process “counters” the large independent sets introduced by the blow up. A modified triangle-free process. The reason we work with a variant of the triangle-free process is that the triangle-free process exhibits a complicated dynam- ics that requires an extremely subtle analysis. For example, in both [3] and [8], the authors need to show the highly non-trivial interaction and “self correction” properties of certain martingales associated with the process. By contrast, in our process, we are able to avoid these subtleties entirely, by manually “steering” the process to ensure it follows a simpler trajectory. This results in a greatly simplified analysis and more straightforward proof. In particular, if we apply our version of the triangle-free process without our initial “seed” step where we take a blow up of a random graph, our analysis gives a much simpler proof of the lower bound (1) on R(3, k) proved in [3, 8]. Perhaps the most interesting consequence of Theorem 1 is that it strongly sug- gests that the natural triangle-free process is not optimal for Ramsey and rather suggests that the optimal graphs mix randomness with some underlying structure. Philosophy behind the construction. The main intuition behind Theorem 1 is the feeling that there should exist triangle-free graphs that are denser than the triangle-free process but still sufficiently pseudo-random so that the independence number is the same as the binomial random graph at the same density. If one thinks of the triangle-free process as the “most random” graph at its density, the idea behind our construction is to “trade-off” some of this “randomness” to obtain a slightly denser graph. In fact we believe that a even better trade-off is possible and that one should be able to obtain a constant of 1/2 + o(1) in the lower-bound, but we were unable to provide such a construction. Perhaps somewhat boldly, we conjecture this would be optimal.
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.