Date
Tue, 10 Nov 2015
14:30
Location
L6
Speaker
Pedro Vieira
Organisation
ETH Zurich

We discuss a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of $G(n,p)$ in order to typically find a subgraph possessing a certain structure. More specifically, given a monotone property of graphs $P$, we consider $G(n,p)$ where $p$ is above the threshold probability for $P$ and look for adaptive algorithms which query significantly less than all pairs of vertices in order to reveal that the property $P$ holds with high probability. In this talk we focus particularly on the properties of containing a Hamilton cycle and containing paths of linear size. The talk is based on joint work with Asaf Ferber, Michael Krivelevich and Benny Sudakov.

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 14:57.