Show simple item record

dc.contributor.author
Draganić, Nemanja
dc.contributor.author
Krivelevich, Michael
dc.contributor.author
Nenadov, Rajko
dc.date.accessioned
2021-06-16T20:15:29Z
dc.date.available
2021-01-27T06:16:28Z
dc.date.available
2021-01-27T17:26:31Z
dc.date.available
2021-06-16T20:15:29Z
dc.date.issued
2021-08
dc.identifier.issn
1042-9832
dc.identifier.issn
1098-2418
dc.identifier.other
10.1002/rsa.20995
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/465804
dc.description.abstract
The r-size-Ramsey number (R) over cap (r)(H) of a graph H is the smallest number of edges a graph G can have such that for every edge-coloring of G with r colors there exists a monochromatic copy of H in G. For a graph H, we denote by H-q the graph obtained from H by subdividing its edges with q - 1 vertices each. In a recent paper of Kohayakawa, Retter and Rodl, it is shown that for all constant integers q, r >= 2 and every graph H on n vertices and of bounded maximum degree, the r-size-Ramsey number of H-q is at most (log n)(20(q-1))n(1+1/q), for n large enough. We improve upon this result using a significantly shorter argument by showing that (R) over cap (r)(H-q) <= O(n(1+1/q)) for any such graph H.
en_US
dc.language.iso
en
en_US
dc.publisher
Wiley
en_US
dc.subject
Ramsey theory
en_US
dc.subject
random graphs
en_US
dc.subject
subdivisions
en_US
dc.title
The size‐Ramsey number of short subdivisions
en_US
dc.type
Journal Article
dc.date.published
2021-01-11
ethz.journal.title
Random Structures & Algorithms
ethz.journal.volume
59
en_US
ethz.journal.issue
1
en_US
ethz.journal.abbreviated
Random struct. algorithms
ethz.pages.start
68
en_US
ethz.pages.end
78
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2021-01-27T06:16:32Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-06-16T20:15:37Z
ethz.rosetta.lastUpdated
2021-06-16T20:15:37Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=The%20size%E2%80%90Ramsey%20number%20of%20short%20subdivisions&amp;rft.jtitle=Random%20Structures%20&%20Algorithms&amp;rft.date=2021-08&amp;rft.volume=59&amp;rft.issue=1&amp;rft.spage=68&amp;rft.epage=78&amp;rft.issn=1042-9832&amp;1098-2418&amp;rft.au=Dragani%C4%87,%20Nemanja&amp;Krivelevich,%20Michael&amp;Nenadov,%20Rajko&amp;rft.genre=article&amp;rft_id=info:doi/10.1002/rsa.20995&amp;
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record