- FR
- EN
lundi 17 septembre, 14h, salle P303
Abstract :
A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., 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 on arXiv,
https://arxiv.org/abs/1510.02438
https://arxiv.org/abs/1805.03405
