Premium
The cores of random hypergraphs with a given degree sequence
Author(s) -
Cooper Colin
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20040
Subject(s) - combinatorics , degree (music) , mathematics , sequence (biology) , bounded function , vertex (graph theory) , poisson distribution , upper and lower bounds , discrete mathematics , random graph , frequency partition of a graph , tree (set theory) , graph , statistics , line graph , physics , mathematical analysis , genetics , acoustics , biology , graph power
Abstract We study random r ‐uniform n vertex hypergraphs with fixed degree sequence d = ( d 1 …, d n ), maximum degree Δ = o ( n 1/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 ( n 2/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, 2004