Continuous and discontinuous phase transitions in hypergraph processes

Let V denote a set of N vertices. To construct a hypergraph process , create a new hyperedge at each event time of a Poisson process; the cardinality K of this hyperedge is random, with generating function ρ( x ) = def ∑ ρ k x k , where P ( K = k ) = ρ k ; given K = k , the k vertices appearing in the new hyperedge are selected uniformly at random from V . Assume ρ 1 + ρ 2 > 0. Hyperedges of cardinality 1 are called patches , and serve as a way of selecting root vertices. Identifiable vertices are those which are reachable from these root vertices, in a strong sense which generalizes the notion of graph component. Hyperedges are called identifiable if all of their vertices are identifiable. We use “fluid limit” scaling: Hyperedges arrive at rate N , and we study structures of size O (1) and O ( N ). After division by N , numbers of identifiable vertices and hyperedges exhibit phase transitions, which may be continuous or discontinuous depending on the shape of the structure function − log(1 − x )/ρ′( x ), x ∈ (0, 1). Both the case ρ 1 > 0, and the case ρ 1 = 0 < ρ 2 are considered; for the latter, a single extraneous patch is added to mark the root vertex. Published 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004