Random hypergraph processes with degree restrictions

Catherine Greenhill, Andrzej Ruciński, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

A d-process for s-uniform hypergraphs starts with an empty hypergraph on n vertices, and adds one s-tuple at each time step, chosen uniformly at random from those 5-tuples which are not already present as a hyperedge and which consist entirely of vertices with degree less than d. We prove that for d ≥ 2 and s ≥ 3, with probability which tends to 1 as n tends to infinity, the final hypergraph is saturated; that is, it has n - i vertices of degree d and i vertices of degree d -1, where i = dn - ⌊sdn/s⌋. This generalises the result for s = 2 obtained by the second and third authors. In addition, when s ≥ 3, we prove asymptotic equivalence of this process and the more relaxed process, in which the chosen s-tuple may already be a hyperedge (and which therefore may form multiple hyperedges).

Original languageEnglish
Pages (from-to)319-332
Number of pages14
JournalGraphs and Combinatorics
Volume20
Issue number3
DOIs
Publication statusPublished - 2004
Externally publishedYes

Cite this