The size-Ramsey number of powers of paths

jats:titleAbstract</jats:title>jats:pGiven graphs <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0001.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0001" /> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0002.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0002" /> and a positive integer <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0003.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0003" />, say that <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0004.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0004" /> jats:italicis</jats:italic> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0005.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0005" />‐jats:italicRamsey for</jats:italic> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0006.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0006" />, denoted <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0007.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0007" />, if every <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0008.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0008" />‐coloring of the edges of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0009.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0009" /> contains a monochromatic copy of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0010.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0010" />. The jats:italicsize‐Ramsey number</jats:italic> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0011.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0011" /> of a graph <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0012.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0012" /> is defined to be <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0013.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0013" />. Answering a question of Conlon, we prove that, for every fixed <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0014.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0014" />, we have <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0015.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0015" />, where <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0016.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0016" /> is the <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0017.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0017" />th power of the <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0018.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0018" />‐vertex path <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0019.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0019" /> (ie, the graph with vertex set <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0020.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0020" /> and all edges <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0021.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0021" /> such that the distance between <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0022.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0022" /> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0023.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0023" /> in <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0024.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0024" /> is at most <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt22432-math-0025.png" xlink:title="urn:x-wiley:03649024:media:jgt22432:jgt22432-math-0025" />). Our proof is probabilistic, but can also be made constructive.</jats:p>

Keywords

powers of paths, Ramsey, size-Ramsey

Journal Title

Journal of Graph Theory

Journal ISSN

0364-9024
1097-0118

Volume Title

91

Publisher

Wiley

Publisher DOI

https://doi.org/10.1002/jgt.22432

Rights

http://www.rioxx.net/licenses/all-rights-reserved

Sponsorship

Most of the work for this paper was done during my PhD, which was half funded by EPSRC grant reference 1360036, and half by Merton College Oxford. The third author was partially supported by FAPESP (Proc.~2013/03447-6) and by CNPq (Proc.~459335/2014-6, 310974/2013-5). The fifth author was supported by FAPESP (Proc.~2013/11431-2, Proc.~2013/03447-6 and Proc.~2018/04876-1) and partially by CNPq (Proc.~459335/2014-6). This research was supported in part by CAPES (Finance Code 001). The collaboration of part of the authors was supported by a CAPES/DAAD PROBRAL grant (Proc.~430/15).

Collections

Cambridge University Research Outputs