Distinct degrees in induced subgraphs

Matthew Jenssen; Eoin Long; Peter Keevash; Liana Yepremyan

doi:10.1090/proc/15060

Distinct degrees in induced subgraphs

Matthew Jenssen, Eoin Long, Peter Keevash, Liana Yepremyan

Mathematics

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

1 Citation (Scopus)

188 Downloads (Pure)

Abstract

An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N-vertex graph is called C-Ramsey if it has no homogeneous set of size C logN. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree, and Sós, shows that any C-Ramsey N-vertex graph contains an induced subgraph with Ω_C(N^1/2) distinct degrees. We improve this to Ω_C(N^2/3), which is tight up to the constant factor. We also show that any N-vertex graph with N > (k-1)(n-1) and n ≥ n₀(k) = Ω(k⁹) either contains a homogeneous set of order n or an induced subgraph with k distinct degrees. The lower bound on N here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.

Original language	English
Pages (from-to)	3835-3846
Number of pages	12
Journal	Proceedings of the American Mathematical Society
Volume	148
Issue number	9
Early online date	22 May 2020
DOIs	https://doi.org/10.1090/proc/15060
Publication status	Published - Sept 2020

Keywords

Ramsey theory
Probabilistic methods
Induced subgraphs

ASJC Scopus subject areas

Applied Mathematics
Mathematics(all)

Access to Document

10.1090/proc/15060Licence: None: All rights reserved

JenssenM2020Distinct
First published in Proceedings of the American Mathematical Society in Volume 148, Number 9, September 2020, published by the American Mathematical Society. © 2020 American Mathematical Society.
Accepted author manuscript, 280 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Cite this

@article{97b27a9717f245b88924cf5978b9e24d,

title = "Distinct degrees in induced subgraphs",

abstract = "An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N-vertex graph is called C-Ramsey if it has no homogeneous set of size C logN. A theorem of Bukh and Sudakov, solving a conjecture of Erd{\H o}s, Faudree, and S{\'o}s, shows that any C-Ramsey N-vertex graph contains an induced subgraph with ΩC(N1/2) distinct degrees. We improve this to ΩC(N2/3), which is tight up to the constant factor. We also show that any N-vertex graph with N > (k-1)(n-1) and n ≥ n0(k) = Ω(k9) either contains a homogeneous set of order n or an induced subgraph with k distinct degrees. The lower bound on N here is sharp, as shown by an appropriate Tur{\'a}n graph, and confirms a conjecture of Narayanan and Tomon.",

keywords = "Ramsey theory, Probabilistic methods, Induced subgraphs",

author = "Matthew Jenssen and Eoin Long and Peter Keevash and Liana Yepremyan",

year = "2020",

month = sep,

doi = "10.1090/proc/15060",

language = "English",

volume = "148",

pages = "3835--3846",

journal = "Proceedings of the American Mathematical Society",

issn = "0002-9939",

publisher = "American Mathematical Society",

number = "9",

}

TY - JOUR

T1 - Distinct degrees in induced subgraphs

AU - Jenssen, Matthew

AU - Long, Eoin

AU - Keevash, Peter

AU - Yepremyan, Liana

PY - 2020/9

Y1 - 2020/9

N2 - An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N-vertex graph is called C-Ramsey if it has no homogeneous set of size C logN. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree, and Sós, shows that any C-Ramsey N-vertex graph contains an induced subgraph with ΩC(N1/2) distinct degrees. We improve this to ΩC(N2/3), which is tight up to the constant factor. We also show that any N-vertex graph with N > (k-1)(n-1) and n ≥ n0(k) = Ω(k9) either contains a homogeneous set of order n or an induced subgraph with k distinct degrees. The lower bound on N here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.

AB - An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N-vertex graph is called C-Ramsey if it has no homogeneous set of size C logN. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree, and Sós, shows that any C-Ramsey N-vertex graph contains an induced subgraph with ΩC(N1/2) distinct degrees. We improve this to ΩC(N2/3), which is tight up to the constant factor. We also show that any N-vertex graph with N > (k-1)(n-1) and n ≥ n0(k) = Ω(k9) either contains a homogeneous set of order n or an induced subgraph with k distinct degrees. The lower bound on N here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.

KW - Ramsey theory

KW - Probabilistic methods

KW - Induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85090518676&partnerID=8YFLogxK

U2 - 10.1090/proc/15060

DO - 10.1090/proc/15060

M3 - Article

SN - 0002-9939

VL - 148

SP - 3835

EP - 3846

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

IS - 9

ER -

Distinct degrees in induced subgraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this