On a Ramsey‐type problem of Erdős and Pach. Issue 6 (6th October 2017)

• Record Type: Journal Article
• Authors: Kang, Ross J.; Long, Eoin; Patel, Viresh; Regts, Guus
• Is Part Of: Bulletin of the London Mathematical Society. Volume 49:Issue 6(2017)
• Page Start: 991
• Page End: 999
• Publication Date: 2017-10-06
• Subjects: 05C55 (primary) -- 05D10 -- 05D40 (secondary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12094
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: We affirmatively answer a question of Erdős and Pach from 1983 by showing the following: there is some constant C > 0 such that for any graph G on C k ln k vertices either G or its complement G ¯ has an induced subgraph on k vertices with minimum degree at least 1 2 ( k − 1 ) .