Combinatorics Seminar

When: Sunday, June 2, 10am

Where: Schreiber 309

Speaker: Asaf Ferber, Tel Aviv University

Title: Robustness of properties of graphs and hypergraphs

Abstract:

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.

w3c valid   accessible website
redesigned by barak soreq