The size-Ramsey number of powers of paths
cam.issuedOnline | 2018-12-02 | |
dc.contributor.author | Clemens, D | |
dc.contributor.author | Jenssen, M | |
dc.contributor.author | Kohayakawa, Y | |
dc.contributor.author | Morrison, N | |
dc.contributor.author | Mota, GO | |
dc.contributor.author | Reding, D | |
dc.contributor.author | Roberts, B | |
dc.contributor.orcid | Kohayakawa, Y [0000-0001-7841-157X] | |
dc.contributor.orcid | Mota, GO [0000-0001-9722-1819] | |
dc.date.accessioned | 2018-12-22T00:30:29Z | |
dc.date.available | 2018-12-22T00:30:29Z | |
dc.date.issued | 2019 | |
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.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). | |
dc.identifier.doi | 10.17863/CAM.34672 | |
dc.identifier.eissn | 1097-0118 | |
dc.identifier.issn | 0364-9024 | |
dc.identifier.uri | https://www.repository.cam.ac.uk/handle/1810/287368 | |
dc.language.iso | eng | |
dc.publisher | Wiley | |
dc.publisher.url | http://dx.doi.org/10.1002/jgt.22432 | |
dc.subject | powers of paths | |
dc.subject | Ramsey | |
dc.subject | size-Ramsey | |
dc.title | The size-Ramsey number of powers of paths | |
dc.type | Article | |
dcterms.dateAccepted | 2018-08-18 | |
prism.endingPage | 299 | |
prism.issueIdentifier | 3 | |
prism.publicationDate | 2019 | |
prism.publicationName | Journal of Graph Theory | |
prism.startingPage | 290 | |
prism.volume | 91 | |
rioxxterms.licenseref.startdate | 2019-07-01 | |
rioxxterms.licenseref.uri | http://www.rioxx.net/licenses/all-rights-reserved | |
rioxxterms.type | Journal Article/Review | |
rioxxterms.version | AM | |
rioxxterms.versionofrecord | 10.1002/jgt.22432 |
Files
Original bundle
1 - 1 of 1
Loading...
- 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
1 - 1 of 1
No Thumbnail Available
- Name:
- DepositLicenceAgreementv2.1.pdf
- Size:
- 150.9 KB
- Format:
- Adobe Portable Document Format