Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe triangle-free process and the Ramsey number $R(3,k)$
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The areas of Ramsey theory and random graphs have been closely linked ever since ErdH{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 was introduced 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$ are introduced one-by-one at random and added to the graph if they do not create a triangle; the resulting final (random) graph is denoted $G_{n,triangle}$. In 2009, Bohman succeeded in following this process for a positive fraction of its duration, and thus obtained a second proof of Kims 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 the triangle-free process all the way to its asymptotic end. In particular, we shall prove that $$ebig( G_{n,triangle} big) ,=, left( frac{1}{2sqrt{2}} + o(1) right) n^{3/2} sqrt{log n },$$ with high probability as $n to infty$. We also obtain several pseudorandom properties of $G_{n,triangle}$, and use them to bound its independence number, which gives as an immediate corollary $$R(3,k) , ge , left( frac{1}{4} - o(1) right) frac{k^2}{log k}.$$ This significantly improves Kims lower bound, and is within a factor of $4 + o(1)$ of the best known upper bound, proved by Shearer over 25 years ago.
rate research
Read More
The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and ErdH{o}s conjectured that r(K_3,Q_n) = 2^{n+1} - 1 for every n in N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) le 7000 cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n to infty.
In 1967, ErdH{o}s asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of ErdH{o}s and Hajnal together with Shearers classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 sqrt{2} + o(1)) sqrt{n/log n}$. We improve this bound by a factor $sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.
Building on previous work of the author, for each finite triangle-free graph $mathbf{G}$, we determine the equivalence relation on the copies of $mathbf{G}$ inside the universal homogeneous triangle-free graph, $mathcal{H}_3$, with the smallest number of equivalence classes so that each one of the classes persists in every isomorphic subcopy of $mathcal{H}_3$. This characterizes the exact big Ramsey degrees of $mathcal{H}_3$. It follows that the triangle-free Henson graph is a big Ramsey structure.
Given a hypergraph $H$, the size-Ramsey number $hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and Rodl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $hat{r}_2(P^{(3)}_n) = O(n^{3/2} log^{3/2} n)$.
Given a class $mathcal{C}$ of graphs and a fixed graph $H$, the online Ramsey game for $H$ on $mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $mathcal C$, and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$, Painter wins the online Ramsey game for $H$ on $F$-free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$-free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$-minor-free graphs, extending a result by Grytczuk, Ha{l}uszczak, and Kierstead.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
