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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
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 |