Springe direkt zu Inhalt

Research Seminar Combinatorics

Next Talk

Thursday, November 17th, 2023 at 14:15
A3 SR024

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.

Schedule and abstracts 2023/2024

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.

Links

Mailing list:

To subscribe to the mailing-list of the seminar, please follow this link:
https://lists.fu-berlin.de/listinfo/combinatorics-seminar

Notes:

For any request, please send an e-mail to:
combinatorics-seminar-owner@lists.fu-berlin.de

Archives

Schedule and abstracts 2023/2024

Schedule and abstracts 2022/2023

Schedule and abstracts 2021/2022

Schedule and abstracts 2020/2021

Schedule and abstracts 2019/2020

Schedule and abstracts 2018/2019

Schedule and abstracts 2017/2018

Schedule and abstracts 2016/2017

Schedule and abstracts 2015/2016

Schedule and abstracts 2014/2015

Schedule and abstracts 2013/2014

Schedule and abstracts 2012/2013

Schedule and abstracts 2011/2012

Schedule and abstracts 2010/2011

Schedule and abstracts 2009/2010