• This event has passed.

# Paul Seymour, A loglog step towards the Erdős-Hajnal conjecture

## March 16 Thursday @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)

### Speaker

Paul Seymour
Department of Mathematics, Princeton University
https://www.math.princeton.edu/~pds/

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$.

There has no improvement on this result (for general $H$) until now, but now we have an improvement: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ This talk will outline the proof.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

## Details

Date:
March 16 Thursday
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

## Venue

Zoom ID: 869 4632 6610 (ibsdimag)

## Organizer

O-joung Kwon (권오정)
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209