Patrick Morris

Motivated by the investigation of sharpness of thresholds for Ramsey properties in random graphs, Friedgut, Kohayakawa, Rödl, Ruciński and Tetali introduced two variants of a single‐player game whose goal is to colour the edges of a random graph, in an online fashion, so as not to create a monochromatic triangle. In the two‐round variant of the game, the player is first asked to find a triangle‐free colouring of the edges of a random graph and then extend this colouring to a triangle‐free colouring of the union of and another (independent) random graph , which is disclosed to the player only after they have coloured . Friedgut et al. analysed this variant of the online Ramsey game in two instances: when has edges and when the number of edges of is just below the threshold above which a random graph typically no longer admits a triangle‐free colouring, which is located at . The two‐round Ramsey game has been recently revisited by Conlon, Das, Lee and Mészáros, who generalised the result of Friedgut et al. from triangles to all strictly 2‐balanced graphs. We extend the work of Friedgut et al. in an orthogonal direction and analyse the triangle case of the two‐round Ramsey game at all intermediate densities. More precisely, for every , with the exception of , we determine the threshold density at which it becomes impossible to extend any triangle‐free colouring of a typical to a triangle‐free colouring of the union of and . An interesting aspect of our result is that this threshold density ‘jumps’ by a polynomial quantity as crosses a “critical” window around .

In an array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than times, the array contains a transversal of size . In particular, if the array is filled with symbols, each appearing times (an equi‐ square), we get transversals of size . Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals.

For a graph and , we denote by the random sparsification of obtained by keeping each edge of independently, with probability . We show that there exists a such that if and is an ‐vertex graph with and , then with high probability contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of , are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in (corresponding to in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least which gets close to the truth.

An n -vertex graph is said to to be (p,\beta) -bijumbled if for any vertex sets A,B\subseteq V(G) , we have e(A,B)=p|A|\,|B|\pm \beta \sqrt{|A|\,|B|}. We prove that for any r\in {\mathbb N}_{\ge3} and c>0 there exists an \varepsilon>0 such that any n -vertex (p,\beta) -bijumbled graph with n\in r \mathbb{N} , p>0 , \delta(G)\geq cpn and \beta \leq \varepsilon p^{r-1}n contains a K_{r} -factor. This implies a corresponding result for the stronger pseudorandom notion of (n,d,\lambda) -graphs. For the case of triangle factors, that is, when r=3 , this result resolves a conjecture of Krivelevich, Sudakov and Szabó from 2004 and it is tight due to a pseudorandom triangle-free construction of Alon. In fact, in this case even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition of \beta=o(p^{2}n) actually guarantees that a (p,\beta) -bijumbled graph G contains every graph on n vertices with maximum degree at most 2.