The minimum degree of minimal Ramsey graphs for cliques

John Bamberg; Anurag Bishnoi; Thomas Lesgourgues

doi:10.1112/blms.12658

The minimum degree of minimal Ramsey graphs for cliques

John Bamberg, Anurag Bishnoi^*, Thomas Lesgourgues

^*Corresponding author for this work

Discrete Mathematics and Optimization

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

1 Citation (Scopus)

128 Downloads (Pure)

Abstract

We prove that (Formula presented.), where (Formula presented.) is the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph (Formula presented.) such that any (Formula presented.) -colouring of the edges of (Formula presented.) contains a monochromatic (Formula presented.), whereas no proper subgraph of (Formula presented.) has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

Original language	English
Pages (from-to)	1827-1838
Number of pages	12
Journal	Bulletin of the London Mathematical Society
Volume	54
Issue number	5
DOIs	https://doi.org/10.1112/blms.12658
Publication status	Published - 2022

Access to Document

10.1112/blms.12658

Bulletin of London Math Soc - 2022 - Bamberg - The minimum degree of minimal Ramsey graphs for cliquesFinal published version, 148 KBLicence: CC BY-NC

Cite this

@article{34434e829953477683a8c7938ae5a84f,

title = "The minimum degree of minimal Ramsey graphs for cliques",

abstract = "We prove that (Formula presented.), where (Formula presented.) is the Ramsey parameter introduced by Burr, Erd{\H o}s and Lov{\'a}sz in 1976, which is defined as the smallest minimum degree of a graph (Formula presented.) such that any (Formula presented.) -colouring of the edges of (Formula presented.) contains a monochromatic (Formula presented.), whereas no proper subgraph of (Formula presented.) has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.",

author = "John Bamberg and Anurag Bishnoi and Thomas Lesgourgues",

year = "2022",

doi = "10.1112/blms.12658",

language = "English",

volume = "54",

pages = "1827--1838",

journal = "Bulletin of the London Mathematical Society",

issn = "0024-6093",

publisher = "Oxford University Press",

number = "5",

}

TY - JOUR

T1 - The minimum degree of minimal Ramsey graphs for cliques

AU - Bamberg, John

AU - Bishnoi, Anurag

AU - Lesgourgues, Thomas

PY - 2022

Y1 - 2022

N2 - We prove that (Formula presented.), where (Formula presented.) is the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph (Formula presented.) such that any (Formula presented.) -colouring of the edges of (Formula presented.) contains a monochromatic (Formula presented.), whereas no proper subgraph of (Formula presented.) has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

AB - We prove that (Formula presented.), where (Formula presented.) is the Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is defined as the smallest minimum degree of a graph (Formula presented.) such that any (Formula presented.) -colouring of the edges of (Formula presented.) contains a monochromatic (Formula presented.), whereas no proper subgraph of (Formula presented.) has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

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

U2 - 10.1112/blms.12658

DO - 10.1112/blms.12658

M3 - Article

AN - SCOPUS:85128177907

SN - 0024-6093

VL - 54

SP - 1827

EP - 1838

JO - Bulletin of the London Mathematical Society

JF - Bulletin of the London Mathematical Society

IS - 5

ER -

The minimum degree of minimal Ramsey graphs for cliques

Abstract

Access to Document

Other files and links

Fingerprint

Cite this