The average number of spanning hypertrees in sparse uniform hypergraphs

DOI10.1016/J.DISC.2020.112192MaRDI QIDQ2219973zbMATH OpenOpenAlexFDO

Authors Haya S. Aldosari, Catherine Greenhill

Publication date 21 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.04993

zbMATH Keywords

hypergraphasymptotic enumerationhypertreespanning treerandom hypergraph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Abstract: An $r$-uniform hypergraph $H$ consists of a set of vertices $V$ and a set of edges whose elements are $r$-subsets of $V$. We define a hypertree to be a connected hypergraph which contains no cycles. A hypertree spans a hypergraph $H$ if it is a subhypergraph of $H$ which contains all vertices of $H$. Greenhill, Isaev, Kwan and McKay (2017) gave an asymptotic formula for the average number of spanning trees in graphs with given, sparse degree sequence. We prove an analogous result for $r$-uniform hypergraphs with given degree sequence $$. Our formula holds when $r^5{k}_{max}^3=o((kr-k-r)n)$, where $k$ is the average degree and $k_{max}$ is the maximum degree.

Recommendations

• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Spanning trees in random regular uniform hypergraphs
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• The average number of spanning trees in sparse graphs with given degrees

Cites work

• scientific article; zbMATH DE number 997340 (Why is no real title available?)
• scientific article; zbMATH DE number 3873374 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 3801587 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• Efficient Prüfer-like coding and counting labelled hypertrees
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• On the number of hyperforests
• Spanning trees of 3-uniform hypergraphs
• The average number of spanning trees in sparse graphs with given degrees

Cited in

(2)

• The average number of spanning trees in sparse graphs with given degrees
• Spanning trees in random regular uniform hypergraphs

This page was built for publication: The average number of spanning hypertrees in sparse uniform hypergraphs

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