Decomposing 1-Sperner hypergraphs, with applications to graphs

Hypergraphs are generalizations of graphs in which edges (in this context referred to as hyperedges) can have arbitrary cardinality. A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable if the characteristic vectors of its hyperedges are the binary solutions to a linear equation with positive coefficients. Threshold (Sperner) hypergraphs are defined similarly, with respect to minimal binary solutions of a linear inequality with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce the class of 1-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it, including bounds on the size of 1-Sperner hypergraphs, a proof that every 1-Sperner hypergraph is both threshold and equilizable, and an efficient algorithm for generating the minimal transversals within this class of hypergraphs. Several applications of 1-Sperner hypergraphs and their structure to graphs will also be discussed, including new characterizations of threshold graphs and new classes of graphs of bounded clique-width.

The talk is based on joint works with Endre Boros and Vladimir Gurvich.
Preprints are available at:
https://arxiv.org/abs/1510.02438
https://arxiv.org/abs/1805.03405