Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees

zbMATH Open1344.05073MaRDI QIDQ311513FDOQ311513

Authors Vladimir Blinovsky, Catherine Greenhill

Publication date 13 September 2016

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

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

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

hypergraphasymptotic enumerationswitching

Mathematics Subject Classification ID

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

Abstract: A hypergraph is simple if it has no loops and no repeated edges, and a hypergraph is linear if it is simple and each pair of edges intersects in at most one vertex. For $ngeq3$, let $r=r(n)geq3$ be an integer and let $$ be a vector of nonnegative integers, where each $k_j=k_j(n)$ may depend on $n$. Let $M=M(n)=su{m}_{j=1}^n{k}_j$ for all $ngeq3$, and define the set $mathcalI=ngeq3midr(n)extdividesM(n)$. We assume that $mathcalI$ is infinite, and perform asymptotics as $n$ tends to infinity along $mathcalI$. Our main result is an asymptotic enumeration formula for linear $r$-uniform hypergraphs with degree sequence $$. This formula holds whenever the maximum degree $k_{max}$ satisfies $r^4{k}_{max}^4(k_{max}+r)=o(M)$. Our approach is to work with the incidence matrix of a hypergraph, interpreted as the biadjacency matrix of a bipartite graph, enabling us to apply known enumeration results for bipartite graphs. This approach also leads to a new asymptotic enumeration formula for simple uniform hypergraphs with specified degrees, and a result regarding the girth of random bipartite graphs with specified degrees.

Recommendations

• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Asymptotic enumeration of non-uniform linear hypergraphs
• Asymptotic enumeration of sparse multigraphs with given degrees
• Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
• 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
• Linear Ramsey numbers of sparse graphs
• Asymptotic enumeration of graphs with given degree sequence

Cites work

• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• 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
• Asymptotic enumeration of sparse multigraphs with given degrees
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Coloring uniform hypergraphs with few edges
• Intersection graphs of k-uniform linear hypergraphs
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Probabilistic existence of rigid combinatorial structures
• Properly 2-Colouring Linear Hypergraphs
• Randomly coloring simple hypergraphs
• Short cycles in random regular graphs
• Subgraphs of dense random graphs with specified degrees

Cited in

(13)

• Lower bounds on Tuza constants for transversals in linear uniform hypergraphs
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Degree sequences of sufficiently dense random uniform hypergraphs
• On the number of linear multipartite hypergraphs with given size
• Sampling hypergraphs with given degrees
• Asymptotic enumeration of non-uniform linear hypergraphs
• Asymptotic enumeration of linear hypergraphs with given number of vertices and edges
• The average number of spanning hypertrees in sparse uniform hypergraphs
• On the random greedy linear uniform hypergraph packing
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges

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

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