Noncover complexes, independence complexes, and domination numbers of hypergraphs. (English) Zbl 1508.05129

Summary: Let \(\mathcal{H}\) be a hypergraph on a finite set \(V\). An independent set of \(\mathcal{H}\) is a set of vertices that does not contain an edge of \(\mathcal{H}\). The indepenence complex of \(\mathcal{H}\) is the simplicial complex on \(V\) whose faces are independent sets of \(\mathcal{H}\). A cover of \(\mathcal{H}\) is a vertex subset which meets all edges of \(\mathcal{H}\). The noncover complex of \(\mathcal{H}\) is the simplicial complex on \(V\) whose faces are noncovers of \(\mathcal{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.


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C65 Hypergraphs
13D05 Homological dimension and commutative rings
13F55 Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes
Full Text: Link


[1] B. D. Acharya. “Domination in hypergraphs”.AKCE J. Graph Combin.4(2007), pp. 117-126. · Zbl 1136.05047
[2] R. Aharoni, M. Chudnovsky, and A. Kotlov. “Triangulated spheres and colored cliques”. Discrete Comput. Geom.28.2 (2002), pp. 223-229.Link. · Zbl 1017.52009
[3] R. Aharoni and P. Haxell. “Hall’s theorem for hypergraphs”.J. Graph Th.35.2 (2000), pp. 83- 88.Link. · Zbl 0956.05075
[4] A. Björner and M. Tancer. “Note: Combinatorial Alexander duality - A short and elementary proof”.Discrete Comput. Geom.42(2009), pp. 586-593.Link. · Zbl 1179.57037
[5] C. Bujtás, M. Henning, Z. Tuza, and A. Yeo. “Total transversals and total domination in uniform hypergraphs”.Elctron. J. Combin.21.2 (2014), #P2.24.Link. · Zbl 1300.05196
[6] I. Choi, J. Kim, and B. Park. “Collapsibility of non-cover complexes of graphs”.Elctron. J. Combin.27.1 (2020), #P1.20.Link. · Zbl 1431.05111
[7] M. Chudnovsky. “Systems of disjoint representatives”. PhD thesis, unpublished. Haifa, 2000.
[8] H. Dao and J. Schweig. “Projective dimension, graph domination parameters, and independence complex homology”.J. Combin. Theory, Ser. A120.2 (2013), pp. 453-469.Link. · Zbl 1257.05114
[9] H. Dao and J. Schweig. “Further applications of clutter domination parameters to projective dimension”.J. Algebra432(2015), pp. 1-11.Link. · Zbl 1316.13019
[10] A. Holmsen, L. Martinez-Sandoval, and L. Montejano. “A geometric Hall-type theorem”. Proc. Amer. Math. Soc.144(2016), pp. 503-511.Link. · Zbl 1331.05219
[11] G. Kalai and R. Meshulam. “A topological colorful Helly theorem”.Adv. Math.191.2 (2005), pp. 305-311.Link. · Zbl 1064.52008
[12] G. Kalai and R. Meshulam. “Intersections of Leray complexes and regularity of monomial ideals”.J. Combin. Theory, Ser. A113.7 (2006), pp. 1586-1592.Link. · Zbl 1105.13026
[13] R. Meshulam. “The clique complex and hypergraph matching”.Combinatorica21.1 (2001), pp. 89-94.Link. · Zbl 1107.05302
[14] R.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.