Jan Volec
(Czech Technical University in Prague)

Jan Volec (Czech Technical University in Prague)

On the minimum eigenvalue of regular triangle-free graphs.

Abstract: Motivated by two well-known conjectures of Erdős on triangle-free graphs, Brandt asked in 1994 whether the smallest eignvalue of an n-vertex d-regular triangle-free graph is at most 4n/25 - d. In this talk, we confirm the conjecture of Brandt in a stonger sense: we show that the smallest eigenvalue of the signless Laplacian of any n-vertex triangle-free graph G is at most 15n/94 < 0.1596n. In particular, if G is d-regular, then its smallest eigenvalue is at most 15n/94 - d.
This is a joint work with Jozsi Balogh, Felix Clemen, Bernard Lidický and Sergey Norin.

Yamaan Attwa (FU Berlin)

Erdős-Hajnal is true for an infinite family of prime graphs.

Abstract: We say that a graph H has the Erdős-Hajnal property if there exists some ε = ε(H)>0 such that every H-free graph G has a homogeneous set of size at least |G|^ε. Erdős and Hajnal conjectured that every graph H has the EH-property. The conjecture is known to be true for the set F of graphs on at most 5 vertices except P₅ and its complement. Alon, Pach and Solymosi proved that if H₁ and H₂ have the EH-property then H constructed by substituting H₁ into a vertex of H₂ also has the EH-property. Until recently, our knowledge of graphs with the EH-property was limited to the smallest family C of graphs containing F and is closed under substitutions. This talk is an exposition of a paper by Nguyen, Scott and Seymour proving for every n ≥ 4 the existence of a graph G_n on n vertices having the EH-property and is unconstructible from smaller graphs by vertex substitutions.