1MSIS Department and RUTCOR, Rutgers University, New Jersey, USA 2National Research University: Higher School of Economics, Moscow, Russia 3University of Primorska, Koper, Slovenia
The electronic journal of combinatorics, Tome 26 (2019) no. 3
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 in this paper 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. In particular, we obtain bounds on the size of $1$-Sperner hypergraphs and their transversal hypergraphs, show that the characteristic vectors of the hyperedges are linearly independent over the reals, and prove that $1$-Sperner hypergraphs are both threshold and equilizable. The study of $1$-Sperner hypergraphs is motivated also by their applications in graph theory, which we present in a companion paper.
Endre Boros
1
;
Vladimir Gurvich
2
;
Martin Milanič
3
1
MSIS Department and RUTCOR, Rutgers University, New Jersey, USA
2
National Research University: Higher School of Economics, Moscow, Russia
3
University of Primorska, Koper, Slovenia
@article{10_37236_7890,
author = {Endre Boros and Vladimir Gurvich and Martin Milani\v{c}},
title = {Decomposing {1-Sperner} hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/7890},
zbl = {1417.05145},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7890/}
}
TY - JOUR
AU - Endre Boros
AU - Vladimir Gurvich
AU - Martin Milanič
TI - Decomposing 1-Sperner hypergraphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/7890/
DO - 10.37236/7890
ID - 10_37236_7890
ER -
%0 Journal Article
%A Endre Boros
%A Vladimir Gurvich
%A Martin Milanič
%T Decomposing 1-Sperner hypergraphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7890/
%R 10.37236/7890
%F 10_37236_7890
Endre Boros; Vladimir Gurvich; Martin Milanič. Decomposing 1-Sperner hypergraphs. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/7890
