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...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính: Goldschmidt, C, Norris, J
Đị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