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
Room 005 (Ground Floor)