TY - JOUR

T1 - Random hypergraph processes with degree restrictions

AU - Greenhill, Catherine

AU - Ruciński, Andrzej

AU - Wormald, Nicholas C.

PY - 2004

Y1 - 2004

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=17444376809&partnerID=8YFLogxK

U2 - 10.1007/s00373-004-0571-2

DO - 10.1007/s00373-004-0571-2

M3 - Article

AN - SCOPUS:17444376809

VL - 20

SP - 319

EP - 332

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 3

ER -