PIMS - SFU Discrete Math Seminar: Anurag Bishnoi

  • Date: 07/28/2021
  • Time: 10:30
Anurag Bishnoi, TU Delft



The Minimum Degree of Minimal Ramsey Graphs for Cliques


Abstract: In this talk we will present a new upper bound of $s_r(K_t) = O(t^5r^{5/2})$ on the Ramsey parameter $s_r(K_t)$ introduced by Burr, Erd\H{o}s and Lov\'{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r-colouring of the edges of $G$ contains a monochromatic $K_t$, whereas no proper subgraph of $G$ has this property. This improves the previous upper bound of $s_r(K_t) = O(t^6r^3)$ proved by Fox et al. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.


This is joint work with John Bamberg and Thomas Lesgourgues (https://arxiv.org/abs/2008.02474).