1-Sperner hypergraphs and new characterizations of threshold graphs

A hypergraph is a pair (V,E) such that V is a finite set and E is a set of subsets of V (members of E are called hyperedges). We introduce a new class of hypergraphs, the class of 1-Sperner hypergraphs. A hypergraph H is said to be 1-Sperner if every two distinct hyperedges e,f of H satisfy min { | e \ f | ,| f \ e | } = 1.

We prove a decomposition theorem for 1-Sperner hypergraphs and examine several of its consequences, including bounds on the size of 1-Sperner hypergraphs and a new, constructive proof of the fact that every 1-Sperner hypergraph is threshold. (A hypergraph H = (V,E) is said to be threshold if there exist a non-negative vertex weight function w and a non-negative threshold t such that for every subset X of V, we have w(X) >= t if and only if X contains a hyperedge.)

A hypergraph is said to be Sperner (or: a clutter) if no hyperedge is contained in another one. Given a graph G, the clique hypergraph of G is the hypergraph C(G) with vertex set V(G) in which the hyperedges are exactly the maximal cliques of G. The clique hypergraphs of graphs are known to be exactly those Sperner hypergraphs H that are also normal (or: conformal), that is, for every subset X of V(H) such that every pair of elements in X is contained in a hyperedge, there exists a hyperedge containing X.

We show that within the class of normal Sperner hypergraphs, the (generally properly nested) classes of 1-Sperner hypergraphs, of threshold hypergraphs, and of 2-asummable hypergraphs coincide. This yields new characterizations of the class of threshold graphs.

The talk is based on joint work with Endre Boros and Vladimir Gurvich (both at Rutgers University).

Preprint is available at: http://arxiv.org/abs/1510.02438

Slides of talk are here.