Springe direkt zu Inhalt

2023/2024

Talks normally take place Wednesdays or Thursdays.

DateSpeakerTitle
17.11.2023

Jan Volec
(Czech Technical University in Prague)

On the minimum eigenvalue of regular triangle-free graphs.
02.11.2023 Yamaan Attwa
(FU Berlin)
Erdős-Hajnal is true for an infinite family of prime graphs. Part II
26.10.2023 Yamaan Attwa
(FU Berlin)
Erdős-Hajnal is true for an infinite family of prime graphs. Part I
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.