Page 284 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 284
EXTREMAL AND PROBABILISTIC COMBINATORICS (MS-20)
On a problem of M. Talagrand
Jinyoung Park, jpark@math.ias.edu
Institute for Advanced Study, United States
Coauthors: Jeff Kahn, Keith Frankston
We will discuss some special cases of a conjecture of M. Talagrand relating two notions of
“threshold” for an increasing family F of subsets of a finite set X. The full conjecture im-
plies equivalence of the “Fractional Expectation-Threshold Conjecture,” due to Talagrand and
recently proved by Frankston, Kahn, Narayanan, and myself, and the (stronger) “Expectation-
Threshold Conjecture” of Kahn and Kalai.
The conjecture under discussion here says there is a fixed J such that if, for a given increas-
ing family F , p ∈ [0, 1] admits λ : 2X → R+ with
λS ≥ 1 ∀F ∈ F
S⊆F
and
λSp|S| ≤ 1/2,
S
then p/J admits such a λ taking values in {0, 1}.
Talagrand showed this when λ is supported on singletons and suggested a couple of more
challenging test cases. In the talk, I will give more detailed descriptions of this problem, and
some proof ideas if time allows.
Ramsey properties of randomly perturbed sets of integers and the
asymmetric random Rado theorem
Yury Person, yury.person@tu-ilmenau.de
Technische Universität Ilmenau, Germany
Coauthor: Elad Aigner-Horev
We discuss some results in randomly perturbed sets of integers, i.e. sets of the form A∪[n]p, and
thresholds for asymmetric Rado properties in [n]p, which guarantee existence of monochromatic
solutions to certain systems of linear equations.
Packing D-degenerate graphs
Diana Piguet, piguet@cs.cas.cz
Institute of Computer Science of the Czech Academy of Sciences, Czech Republic
Coauthors: Peter Allen, Julia Böttcher, Jan Hladký, Dennis Clemens, Anusch Taraz
A family {H1, . . . , Hk} of graphs packs in a host graph G, if there is a colouring of the edges
of G with colours 1, . . . , k so that there is a copy of Hi in the subgraph of G induced by colour
i. A conjecture of Gyárfás from 1976, now referred to as the Tree Packing Conjecture, says that
if Ti is an i-vertex tree for each 1 ≤ i ≤ n, then {T1, . . . , Tn} packs in the complete graph Kn.
We shall present a result on packing D-degenerate graphs which has direct implications on the
Tree Packing Conjecture.
282
On a problem of M. Talagrand
Jinyoung Park, jpark@math.ias.edu
Institute for Advanced Study, United States
Coauthors: Jeff Kahn, Keith Frankston
We will discuss some special cases of a conjecture of M. Talagrand relating two notions of
“threshold” for an increasing family F of subsets of a finite set X. The full conjecture im-
plies equivalence of the “Fractional Expectation-Threshold Conjecture,” due to Talagrand and
recently proved by Frankston, Kahn, Narayanan, and myself, and the (stronger) “Expectation-
Threshold Conjecture” of Kahn and Kalai.
The conjecture under discussion here says there is a fixed J such that if, for a given increas-
ing family F , p ∈ [0, 1] admits λ : 2X → R+ with
λS ≥ 1 ∀F ∈ F
S⊆F
and
λSp|S| ≤ 1/2,
S
then p/J admits such a λ taking values in {0, 1}.
Talagrand showed this when λ is supported on singletons and suggested a couple of more
challenging test cases. In the talk, I will give more detailed descriptions of this problem, and
some proof ideas if time allows.
Ramsey properties of randomly perturbed sets of integers and the
asymmetric random Rado theorem
Yury Person, yury.person@tu-ilmenau.de
Technische Universität Ilmenau, Germany
Coauthor: Elad Aigner-Horev
We discuss some results in randomly perturbed sets of integers, i.e. sets of the form A∪[n]p, and
thresholds for asymmetric Rado properties in [n]p, which guarantee existence of monochromatic
solutions to certain systems of linear equations.
Packing D-degenerate graphs
Diana Piguet, piguet@cs.cas.cz
Institute of Computer Science of the Czech Academy of Sciences, Czech Republic
Coauthors: Peter Allen, Julia Böttcher, Jan Hladký, Dennis Clemens, Anusch Taraz
A family {H1, . . . , Hk} of graphs packs in a host graph G, if there is a colouring of the edges
of G with colours 1, . . . , k so that there is a copy of Hi in the subgraph of G induced by colour
i. A conjecture of Gyárfás from 1976, now referred to as the Tree Packing Conjecture, says that
if Ti is an i-vertex tree for each 1 ≤ i ≤ n, then {T1, . . . , Tn} packs in the complete graph Kn.
We shall present a result on packing D-degenerate graphs which has direct implications on the
Tree Packing Conjecture.
282
