On a Ramsey-type problem of Erdős and Pach

DOI10.1112/BLMS.12094MaRDI QIDQ4601481zbMATH OpenOpenAlexFDO

Authors Ross J. Kang, Eoin Long, Viresh Patel, Guus Regts

Publication date 16 January 2018

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4459, http://pure-oai.bham.ac.uk/ws/files/75179888/erdospach2016revised.pdf

zbMATH Keywords

minimum degreesubgraphcomplement of graph

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper we show that there exists a constant $C>0$ such that for any graph $G$ on $Cklnk$ vertices either $G$ or its complement $$ has an induced subgraph on $k$ vertices with minimum degree at least $frac12(k-1)$. This affirmatively answers a question of ErdH{o}s and Pach from 1983.

Recommendations

• On a Ramsey-type problem of Erdős and Pach
• On a Ramsey-Turán type problem
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• scientific article; zbMATH DE number 4213982
• On a Ramsey type theorem
• The Ramsey-type version of a problem of Pomerance and Schinzel
• scientific article; zbMATH DE number 4177114
• On a Question of Erdös and Faudree on the Size Ramsey Numbers
• A conjecture of Erdős on graph Ramsey numbers
• On some problems of Euclidean Ramsey theory

Cited in

(13)

• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Distinct degrees and homogeneous sets
• A conjecture of Erdős on graph Ramsey numbers
• Ramsey type results on the solvability of certain equation in \(\mathbb Z_m\)
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• On a Ramsey-type problem of Erdős and Pach
• On a Question of Erdös and Faudree on the Size Ramsey Numbers
• The Erdős-Szekeres problem and an induced Ramsey question
• scientific article; zbMATH DE number 970803 (Why is no real title available?)
• scientific article; zbMATH DE number 1735672 (Why is no real title available?)
• A precise threshold for quasi-Ramsey numbers
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• On a Ramsey-Turán type problem

This page was built for publication: On a Ramsey-type problem of Erdős and Pach

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