Premium
Essential edges in Poisson random hypergraphs
Author(s) -
Goldschmidt Christina,
Norris James
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20014
Subject(s) - hypergraph , combinatorics , vertex (graph theory) , mathematics , limiting , random graph , graph , homogeneous , discrete mathematics , mechanical engineering , engineering
Consider a random hypergraph on a set of N vertices in which, for 1 ≤ k ≤ N , a Poisson ( N β k ) number of hyperedges is scattered randomly over all subsets of size k. We collapse the hypergraph by running the following algorithm to exhaustion: Pick a vertex having a 1‐edge and remove it; collapse the hyperedges over that vertex onto their remaining vertices; repeat until there are no 1‐edges left. We call the vertices removed in this process identifiable. Also any hyperedge all of whose vertices are removed is called identifiable. We say that a hyperedge is essential if its removal prior to collapse would have reduced the number of identifiable vertices. The limiting proportions, as N → ∞, of identifiable vertices and hyperedges were obtained in R. W. R. Darling and J. R. Norris [Structure of large random hypergraphs, Ann Appl Probab, to appear. In this paper, we establish the limiting proportion of essential hyperedges. We also discuss, in the case of a random graph, the relation of essential edges to the 2‐core of the graph, the maximal subgraph with minimal vertex degree 2. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004