Seminar series
Date
Tue, 14 Oct 2025
Time
14:00 -
15:00
Location
L4
Speaker
Marcelo Campos
Organisation
Instituto Nacional de Matemática Pura e Aplicada (IMPA)
The induced Ramsey number $R_{ind}(H)$ of a graph $H$ is the minimum number $N$ such that there exists a graph with $N$ vertices for which all red/blue colorings of its edges contain a monochromatic induced copy of $H$. In this talk I'll show there exists an absolute constant $C > 0$ such that, for every graph $H$ on $k$ vertices, these numbers satisfy $R_{ind}(H) ≤ 2^{Ck}$. This resolves a conjecture of Erdős from 1975.
This is joint work with Lucas Aragão, Gabriel Dahia, Rafael Filipe and João Marciano.