On a Ramsey‐type problem of Erdős and Pach. Issue 6 (6th October 2017) - Kang, Ross J.; Long, Eoin; Patel, Viresh; Regts, Guus
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 ) .