When: Sunday, June 2, 10am
Where: Schreiber 309
Speaker: Asaf Ferber, Tel Aviv University
Title: Robustness of properties of graphs and hypergraphs
We discuss a few topics related to measurement of robustness of various properties of graphs and hypergraphs. At the beginning of the talk we discuss some properties of G(n,p) which can be preserved after a Maker-Breaker game, i.e, a two players game played on the edge-set of a given graph G, in which Maker's goal is to build a subgraph of G which preserves some given property P (e.g, connectivity, Hamiltonicity etc.), and Breaker's goal is to try to prevent Maker from doing so. At the second part of the talk we discuss problems related to counting and packing Hamilton cycles in dense graphs, digraphs and hypergraphs. We would like to present a general method, based on estimating the permanent of the adjacency matrix of a graph, for tackling these kind of problems. We then show how to utilize this approach to prove several extremal results. At the end of the talk, we show how to obtain similar results for dense hypergraphs and present some challenging open problems.
All the discussed results are part of my PhD thesis under the supervision of Prof. Michael Krivelevich, and are based on joint works with Dennis Clemens, Roman Glebov, Dan Hefetz, Michael Krivelevich, Anita Liebenau, Alon Naor and Benny Sudakov.