Page 282 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 282
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
(3/2 + o(1))t average degree forces every t-vertex planar graph as a minor, and the constant
3/2 is optimal; a universal bound of (2 + o(1))t on average degree forcing every t-vertex graph
in any nontrivial minor-closed family as a minor, and the constant 2 is best possible. This is
joint work with John Haslegrave and Hong Liu.
Progress on intersecting families
Andrey Kupavskii, kupavskii@ya.ru
Moscow Institute of Physics and Technology, Russian Federation, and G-SCOP, CNRS, France
We say that a family of sets is intersecting, if any two of its sets intersect. The Erdos-Ko-Rado
theorem characterizes the largest intersecting families of k-element subets of an n-element set,
and a lot of studies have been devoted to the following vague question: what structure could a
family have, given that it has size close to extremal? This question has many possible answers,
depending on the structure we look for, and I am going to discuss several of them during my
talk. These will include junta approximations, diversity and covering number.
Such structural results have implications for other related problems, and I will cover at least
one such application to the colorings of Kneser graphs. Recall that a Kneser graph is a graph on
the collection of all k-element subsets of an n-element set, with two sets connected by an edge
when they are disjoint. One of the famous results of Lovász is the topological proof that such
graph has chromatic number n − 2k + 2. We discuss the following problem: for which values
of n = n(k) we can guarantee that one of the colors is trivial, i.e., it consists of sets containing
a fixed element?
Partially based on joint works with Peter Frankl and Sergei Kiselev.
Geometric constructions for Ramsey-Turán theory
Hong Liu, yongchuangliu@gmail.com
University of Warwick, United Kingdom
Combining two classical notions in extremal combinatorics, the study of Ramsey-Turán theory
seeks to determine, for integers m ≤ n and p ≤ q, the number RTp(n, Kq, m), which is the
maximum size of an n-vertex Kq-free graph in which every set of at least m vertices contains a
Kp.
Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal
structure for the general case exhibits certain periodic behaviour, resembling that of the special
case when p = 2; (2) constructing analogues of Bollobás-Erdo˝s graphs with densities other than
1/2.
We refute the first conjecture by witnessing asymptotic extremal structures that are drasti-
cally different from the p = 2 case, and address the second problem by constructing Bollobás-
Erdo˝s-type graphs using high dimensional complex spheres with all rational densities. Some
matching upper bounds are also provided.
280
(3/2 + o(1))t average degree forces every t-vertex planar graph as a minor, and the constant
3/2 is optimal; a universal bound of (2 + o(1))t on average degree forcing every t-vertex graph
in any nontrivial minor-closed family as a minor, and the constant 2 is best possible. This is
joint work with John Haslegrave and Hong Liu.
Progress on intersecting families
Andrey Kupavskii, kupavskii@ya.ru
Moscow Institute of Physics and Technology, Russian Federation, and G-SCOP, CNRS, France
We say that a family of sets is intersecting, if any two of its sets intersect. The Erdos-Ko-Rado
theorem characterizes the largest intersecting families of k-element subets of an n-element set,
and a lot of studies have been devoted to the following vague question: what structure could a
family have, given that it has size close to extremal? This question has many possible answers,
depending on the structure we look for, and I am going to discuss several of them during my
talk. These will include junta approximations, diversity and covering number.
Such structural results have implications for other related problems, and I will cover at least
one such application to the colorings of Kneser graphs. Recall that a Kneser graph is a graph on
the collection of all k-element subsets of an n-element set, with two sets connected by an edge
when they are disjoint. One of the famous results of Lovász is the topological proof that such
graph has chromatic number n − 2k + 2. We discuss the following problem: for which values
of n = n(k) we can guarantee that one of the colors is trivial, i.e., it consists of sets containing
a fixed element?
Partially based on joint works with Peter Frankl and Sergei Kiselev.
Geometric constructions for Ramsey-Turán theory
Hong Liu, yongchuangliu@gmail.com
University of Warwick, United Kingdom
Combining two classical notions in extremal combinatorics, the study of Ramsey-Turán theory
seeks to determine, for integers m ≤ n and p ≤ q, the number RTp(n, Kq, m), which is the
maximum size of an n-vertex Kq-free graph in which every set of at least m vertices contains a
Kp.
Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal
structure for the general case exhibits certain periodic behaviour, resembling that of the special
case when p = 2; (2) constructing analogues of Bollobás-Erdo˝s graphs with densities other than
1/2.
We refute the first conjecture by witnessing asymptotic extremal structures that are drasti-
cally different from the p = 2 case, and address the second problem by constructing Bollobás-
Erdo˝s-type graphs using high dimensional complex spheres with all rational densities. Some
matching upper bounds are also provided.
280
