Induced Ramsey-type theorems

DOI10.1016/J.ENDM.2007.07.010MaRDI QIDQ5900068zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Benny Sudakov

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0706.4112

zbMATH Keywords

forbidden induced subgraphinduced Ramsey numberRamsey theory

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Ramsey theory (05D10)

Abstract: We 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.

Recommendations

• Induced Ramsey-type theorems
• On two problems in graph Ramsey theory
• Induced Ramsey numbers
• scientific article; zbMATH DE number 2197902
• scientific article; zbMATH DE number 3863243

Cites work

• Edge Distribution of Graphs with Few Copies of a Given Graph
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 2197902 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Induced Ramsey numbers
• Non-Ramsey graphs are c n-universal
• On a Ramsey type theorem
• On induced Ramsey numbers for graphs with bounded maximum degree
• On universality of graphs with uniformly distributed edges
• Pseudo-random graphs
• Ramsey-type theorems
• Some remarks on the theory of graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(9)

• Induced restricted Ramsey theorems for spaces
• Some Ramsey-type theorems
• Indicators, chains, antichains, Ramsey property
• On two problems in graph Ramsey theory
• Induced Ramsey-type theorems
• Class Ramsey numbers involving induced graphs
• Symmetrized induced Ramsey theory
• A note on the induced Ramsey theorem for spaces
• A short proof of the induced Ramsey theorem for hypergraphs

This page was built for publication: Induced Ramsey-type theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900068)