English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The areas of Ramsey theory and random graphs have been closely linked eversince Erd\H{o}s' famous proof in 1947 that the 'diagonal' Ramsey numbers $R(k)$grow exponentially in $k$. In the early 1990s, the triangle-free process wasintroduced as a model which might potentially provide good lower bounds for the'off-diagonal' Ramsey numbers $R(3,k)$. In this model, edges of $K_n$ areintroduced one-by-one at random and added to the graph if they do not create atriangle; the resulting final (random) graph is denoted $G_{n,\triangle}$. In2009, Bohman succeeded in following this process for a positive fraction of itsduration, and thus obtained a second proof of Kim's celebrated result that$R(3,k) = \Theta \big( k^2 / \log k \big)$.  In this paper we improve the results of both Bohman and Kim, and follow thetriangle-free process all the way to its asymptotic end. In particular, weshall prove that $$e\big( G_{n,\triangle} \big) \,=\, \left(\frac{1}{2\sqrt{2}} + o(1) \right) n^{3/2} \sqrt{\log n },$$ with highprobability as $n \to \infty$. We also obtain several pseudorandom propertiesof $G_{n,\triangle}$, and use them to bound its independence number, whichgives as an immediate corollary $$R(3,k) \, \ge \, \left( \frac{1}{4} - o(1)\right) \frac{k^2}{\log k}.$$ This significantly improves Kim's lower bound,and is within a factor of $4 + o(1)$ of the best known upper bound, proved byShearer over 25 years ago.

The triangle-free process and the Ramsey number $R(3,k)$