Guilherme Oliveira Mota

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for 2 less than or equals k element of double struck upper N 2 ≤ k ∈ N $2\leq k\in {\mathbb{N}}$ , any colouring of the edges of upper K Subscript n K n $K_n$ with n n $n$ sufficiently large gives a copy of upper C Subscript 2 k C 2 k $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if p equals omega left parenthesis n Superscript negative 1 plus 1 divided by left parenthesis 2 k minus 1 right parenthesis Baseline log n right parenthesis p = ω ( n − 1 + 1 / ( 2 k − 1 ) log ⁡ n ) $p=\omega (n^{-1+1/(2k-1)}\log n)$ , then bold upper G left parenthesis n comma p right parenthesis G ( n , p ) ${\mathbf G}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of upper C Subscript 2 k C 2 k $C_{2k}$ . This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a log log $\log$ factor.

Given positive integers $k$ and $\ell$ we write $G \rightarrow (K_k,K_\ell)$ if every 2-colouring of the edges of $G$ yields a red copy of $K_k$ or a blue copy of $K_\ell$ and we denote by $R(k)$ the minimum $n$ such that $K_n\rightarrow (K_k,K_k)$. By using probabilistic methods and hypergraph containers we prove that for every integer $k \geq 3$, there exists a graph $G$ such that $G \nrightarrow (K_k,K_k)$ and $G \rightarrow (K_{R(k)-1},K_{k-1})$. This result can be viewed as a variation of a classical theorem of Nešetřil and Rödl [The Ramsey property for graphs with forbidden complete subgraphs, Journal of Combinatorial Theory, Series B, 20 (1976), 243-249], who proved that for every integer $k\geq 2$ there exists a graph $G$ with no copies of $K_k$ such that $G\rightarrow(K_{k-1}, K_{k-1})$.

Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{\lfloor n^2/4\rfloor}$ for $n \geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n \geq 8$. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{\lfloor n^2/4\rfloor}$ such orientations.

For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer family of such graphs.

For every $k \geq 3$, we determine the order of growth, up to polylogarithmic factors, of the number of orientations of the binomial random graph containing no directed cycle of length $k$. This solves a conjecture of Kohayakawa, Morris and the last two authors.

For graphs $G$ and $H$, let $G {\displaystyle\smash{\begin{subarray}{c} \hbox{$\tiny\rm rb$} \\ \longrightarrow \\ \hbox{$\tiny\rm p$} \end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow $H$ in $G$. It is known that, for every graph $H$, an asymptotic upper bound for the threshold function $p^{\rm rb}_H=p^{\rm rb}_H(n)$ of this property for the random graph $G(n,p)$ is $n^{-1/m^{(2)}(H)}$, where $m^{(2)}(H)$ denotes the so-called maximum $2$-density of $H$. Extending a result of Nenadov, Person, \v{S}kori\'c, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{\rm rb}_{K_k}$ for $k\geq 5$. Furthermore, we show that $p^{\rm rb}_{K_4} = n^{-7/15}$.