Talks normally take place Wednesdays or Thursdays.
17.11.2023 |
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.
|
26.10.2023 and 02.11.2023 |
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 P5 and its complement. Alon, Pach and Solymosi proved that if H1 and H2 have the EH-property then H constructed by substituting H1 into a vertex of H2 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 Gn on n vertices having the EH-property and is unconstructible from smaller graphs by vertex substitutions.
|