The cores of random hypergraphs with a given degree sequence
Author:
- 28 October 2004
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 25 (4) , 353-375
Abstract
We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d1…,dn), maximum degree Δ = o(n1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n2/3 Δ4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004Keywords
This publication has 18 references indexed in Scilit:
- Sudden Emergence of a Giantk-Core in a Random GraphJournal of Combinatorial Theory, Series B, 1996
- A Family of Perfect Hashing MethodsThe Computer Journal, 1996
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- Random graphs and systems of linear equations in finite fieldsRandom Structures & Algorithms, 1994
- The birth of the giant componentRandom Structures & Algorithms, 1993
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990
- On tree census and the giant component in sparse random graphsRandom Structures & Algorithms, 1990
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978