%0 Generic %1 conlon2020repeated %A Conlon, David %A Tyomkyn, Mykhaylo %D 2020 %K Complete_graph Ramsey colouring seminar %T Repeated patterns in proper colourings %U http://arxiv.org/abs/2002.00921 %X For a fixed graph $H$, what is the smallest number of colours $C$ such that there is a proper edge-colouring of the complete graph $K_n$ with $C$ colours containing no two vertex-disjoint colour-isomorphic copies, or repeats, of $H$? We study this function and its generalisation to more than two copies using a variety of combinatorial, probabilistic and algebraic techniques. For example, we show that for any tree $T$ there exists a constant $c$ such that any proper edge-colouring of $K_n$ with at most $c n^2$ colours contains two repeats of $T$, while there are colourings with at least $c' n^3/2$ colours for some absolute constant $c'$ containing no three repeats of any tree with at least two edges. We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$ edges, a colouring with $o(n^(m+1)/m)$ colours contains $ømega(1)$ repeats of $T$.

@misc{conlon2020repeated, abstract = {For a fixed graph $H$, what is the smallest number of colours $C$ such that there is a proper edge-colouring of the complete graph $K_n$ with $C$ colours containing no two vertex-disjoint colour-isomorphic copies, or repeats, of $H$? We study this function and its generalisation to more than two copies using a variety of combinatorial, probabilistic and algebraic techniques. For example, we show that for any tree $T$ there exists a constant $c$ such that any proper edge-colouring of $K_n$ with at most $c n^2$ colours contains two repeats of $T$, while there are colourings with at least $c' n^{3/2}$ colours for some absolute constant $c'$ containing no three repeats of any tree with at least two edges. We also show that for any graph $H$ containing a cycle there exist $k$ and $c$ such that there is a proper edge-colouring of $K_n$ with at most $c n$ colours containing no $k$ repeats of $H$, while, for a tree $T$ with $m$ edges, a colouring with $o(n^{(m+1)/m})$ colours contains $\omega(1)$ repeats of $T$.}, added-at = {2020-02-04T15:46:12.000+0100}, author = {Conlon, David and Tyomkyn, Mykhaylo}, biburl = {https://www.bibsonomy.org/bibtex/2eb6b453141903171af5bb5eb3b4b1e36/j.c.m.janssen}, description = {Repeated patterns in proper colourings}, interhash = {2bef8776f1291b5c34a157c7a3f5f06b}, intrahash = {eb6b453141903171af5bb5eb3b4b1e36}, keywords = {Complete_graph Ramsey colouring seminar}, note = {cite arxiv:2002.00921}, timestamp = {2020-02-04T15:46:12.000+0100}, title = {Repeated patterns in proper colourings}, url = {http://arxiv.org/abs/2002.00921}, year = 2020 }