2003/12/24 by R. W. R. Darling, David Levin, Darling, R. W. R. +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #05C80 #05C85 #60F17 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #math.CO #math.PR #msc:05C80 #msc:05C85 #msc:60F17
paper · pdf · doi:10.48550/arxiv.math/0312451
25 pages, 2 figures. Revised version. To appear in Random Structures & Algorithms
openalex publication_date 2003/12/24 · arxiv created 2004/03/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 arbitrary probability generating function r(x), except that we assume P(K=1) +P(K=2) > 0. Given K=k, the k vertices appearing in the new hyperedge are selected uniformly at random from V. 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 also 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 reducible hyperedges exhibit phase transitions, which may be continuous or discontinuous depending on the shape of the structure function -log(1 - x)/r'(x), for x in (0,1). Both the case P(K=1) > 0 and the case P(K=1) = 0 < P(K=2) are considered; for the latter, a single extraneous patch is added to mark the root vertex.