Title: Chromatic structure in locally sparse graphs
| Speaker: | Ross Kang |
| Affiliation: | Radboud University Nijmegen |
| Zoom: | Please email Emma Watson |
Abstract:
Efforts
to
understand
the
structure
of
triangle-free
graphs
have
long
played
a
central
role
in
the
development
of
combinatorial
mathematics.
Classic
results
of
Mantel
(1907),
Ramsey
(1930),
Blanche
Descartes
(1948)
produce
global
structure
from
the
local
property
of
having
no
edges
in
any
neighbourhood.
Despite
the
scrutiny
it
has
sustained
over
the
decades,
study
of
this
topic,
and
its
close
relatives,
continues
to
uncover
surprisingly
basic
challenges,
insights
and
connections.
I
will
give
a
brief
overview
of
the
history
as
well
as
the
focus
of
current/recent
momentum.
I
will
also
highlight
a
recent,
general
framework
for
producing
global
structure
from
local
structure.
This
generalises
and
strengthens
a
swathe
of
important
results
in
the
area,
including
those
of
Ajtai,
Komlós,
Szemerédi
(1981),
Shearer
(1983/1996),
Johansson
(1996),
Alon
(1996),
Alon,
Krivelevich,
Sudakov
(1999),
Bansal,
Gupta,
Guruganesh
(2018),
Bonamy,
Kelly,
Nelson,
Postle
(2018),
Molloy
(2019),
Bernshteyn
(2019),
and
Achlioptas,
Iliopoulos,
Sinclair
(2019).
The
framework
is
built
around
a
technique
inspired
by
statistical
physics
–namely,
a
local
analysis
of
the
hard-core
model–
combined
with
the
suitable
application
of
the
Lovász
local
lemma.
This
is
joint
work
with
Ewan
Davies,
Rémi
de
Joannis
de
Verclos,
François
Pirot,
Jean-Sébastien
Sereni.