Résumé : 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 genera ting 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.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |