


Combinatorics Seminar
Monday, 05th Feb. 4 pm
===================
Venue: meet.google.com/itehvpvoqy
Host: S. Krishnan
Speaker: Pranshu Gupta
Affiliation: University of Passau
Title: Minimal Ramsey graphs and the Erdős Rothschild problem
Abstract: In this talk, I will provide an overview of my research thus far. My main area of focus during my time as a doctoral candidate had
been the minimal Ramsey graphs. A graph G is said to be Ramsey for a graph H if, for any two colouring of the edges of G, there exists a monochromatic
copy of H. Determination of the smallest such clique for a graph H has been
a topic of intense research. A graph G is said to be minimal Ramsey if G
itself is Ramsey for H but no proper subgraph of it is Ramsey for H. In
1976, in their seminal paper, Burr, Erdős, and Lovász initiated a
systematic study of said graphs. One such popular problem has been the
determination of the minimum of the minimum degree among all minimal Ramsey graphs, for a given H. I will introduce this notion and summarize my
contributions to this field. I will follow this up with a discussion on one of my more recent works, with my colleagues Pehova, Powierski, and Staden,
on the Erdős Rothschild problem. The Erdős Rothschild problem from 1974 asks, given positive integers n,s, and k, what the maximum number of edge colourings, with s colours, an n vertex graph can have which avoids a monochromatic copy of clique of size k. We initiate a systematic study of the generalisation of this problem to a given forbidden family of colourings of cliques of size k.I will elaborate on the problem of forbidden triangles with exactly two colours. We solve this problem for all integers s ≥ 2 and large n and show in particular that every extremal graph is a Turán graph on an even number of parts; r is a solution to a certain optimisation
problem which grows with s. This extends the work of Hoppen, Lefmann and Schmidt who solved the cases s ≤ 26, in which case r is 2 and proves their conjecture for s=27.