The minimum degree of minimal Ramsey graphs for cliques

Journal article (2022)

Authors

John Bamberg University of Western Australia
A. Bishnoi Discrete Mathematics and Optimization - EEMCS
Thomas Lesgourgues University of New South Wales
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2022 John Bamberg, A. Bishnoi, Thomas Lesgourgues
DOI
help_outline
https://doi.org/10.1112/blms.12658
More Info
expand_more

Published Date

2022

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.