Page 280 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 280
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
Universal phenomena for random constrained permutations
Jacopo Borga, borgajacopo@gmail.com
University of Zurich, Switzerland
How do local/global constraints affect the limiting shape of random permutations? This is
a classical question that has received considerable attention in the last 15 years. In this talk
we give an overview of some recent results on this topic, mainly focusing on random pattern-
avoiding permutations. We first introduce a notion of scaling limit for permutations, called
permutons. Then we present some recent results that highlight certain universal phenomena for
permuton limits of various families of pattern-avoiding permutations. These results will lead
us to the definition of three remarkable new limiting random permutons: the “biased Brownian
separable permuton”, the “Baxter permuton” and the "skew Brownian permuton". We finally
discuss some recent results that show how permuton limits are useful to investigate the be-
haviour of certain statistics on random pattern-avoiding permutations, such as the length of the
longest increasing subsequence.
Progress towards Nash-Williams’ Conjecture on Triangle Decompositions
Michelle Delcourt, michelledelcourt@gmail.com
Ryerson University, Canada
Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of
the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large,
triangle divisible graph on n vertices with minimum degree at least 0.75 n admits a triangle
decomposition. In the light of recent results, the fractional version of this problem is of central
importance. A fractional triangle decomposition is an assignment of non-negative weights to
each triangle in a graph such that the sum of the weights along each edge is precisely one.
We show that for any graph on n vertices with minimum degree at least 0.827327 n admits
a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus,
this implies that for every sufficiently large triangle divisible graph on n vertices with minimum
degree at least 0.82733 n admits a triangle decomposition. This is a significant improvement
over the previous asymptotic result of Dross showing the existence of fractional triangle decom-
positions of sufficiently large graphs with minimum degree more than 0.9 n. This is joint work
with Luke Postle.
New results for MaxCut in H-free graphs
Stefan Glock, stefan.glock@eth-its.ethz.ch
ETH Zürich, Switzerland
Coauthors: Oliver Janzer, Benny Sudakov
The MaxCut problem asks for the size mc(G) of a largest cut in a graph G. It is well known that
mc(G) ≥ m/2 for any m-edge graph G, and the difference mc(G) − m/2 is called the surplus
of G. The study of the surplus of H-free graphs was initiated by Erdo˝s and Lovász in the 70s,
who in particular asked what happens for triangle-free graphs. This was famously resolved by
Alon, who showed that in the triangle-free case the surplus is Ω(m4/5), and found constructions
278
Universal phenomena for random constrained permutations
Jacopo Borga, borgajacopo@gmail.com
University of Zurich, Switzerland
How do local/global constraints affect the limiting shape of random permutations? This is
a classical question that has received considerable attention in the last 15 years. In this talk
we give an overview of some recent results on this topic, mainly focusing on random pattern-
avoiding permutations. We first introduce a notion of scaling limit for permutations, called
permutons. Then we present some recent results that highlight certain universal phenomena for
permuton limits of various families of pattern-avoiding permutations. These results will lead
us to the definition of three remarkable new limiting random permutons: the “biased Brownian
separable permuton”, the “Baxter permuton” and the "skew Brownian permuton". We finally
discuss some recent results that show how permuton limits are useful to investigate the be-
haviour of certain statistics on random pattern-avoiding permutations, such as the length of the
longest increasing subsequence.
Progress towards Nash-Williams’ Conjecture on Triangle Decompositions
Michelle Delcourt, michelledelcourt@gmail.com
Ryerson University, Canada
Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of
the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large,
triangle divisible graph on n vertices with minimum degree at least 0.75 n admits a triangle
decomposition. In the light of recent results, the fractional version of this problem is of central
importance. A fractional triangle decomposition is an assignment of non-negative weights to
each triangle in a graph such that the sum of the weights along each edge is precisely one.
We show that for any graph on n vertices with minimum degree at least 0.827327 n admits
a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus,
this implies that for every sufficiently large triangle divisible graph on n vertices with minimum
degree at least 0.82733 n admits a triangle decomposition. This is a significant improvement
over the previous asymptotic result of Dross showing the existence of fractional triangle decom-
positions of sufficiently large graphs with minimum degree more than 0.9 n. This is joint work
with Luke Postle.
New results for MaxCut in H-free graphs
Stefan Glock, stefan.glock@eth-its.ethz.ch
ETH Zürich, Switzerland
Coauthors: Oliver Janzer, Benny Sudakov
The MaxCut problem asks for the size mc(G) of a largest cut in a graph G. It is well known that
mc(G) ≥ m/2 for any m-edge graph G, and the difference mc(G) − m/2 is called the surplus
of G. The study of the surplus of H-free graphs was initiated by Erdo˝s and Lovász in the 70s,
who in particular asked what happens for triangle-free graphs. This was famously resolved by
Alon, who showed that in the triangle-free case the surplus is Ω(m4/5), and found constructions
278
