The size-Ramsey number of powers of paths
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
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>
Description
Keywords
Journal Title
Conference Name
Journal ISSN
1097-0118