Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 10, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Anders Martinsson
Inspired by the problem of inducibility of graphs, a recent paper by Alon, Hefetz, Krivelevich and Tyomkyn posed the following problem. Given parameters ℓ, k and n what is the maximum probability, taken over all n-vertex graphs G, that k random vertices of G induces exactly ℓ edges? For ℓ equal to 0 or k choose 2, this is trivially one as attained by the empty and complete graphs respectively. Alon et al conjectured an upper bound of 1/e+o(1) for any other ℓ. A stronger version of this statement was shown by Kwan, Sudakov, and Tran (as seen in a past Mise 🙂) under the assumtion that ℓ is at least linear in k. In this talk I will present a simple argument that the bound holds also for small ℓ, thus resolving the conjecture affirmatively. This is joint work with Mousset, Noever and Trujić.
Automatic MiSe System Software Version 1.4803M | admin login