Hypergraph Versals

arXiv1602.01770MaRDI QIDQ6270149FDOQ6270149

Publication date: 4 February 2016

Abstract: Let H be a hypergraph on n vertices with the property that no edge contains another. We prove some results for a special case of the Isolation Lemma when the label set for the edges of H can only take two values. Given any set of vertices S and an edge e, the weight of S in e is the size of e plus the size of the intersection of S and e. A versal S for an edge e is a set of vertices with weight in e smaller than the weight in any other edge. We show that H always has at least n + 1 versals except if H is either the set of all singletons T_n or the complement of T_n or the 4-cycle graph. In those exceptional cases there are only n versals.

This page was built for publication: Hypergraph Versals

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