Essential edges in Poisson random hypergraphs
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 h...
Những tác giả chính: | , |
---|---|
Định dạng: | Journal article |
Ngôn ngữ: | English |
Được phát hành: |
2004
|
_version_ | 1826286662752141312 |
---|---|
author | Goldschmidt, C Norris, J |
author_facet | Goldschmidt, C Norris, J |
author_sort | Goldschmidt, C |
collection | OXFORD |
description | 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 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. |
first_indexed | 2024-03-07T01:47:05Z |
format | Journal article |
id | oxford-uuid:98c615f6-4c9b-40b5-a799-c8505f795f98 |
institution | University of Oxford |
language | English |
last_indexed | 2024-03-07T01:47:05Z |
publishDate | 2004 |
record_format | dspace |
spelling | oxford-uuid:98c615f6-4c9b-40b5-a799-c8505f795f982022-03-27T00:09:21ZEssential edges in Poisson random hypergraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:98c615f6-4c9b-40b5-a799-c8505f795f98EnglishSymplectic Elements at Oxford2004Goldschmidt, CNorris, JConsider 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 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. |
spellingShingle | Goldschmidt, C Norris, J Essential edges in Poisson random hypergraphs |
title | Essential edges in Poisson random hypergraphs |
title_full | Essential edges in Poisson random hypergraphs |
title_fullStr | Essential edges in Poisson random hypergraphs |
title_full_unstemmed | Essential edges in Poisson random hypergraphs |
title_short | Essential edges in Poisson random hypergraphs |
title_sort | essential edges in poisson random hypergraphs |
work_keys_str_mv | AT goldschmidtc essentialedgesinpoissonrandomhypergraphs AT norrisj essentialedgesinpoissonrandomhypergraphs |