Weak saturation of multipartite hypergraphs

Denys Bulavka (Matousek prize lecture)

Charles University

March 2, 2023, 12:20 in S6


Given a host graph H and a pattern graph P, a subgraph G of H is weakly P-saturated in H  if the edge set E(H)-E(G) admits an ordering e_1,e_2,.. such that adding these edges in this ordering to G creates a new copy of P at each step containing the newly added edge. Weak saturation was introduced by Bollobas in the 60's, and the main task is to compute the minimum number of edges a weakly P-saturated graph of H can have, so called weak saturation number of P in H. Weak saturation has been studied extensively. For example, if both pattern and host are cliques then the weak saturation number was determined independently by Frankl, Kalai, and Alon; if the pattern is a complete bipartite graph with equal-sized parts, and the host is the clique the weak saturation number was determined by Kalai; the case where both pattern and host are complete d-partite d-uniform hypergraphs was studied first by Alon and later by Moshkovitz and Shapira. In this talk, I will explain our result concerning the case where the pattern and the host are complete d-partite q-uniform hypergraphs, with q at most d, generalizing the above mentioned results of Alon and, Moshkovitz and Shapira.

This is a joint work with Martin Tancer and Mykhaylo Tyomkyn.