We prove that the probability of crossing a large square in quenched Voronoi percolation converges to 1/2 at criticality, confirming a conjecture of Benjamini, Kalai and Schramm from 1999. The main new tools are a quenched version of the box-crossing
property for Voronoi percolation at criticality, and an Efron-Stein type bound on the variance of the probability of the crossing event in terms of the sum of the squares of the influences. As a corollary of the proof, we moreover obtain that the quenched crossing event at criticality is almost surely noise sensitive.
The Ramsey number r(K_s,Q_n) is the smallest positive integer N such that every red-blue colouring of the edges of the complete graph K_N on N vertices contains either a red n-dimensional hypercube, or a blue clique on s vertices. Answering a questio
n of Burr and ErdH{o}s from 1983, and improving on recent results of Conlon, Fox, Lee and Sudakov, and of the current authors, we show that r(K_s,Q_n) = (s-1) (2^n - 1) + 1 for every s in N and every sufficiently large n in N.
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.
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.
By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices infected at time 0, new vertices are subsequently infected, at each time step, if they have at least $rinmathbb{N}$ previously infected n
eighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$: with $2leq rleq d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that [p_c([n]^d,r)=Thetabiggl(frac{1}{log_{(r-1)}n}biggr)^{d-r+1},] where $log_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))frac{pi^2}{18log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.
