Enumeration and randomized constructions of hypertrees

DOI10.1002/RSA.20841MaRDI QIDQ4973641zbMATH OpenOpenAlexWikidataFDO

Authors Nathan Linial, Yuval Peled

Publication date 28 November 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

simplicial complexeshomologyhypertreesthe probabilistic method

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Hypergraphs (05C65) Combinatorial aspects of simplicial complexes (05E45) Singular homology and cohomology theory (55N10)

Abstract: Over thirty years ago, Kalai proved a beautiful $d$-dimensional analog of Cayley's formula for the number of $n$-vertex trees. He enumerated $d$-dimensional hypertrees weighted by the squared size of their $(d-1)$-dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of $d$-hypertrees, which is our concern here. Our main result, Theorem 1.4, significantly improves the lower bound for the number of $d$-hypertrees. In addition, we study a random $1$-out model of $d$-complexes where every $(d-1)$-dimensional face selects a random $d$-face containing it, and show it has a negligible $d$-dimensional homology.

Recommendations

• scientific article; zbMATH DE number 123394
• Enumeration of K-trees and applications
• Random generation of trees and other combinatorial objects
• Algorithms, random tree models and combinatorial objects
• scientific article; zbMATH DE number 3865301
• Recursive combinatorial structures: enumeration, probabilistic analysis and random generation
• Random hyperplane search trees
• Random recursive hypergraphs
• Asymptotic Enumeration of Spanning Trees
• A generalized enumeration of labeled trees and reverse Prüfer algorithm

Cited in

(12)

• The local weak limit of \(k\)-dimensional hypertrees
• Embedding loose spanning trees in 3-uniform hypergraphs
• The number of \((d,k)\)-hypertrees
• Simplex links in determinantal hypertrees
• Generating and enumerating digitally convex sets of trees
• Topology and geometry of random 2-dimensional hypertrees
• scientific article; zbMATH DE number 123394 (Why is no real title available?)
• The worst way to collapse a simplex
• Coboundary expansion for the union of determinantal hypertrees
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• In search of hyperpaths
• Extremal hypercuts and shadows of simplicial complexes

This page was built for publication: Enumeration and randomized constructions of hypertrees

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