Induced Ramsey-type theorems

Simple item page
dc.creatorFox, Jacob
dc.creatorSudakov, Benny
dc.date2007-06-27
dc.date2007-12-27
dc.date.accessioned2026-07-07T08:51:02Z
dc.date.available2026-07-07T08:51:02Z
dc.descriptionWe present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rodl, Erdos-Hajnal, Promel-Rodl, Nikiforov, Chung-Graham, and Luczak-Rodl. The proofs are based on a simple lemma (generalizing one by Graham, Rodl, and Rucinski) that can be used as a replacement for Szemeredi's regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.
dc.description30 pages
dc.identifierhttps://arxiv.org/abs/0706.4112
dc.identifierhttp://arxiv.org/abs/0706.4112
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/144800
dc.subjectCombinatorics
dc.subject05D10; 05C55
dc.titleInduced Ramsey-type theorems
dc.typetext

Files

Collections

arXiv