Decomposing 1-Sperner hypergraphs

Authors Endre Boros, Martin Milanič, Vladimir Gurvich

Publication date 5 August 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02438, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

1-Sperner hypergraphs equilizable Sperner hypergraphs threshold Sperner hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65)

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 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.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

JBool

This page was built for publication: Decomposing 1-Sperner hypergraphs

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