Repeated Patterns in Proper Colorings
- Creators
- Conlon, David
- Tyomkyn, Mykhaylo
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.
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.Attached Files
Published - 21m1414103.pdf
Submitted - 2002.00921.pdf
Files
Name | Size | Download all |
---|---|---|
md5:ceb6365947971db6a3c3c3ba711d1d02
|
377.9 kB | Preview Download |
md5:f5f3209361d600b523c5404e6dca3b59
|
208.5 kB | Preview Download |
Additional details
- Alternative title
- Repeated patterns in proper colourings
- Eprint ID
- 105380
- Resolver ID
- CaltechAUTHORS:20200914-134941914
- NSF
- DMS-2054452
- European Research Council (ERC)
- 810115
- European Research Council (ERC)
- 823748
- Charles University
- 19-04113
- Created
-
2020-09-14Created from EPrint's datestamp field
- Updated
-
2021-10-14Created from EPrint's last_modified field