CaltechAUTHORS
  A Caltech Library Service

Repeated patterns in proper colourings

Conlon, David and Tyomkyn, Mykhaylo (2020) Repeated patterns in proper colourings. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200914-134941914

[img] PDF - Submitted Version
See Usage Policy.

208kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200914-134941914

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 cn² 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 cn 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 ω(1) repeats of T.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2002.00921arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Record Number:CaltechAUTHORS:20200914-134941914
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200914-134941914
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105380
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:14 Sep 2020 21:54
Last Modified:14 Sep 2020 21:54

Repository Staff Only: item control page