Asymptotic enumeration of sparse uniform hypergraphs with given degrees

DOI10.1016/J.EJC.2015.06.004MaRDI QIDQ499481zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Vladimir Blinovsky, Catherine Greenhill

Publication date 30 September 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic enumeration formula

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: Let $rgeq2$ be a fixed integer. For infinitely many $n$, let $$ be a vector of nonnegative integers such that their sum $M$ is divisible by $r$. We present an asymptotic enumeration formula for simple $r$-uniform hypergraphs with degree sequence $k$. (Here "simple" means that all edges are distinct and no edge contains a repeated vertex.) Our formula holds whenever the maximum degree $k_{mathrmmax}$ satisfies $k_{mathrmmax}^3=o(M)$.

Recommendations

• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• Asymptotic enumeration of sparse multigraphs with given degrees
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• Asymptotic enumeration of sparse 2-connected graphs
• Asymptotic enumeration of non-uniform linear hypergraphs
• Asymptotic enumeration of graphs with given degree sequence
• The asymptotic number of connected \(d\)-uniform hypergraphs

Cites work

• Approximate counting of regular hypergraphs
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Probabilistic existence of regular combinatorial structures
• Subgraphs of dense random graphs with specified degrees

Cited in

(12)

• Degree sequences of sufficiently dense random uniform hypergraphs
• On the number of linear multipartite hypergraphs with given size
• Asymptotic enumeration of non-uniform linear hypergraphs
• Asymptotic enumeration of sparse 2-connected graphs
• Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
• The average number of spanning hypertrees in sparse uniform hypergraphs
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
• Asymptotic enumeration of sparse multigraphs with given degrees
• Approximate counting of regular hypergraphs
• The matching process and independent process in random regular graphs and hypergraphs

This page was built for publication: Asymptotic enumeration of sparse uniform hypergraphs with given degrees

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