Séminaire Lotharingien de Combinatoire, 84B.46 (2020), 11 pp.

Jinha Kim and Minki Kim

Noncover Complexes, Independence Complexes, and Domination Numbers of Hypergraphs

Abstract. Let H be a hypergraph on a finite set V. An independent set of H is a set of vertices that does not contain an edge of H. The indepenence complex of H is the simplicial complex on V whose faces are independent sets of H. A cover of H is a vertex subset which meets all edges of H. The noncover complex of H is the simplicial complex on V whose faces are noncovers of H. In this extended abstract, we study homological properties of the independence complexes and the noncover complexes of hypergraphs. In particular, we obtain a lower bound on the homological connectivity of independence complexes and an upper bound on the Leray number of noncover complexes. The bounds are in terms of hypergraph domination numbers. Our proof method is applied to compute the reduced Betti numbers of the independence complexes of certain uniform hypergraphs, called tight paths and tight cycles. This extends to hypergraphs known results on graphs.


Received: November 20, 2019. Accepted: February 20, 2020. Final version: April 30, 2020.

The following versions are available: