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

DOI10.1112/BLMS.12094zbMATH Open1378.05126arXiv1411.4459OpenAlexW3121546727MaRDI QIDQ4601481FDOQ4601481

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

Publication date: 16 January 2018

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

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.

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

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
• 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

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)

Cited In (11)

• Distinct degrees and homogeneous sets
• Title not available (Why is that?)
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• On a Question of Erdös and Faudree on the Size Ramsey Numbers
• On a Ramsey-type problem of Erdős and Pach
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• On a Ramsey-Turán type problem
• A conjecture of Erdős on graph Ramsey numbers
• Ramsey type results on the solvability of certain equation in \(\mathbb Z_m\)
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• Title not available (Why is that?)

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)