# Colloquium by Simona Boyadzhiyska (Freie Universität Berlin): Ramsey simplicity of random graphs

We say that a graph G is *q-Ramsey* for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the *q-color Ramsey number of H*. In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree.

A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) >= q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple.

This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

### Time & Location

Oct 25, 2021 | 04:00 PM s.t.

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)