Repository logo
 

The size-Ramsey number of powers of paths

cam.issuedOnline2018-12-02
dc.contributor.authorClemens, D
dc.contributor.authorJenssen, M
dc.contributor.authorKohayakawa, Y
dc.contributor.authorMorrison, N
dc.contributor.authorMota, GO
dc.contributor.authorReding, D
dc.contributor.authorRoberts, B
dc.contributor.orcidKohayakawa, Y [0000-0001-7841-157X]
dc.contributor.orcidMota, GO [0000-0001-9722-1819]
dc.date.accessioned2018-12-22T00:30:29Z
dc.date.available2018-12-22T00:30:29Z
dc.date.issued2019
dc.description.abstract<jats:title>Abstract</jats:title><jats:p>Given 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:italic>is</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:italic>Ramsey 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:italic>size‐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>
dc.description.sponsorshipMost 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).
dc.identifier.doi10.17863/CAM.34672
dc.identifier.eissn1097-0118
dc.identifier.issn0364-9024
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/287368
dc.language.isoeng
dc.publisherWiley
dc.publisher.urlhttp://dx.doi.org/10.1002/jgt.22432
dc.subjectpowers of paths
dc.subjectRamsey
dc.subjectsize-Ramsey
dc.titleThe size-Ramsey number of powers of paths
dc.typeArticle
dcterms.dateAccepted2018-08-18
prism.endingPage299
prism.issueIdentifier3
prism.publicationDate2019
prism.publicationNameJournal of Graph Theory
prism.startingPage290
prism.volume91
rioxxterms.licenseref.startdate2019-07-01
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserved
rioxxterms.typeJournal Article/Review
rioxxterms.versionAM
rioxxterms.versionofrecord10.1002/jgt.22432

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
sizeRamsey.pdf
Size:
431.07 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Licence
http://www.rioxx.net/licenses/all-rights-reserved
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DepositLicenceAgreementv2.1.pdf
Size:
150.9 KB
Format:
Adobe Portable Document Format