Collapsibility of simplicial complexes of hypergraphs

MaRDI QIDQ2327224zbMATH OpenFDO

Authors Alan Lew

Publication date 14 October 2019

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

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

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

\(r\)-uniform hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05) Combinatorial aspects of simplicial complexes (05E45)

Abstract: Let $mathcalH$ be a hypergraph of rank $r$. We show that the simplicial complex whose simplices are the hypergraphs $mathcalFsubsetmathcalH$ with covering number at most $p$ is $$-collapsible, and the simplicial complex whose simplices are the pairwise intersecting hypergraphs $mathcalFsubsetmathcalH$ is $$-collapsible.

Review text

Summary: Let \(\mathcal{H}\) be an \(r\)-uniform hypergraph. We show that the simplicial complex whose simplices are the hypergraphs \(\mathcal{F}\subset\mathcal{H}\) with covering number at most \(p\) is \(\left(\binom{r+p}{r}-1\right)\)-collapsible. Similarly, the simplicial complex whose simplices are the pairwise intersecting hypergraphs \(\mathcal{F}\subset\mathcal{H}\) is \(\frac{1}{2}\binom{2r}{r}\)-collapsible.

Recommendations

• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• Collapsibility of random clique complexes
• Collapsibility of non-cover complexes of graphs
• The threshold for d-collapsibility in random complexes
• D-collapsibility is NP-complete for d 4

Cites work

• An extremal problem for sets with applications to graph theory
• An extremal problem for two families of sets
• d-collapsing and nerves of families of convex sets
• Dimension gaps between representability and collapsibility
• Geometrical solution of an intersection problem for two hypergraphs
• scientific article; zbMATH DE number 6470115 (Why is no real title available?)
• Intersection patterns of convex sets
• On a product dimension of graphs
• Rainbow fractional matchings
• Rainbow matchings in r-partite r-graphs
• Simplicial complexes of graphs

Cited in

(6)

• Collapsibility of non-cover complexes of graphs
• scientific article; zbMATH DE number 5912063 (Why is no real title available?)
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
• scientific article; zbMATH DE number 6470115 (Why is no real title available?)
• On Vietoris–Rips Complexes (with Scale 3) of Hypercube Graphs

This page was built for publication: Collapsibility of simplicial complexes of hypergraphs

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