CaltechAUTHORS
  A Caltech Library Service

Repeated Patterns in Proper Colorings

Conlon, David and Tyomkyn, Mykhaylo (2021) Repeated Patterns in Proper Colorings. SIAM Journal on Discrete Mathematics, 35 (3). pp. 2249-2264. ISSN 0895-4801. doi:10.1137/21M1414103. https://resolver.caltech.edu/CaltechAUTHORS:20200914-134941914

[img] PDF - Published Version
See Usage Policy.

377kB
[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 colors C such that there is a proper edge-coloring of the complete graph K_n with C colors containing no two vertex-disjoint color-isomorphic copies, or repeats, of H? We study this function and its generalization 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-coloring of K_n with at most c n^2 colors contains two repeats of T, while there are colorings with at most c' n^(3/2) colors 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-coloring of K_n with at most c n colors containing no k repeats of H, while for a tree T with m edges, a coloring with o(n^((m+1)/m)) colors contains ω(1) repeats of T.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/21M1414103DOIArticle
https://arxiv.org/abs/2002.00921arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Alternate Title:Repeated patterns in proper colourings
Additional Information:© 2021 Society for Industrial and Applied Mathematics. Received by the editors April 21, 2021; accepted for publication (in revised form) July 1, 2021; published electronically September 28, 2021. The first author was supported by NSF award DMS-2054452. The second author was supported by ERC Synergy grant DYNASNET 810115, the H2020-MSCA-RISE project CoSP-GA 823748, and GACR grant 19-04113. We are extremely grateful to Sean English and Bob Krueger for spotting an error in an earlier version of this paper and suggesting a fix.
Funders:
Funding AgencyGrant Number
NSFDMS-2054452
European Research Council (ERC)810115
European Research Council (ERC)823748
Charles University19-04113
Subject Keywords:graphs, coloring, extremal problems
Issue or Number:3
Classification Code:AMS subject classification: 05C35
DOI:10.1137/21M1414103
Record Number:CaltechAUTHORS:20200914-134941914
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200914-134941914
Official Citation:Repeated Patterns in Proper Colorings. David Conlon and Mykhaylo Tyomkyn. SIAM Journal on Discrete Mathematics 2021 35:3, 2249-2264; DOI: 10.1137/21M1414103
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 Oct 2021 18:57

Repository Staff Only: item control page