Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges. (March 2019)

• Record Type: Journal Article
• Authors: Aldosari, Haya S.; Greenhill, Catherine
• Is Part Of: European journal of combinatorics. Volume 77(2019)
• Page Start: 68
• Page End: 77
• Publication Date: 2019-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.11.002
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For n ≥ 3 and r = r ( n ) ≥ 3, let k = k ( n ) = ( k 1, …, k n ) be a sequence of non-negative integers with sum M ( k ) = ∑ j = 1 n k j . We assume that M ( k ) is divisible by r for infinitely many values of n, and restrict our attention to these values. Let X = X ( n ) be a simple r -uniform hypergraph on the vertex set V = { v 1, v 2, …, v n } with t edges. We denote by H r ( k ) the set of all simple r -uniform hypergraphs on the vertex set V with degree sequence k, and let H r ( k, X ) be the set of all hypergraphs in H r ( k ) which contain no edge of X . We give an asymptotic enumeration formula for the size of H r ( k, X ) . This formula holds when r 4 k max 3 = o ( M ( k ) ), t k max 3 = o ( M ( k ) 2 ) and r t k max 4 = o ( M ( k ) 3 ) . Our proof involves the switching method. As a corollary, we obtain an asymptotic formula for the number of hypergraphs in H r ( k ) which contain every edge of X . We apply this result to find asymptotic expressions for the expected number of perfect matchings and loose Hamilton cycles in a random hypergraph in H r ( k ) in the regular case.