Journal article icon

Journal article

Essential edges in Poisson random hypergraphs

Abstract:

Consider a random hypergraph on a set of N vertices in which, for 1 ≤ k ≤ N, a Poisson (Nβκ) 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...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1002/rsa.20014

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Statistics
Journal:
RANDOM STRUCTURES and ALGORITHMS
Volume:
24
Issue:
4
Pages:
381-396
Publication date:
2004-07-05
DOI:
EISSN:
1098-2418
ISSN:
1042-9832
URN:
uuid:98c615f6-4c9b-40b5-a799-c8505f795f98
Source identifiers:
172702
Local pid:
pubs:172702

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP