Combinatorics Seminar

When: Sunday, November 25, 10am Where: Schreiber 006 (NOTE THE UNUSUAL LOCATION!) Speaker: Guy Moshkovitz, Tel Aviv University Title: Exact Bounds for Some Hypergraph Saturation Problems

Abstract:

A bipartite graph G on vertex sets X,Y is said to be weakly H-saturated if one can add the edges between X and Y that are missing in G one after the other so that whenever a new edge is added, a new copy of H is created. Balogh, Bollobas, Morris and Riordan have recently raised the question of finding the minimum number of edges in an nxn bipartite graph that is weakly K_{p,q}-saturated. They used algebraic arguments to give a partial answer to this question, as well as to its hypergraph analogue.

We settle this question, in both the graph and hypergraph cases. As a byproduct, we also get a new, multi-partite variant of the well-known Two Families theorem.

Joint work with Asaf Shapira.