Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees

zbMATH Open1344.05073arXiv1409.1314MaRDI QIDQ311513FDOQ311513

Authors: Vladimir Blinovsky, Catherine Greenhill 

Publication date: 13 September 2016

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

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.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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

zbMATH Keywords

hypergraphasymptotic enumerationswitching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Coloring uniform hypergraphs with few edges
• Short cycles in random regular graphs
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Intersection graphs of k-uniform linear hypergraphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration by degree sequence of graphs of high degree
• Randomly coloring simple hypergraphs
• Approximate counting of regular hypergraphs
• Subgraphs of dense random graphs with specified degrees
• Properly 2-Colouring Linear Hypergraphs
• Title not available (Why is that?)
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Asymptotic enumeration of sparse multigraphs with given degrees
• Probabilistic existence of rigid combinatorial structures
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums

Cited In (13)

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

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)