Show simple item record

dc.contributor.author
Pokrovskiy, Alexey
dc.contributor.author
Sudakov, Benny
dc.date.accessioned
2020-10-23T09:30:50Z
dc.date.available
2020-10-23T02:44:52Z
dc.date.available
2020-10-23T09:30:50Z
dc.date.issued
2020
dc.identifier.issn
0895-4801
dc.identifier.issn
1095-7146
dc.identifier.other
10.1137/18M1199125
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/447376
dc.description.abstract
Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red-blue coloring of the edges of the complete graph K-N contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) >= (vertical bar G vertical bar - 1) (chi(H) - 1) + sigma(H), where chi(H) is the chromatic number of H and sigma(H) is the size of the smallest color class in a chi(H)-coloring of H. A graph G is called H-good if R(G, H) = (vertical bar G vertical bar - 1) (chi(H) - 1) + sigma(H). The notion of Ramsey goodness was introduced by Burr and Erdos in 1983 and has been extensively studied since then. In this paper we show that if n >= 10(60)vertical bar H vertical bar and sigma(H) >= chi(H)(22), then the n-vertex cycle C-n is H-good. For graphs H with high chi(H) and sigma(H), this proves in a strong form a conjecture of Allen, Brightwell, and Skokan. © 2020 Society for Industrial and Applied Mathematics.
en_US
dc.language.iso
en
en_US
dc.publisher
SIAM
en_US
dc.subject
Ramsey theory
en_US
dc.subject
Cycles
en_US
dc.subject
Expanders
en_US
dc.title
Ramsey Goodness of Cycles
en_US
dc.type
Journal Article
dc.date.published
2020-09-01
ethz.journal.title
SIAM Journal on Discrete Mathematics
ethz.journal.volume
34
en_US
ethz.journal.issue
3
en_US
ethz.journal.abbreviated
SIAM j. discrete math.
ethz.pages.start
1884
en_US
ethz.pages.end
1908
en_US
ethz.grant
Extremal problems in combinatorics
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Philadelphia, PA
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.grant.agreementno
175573
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2020-10-23T02:45:04Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-10-23T09:31:02Z
ethz.rosetta.lastUpdated
2022-03-29T03:38:36Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Ramsey%20Goodness%20of%20Cycles&rft.jtitle=SIAM%20Journal%20on%20Discrete%20Mathematics&rft.date=2020&rft.volume=34&rft.issue=3&rft.spage=1884&rft.epage=1908&rft.issn=0895-4801&1095-7146&rft.au=Pokrovskiy,%20Alexey&Sudakov,%20Benny&rft.genre=article&rft_id=info:doi/10.1137/18M1199125&
 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