[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 4th 2019
You are cordially invited to our next Monday Lecture & Colloquium on
February 4th at 14:15 h & 16:00 h at FU Berlin.
Location:
Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin
Time: Monday, February 4th - 14:15 h
Lecture: Karim Adiprasito (Hebrew University of Jerusalem)
Title: Triangulated manifolds, Lefschetz conjectures and the revenge of
marriages
Abstract:
Stanley gave us necessary conditions that f-vectors of simplicial
polytopes must satisfy by relating the problem to the hard Lefschetz
theorem in algebraic geometry, an insurmountably deep and intimidating
theorem in algebraic geometry. McMullen conjectured that these conditions
are necessary in general, posing before us the problem of proving the hard
Lefschetz theorem beyond what algebraic geometers would dream of.
I will talk about the revenge of combinatorics, and in particular discuss
how Hall's marriage theorem (or rather, one of its proofs) provides a way
to this deep algebraic conjecture.
Based on arxiv:1812.10454
Coffee & Tea Break:
Room 134
Time: Monday, February 4th - 16:00 h s.t.
Colloquium: Patrick Morris (Freie Universität Berlin)
Title: Clique tilings in randomly perturbed graphs
Abstract:
A major theme in both extremal and probabilistic combinatorics is to find
the appearance thresholds for certain spanning structures. Classical
examples of such spanning structures include perfect matchings, Hamilton
cycles and H-tilings, where we look for vertex disjoint copies of H
covering all the vertices of some host graph G. In this talk we will focus
on H-tilings in the case that H is a clique, a natural generalisation of a
perfect matching.
On the one hand there is the extremal question, how large does the minimum
degree of an n-vertex graph G have to be to guarantee the existence of a
clique factor in G? On the other hand, there is the probabilistic
question. How large does p need to be to almost surely ensure the
appearance of a clique factor in the Erdős-Rényi random graph G(n,p)?
Optimal answers to these questions were given in two famous papers. The
extremal question was answered by Hajnal and Szemerédi in 1970 and the
probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we
bridge the gap between these two results by approaching the following
question which contains the previous questions as special cases. Given an
arbitrary graph of some fixed minimum degree, how many random edges need
to be added on the same set of vertices to ensure the existence of a
clique tiling? We give optimal answers to this question in all cases. Such
results are part of a recent research trend studying properties of what is
known as the randomly perturbed graph model, introduced by Bohman, Frieze
and Martin in 2003.
This is joint work with Jie Han and Andrew Treglown.
