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

Ross Kang; Eoin Long; Viresh Patel; Guus Regts

doi:10.1112/blms.12094

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

Ross Kang, Eoin Long, Viresh Patel, Guus Regts

Mathematics

Research output: Contribution to journal › Article › peer-review

205 Downloads (Pure)

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 G¯ has an induced subgraph on k vertices with minimum degree at least ½(k−1). This affirmatively answers a question of Erdős and Pach from 1983.

Original language	English
Pages (from-to)	991-999
Number of pages	9
Journal	Bulletin of the London Mathematical Society
Volume	49
Issue number	6
Early online date	6 Oct 2017
DOIs	https://doi.org/10.1112/blms.12094
Publication status	Published - 1 Dec 2017

Keywords

05C55 (primary)
05D10
05D40 (secondary)

Access to Document

10.1112/blms.12094Licence: None: All rights reserved

Kang_et_al_On_a_Ramsey_type_problem_of_Erdős_and_Pach_Bulletin_of_the_London_Mathematical_Society_2017
Checked for eligibility: 05/09/2019 This document is the Author Accepted Manuscript version of a published work, Kang, R. J., Long, E. , Patel, V. and Regts, G. (2017), On a Ramsey‐type problem of Erdős and Pach. Bull. London Math. Soc., 49: 991-999. doi:10.1112/blms.12094 which appears in its final form at: https://doi.org/10.1112/blms.12094 copyright © 2017 London Mathematical Society.
Accepted author manuscript, 201 KBLicence: None: All rights reserved

Cite this

@article{2d7106275efa41efbf73b44163bbac08,

title = "On a Ramsey-type problem of Erd{\H o}s and Pach",

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 G¯ has an induced subgraph on k vertices with minimum degree at least ½(k−1). This affirmatively answers a question of Erd{\H o}s and Pach from 1983.",

keywords = "05C55 (primary), 05D10, 05D40 (secondary)",

author = "Ross Kang and Eoin Long and Viresh Patel and Guus Regts",

year = "2017",

month = dec,

day = "1",

doi = "10.1112/blms.12094",

language = "English",

volume = "49",

pages = "991--999",

journal = "Bulletin of the London Mathematical Society",

issn = "0024-6093",

publisher = "London Mathematical Society",

number = "6",

}

TY - JOUR

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

AU - Kang, Ross

AU - Long, Eoin

AU - Patel, Viresh

AU - Regts, Guus

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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 G¯ has an induced subgraph on k vertices with minimum degree at least ½(k−1). This affirmatively answers a question of Erdős and Pach from 1983.

AB - 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 G¯ has an induced subgraph on k vertices with minimum degree at least ½(k−1). This affirmatively answers a question of Erdős and Pach from 1983.

KW - 05C55 (primary)

KW - 05D10

KW - 05D40 (secondary)

U2 - 10.1112/blms.12094

DO - 10.1112/blms.12094

M3 - Article

SN - 0024-6093

VL - 49

SP - 991

EP - 999

JO - Bulletin of the London Mathematical Society

JF - Bulletin of the London Mathematical Society

IS - 6

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this