Combinatorics Seminar

Monday, 05th Feb. 4 pm

===================

Venue: meet.google.com/ite-hvpv-oqy

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.