Page 281 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 281
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
matching this bound.
We prove several new results in this area. First, we obtain an optimal bound when H is an
odd cycle, adding to the lacunary list of graphs for which such a result is known. Secondly, we
extend the result of Alon in the sense that we prove optimal bounds on the surplus of general
graphs in terms of the number of triangles they contain. Thirdly, we improve the currently best
bounds for Kr-free graphs.
Our proofs combine techniques from semidefinite programming, probabilistic reasoning, as
well as combinatorial and spectral arguments.
How does the chromatic number of a random graph vary?
Annika Heckel, annikaheckel@gmail.com
LMU Munich, Germany
If we pick an n-vertex graph uniformly at random, how much does its chromatic number vary?
In 1987 Shamir and Spencer proved that it is contained in some sequence of intervals of length
about n1/2. Alon improved this slightly to n1/2/ log n. Until recently, however, no non-trivial
lower bounds on the fluctuations of the chromatic number of a random graph were known, even
though the question was raised by Bollobás many years ago. We will present the main ideas
needed to prove that, at least for infinitely many values n, the chromatic number of a uniform
n-vertex graph is not concentrated on fewer than n1/2−o(1) consecutive values.
We will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris,
Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length
’zigzags’ between n1/4+o(1) and n1/2+o(1), depending on n.
Joint work with Oliver Riordan.
On graph norms
Jan Hladky, hladky@cs.cas.cz
Institute of Computer Science of the Czech Academy of Sciences, Czech Republic
The concept of graph norms, introduced by Hatami in 2010 (following suggestions from Lovász
and Szegedy), is a convenient tool to work with subgraph densities. The definition is real-
analytic, making use of the framework of graphons. I will describe several results obtained
by in collaboration with Doležal-Grebík-Rocha-Rozhonˇ and Garbe-Lee. This in particular in-
cludes a characterization norming graphs (and alike) using the ‘step-Sidorenko’ property and a
characterization of disconnected norming graphs.
Extremal density for sparse minors and subdivisions
Jaehoon Kim, jaehoon.kim@kaist.ac.kr
KAIST, Republic of Korea
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of
bounded-degree bipartite graphs with a mild separability condition. As corollaries, we prove
that: (1 + o(1))t2 average degree is sufficient to force the t × t grid as a topological minor;
279
matching this bound.
We prove several new results in this area. First, we obtain an optimal bound when H is an
odd cycle, adding to the lacunary list of graphs for which such a result is known. Secondly, we
extend the result of Alon in the sense that we prove optimal bounds on the surplus of general
graphs in terms of the number of triangles they contain. Thirdly, we improve the currently best
bounds for Kr-free graphs.
Our proofs combine techniques from semidefinite programming, probabilistic reasoning, as
well as combinatorial and spectral arguments.
How does the chromatic number of a random graph vary?
Annika Heckel, annikaheckel@gmail.com
LMU Munich, Germany
If we pick an n-vertex graph uniformly at random, how much does its chromatic number vary?
In 1987 Shamir and Spencer proved that it is contained in some sequence of intervals of length
about n1/2. Alon improved this slightly to n1/2/ log n. Until recently, however, no non-trivial
lower bounds on the fluctuations of the chromatic number of a random graph were known, even
though the question was raised by Bollobás many years ago. We will present the main ideas
needed to prove that, at least for infinitely many values n, the chromatic number of a uniform
n-vertex graph is not concentrated on fewer than n1/2−o(1) consecutive values.
We will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris,
Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length
’zigzags’ between n1/4+o(1) and n1/2+o(1), depending on n.
Joint work with Oliver Riordan.
On graph norms
Jan Hladky, hladky@cs.cas.cz
Institute of Computer Science of the Czech Academy of Sciences, Czech Republic
The concept of graph norms, introduced by Hatami in 2010 (following suggestions from Lovász
and Szegedy), is a convenient tool to work with subgraph densities. The definition is real-
analytic, making use of the framework of graphons. I will describe several results obtained
by in collaboration with Doležal-Grebík-Rocha-Rozhonˇ and Garbe-Lee. This in particular in-
cludes a characterization norming graphs (and alike) using the ‘step-Sidorenko’ property and a
characterization of disconnected norming graphs.
Extremal density for sparse minors and subdivisions
Jaehoon Kim, jaehoon.kim@kaist.ac.kr
KAIST, Republic of Korea
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of
bounded-degree bipartite graphs with a mild separability condition. As corollaries, we prove
that: (1 + o(1))t2 average degree is sufficient to force the t × t grid as a topological minor;
279
