Enumeration and randomized constructions of hypertrees

DOI10.1002/RSA.20841zbMATH Open1433.05340arXiv1801.02423OpenAlexW2910179681WikidataQ128578653 ScholiaQ128578653MaRDI QIDQ4973641FDOQ4973641

Authors: Nathan Linial, Yuval Peled 

Publication date: 28 November 2019

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

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.

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

Recommendations

• scientific article
• 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

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)

Cited In (10)

• Embedding loose spanning trees in 3-uniform hypergraphs
• Simplex links in determinantal hypertrees
• Generating and enumerating digitally convex sets of trees
• Topology and geometry of random 2-dimensional hypertrees
• Title not available (Why is that?)
• Coboundary expansion for the union of determinantal hypertrees
• The local weak limit of 𝑘-dimensional hypertrees
• The worst way to collapse a simplex
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• In search of hyperpaths

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)