Perhaps somewhat boldly, we conjecture this would be optimal.
Statement
Perhaps somewhat boldly, we conjecture this would be optimal. 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 ensur
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.