Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees (Q311513)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees |
scientific article |
Statements
Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees (English)
0 references
13 September 2016
0 references
Summary: 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 \(n\geqslant 3\), let \(r= r(n)\geqslant 3\) be an integer and let \(K = (k_1,\dots, k_n)\) be a vector of nonnegative integers, where each \(k_j = k_j(n)\) may depend on \(n\). Let \(M = M(n) = \sum_{j=1}^n k_j\) for all \(n\geqslant 3\), and define the set \(\mathcal{I} = \{ n\geqslant 3 \mid r(n) \,\,\text{divides}\,\, M(n)\}\). We assume that \(\mathcal{I}\) is infinite, and perform asymptotics as \(n\) tends to infinity along \(\mathcal{I}\). Our main result is an asymptotic enumeration formula for linear \(r\)-uniform hypergraphs with degree sequence \(K\). 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.
0 references
hypergraph
0 references
asymptotic enumeration
0 references
switching
0 references