Exact bounds for some hypergraph saturation problems

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: Let W_n(p,q) denote the minimum number of edges in an n x n bipartite graph G on vertex sets X,Y that satisfies the following condition; one can add the edges between X and Y that do not belong to G one after the other so that whenever a new edge is added, a new copy of K_{p,q} is created. The problem of bounding W_n(p,q), and its natural hypergraph generalization, was introduced by Balogh, Bollob'as, Morris and Riordan. Their main result, specialized to graphs, used algebraic methods to determine W_n(1,q). Our main results in this paper give exact bounds for W_n(p,q), its hypergraph analogue, as well as for a new variant of Bollob'as's Two Families theorem. In particular, we completely determine W_n(p,q), showing that if 1 <= p <= q <= n then W_n(p,q) = n^2 - (n-p+1)^2 + (q-p)^2. Our proof applies a reduction to a multi-partite version of the Two Families theorem obtained by Alon. While the reduction is combinatorial, the main idea behind it is algebraic.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Exact bounds for some hypergraph saturation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2259864)