The cores of random hypergraphs with a given degree sequence

被引:50
作者
Cooper, C [1 ]
机构
[1] Kings Coll London, Dept Comp Sci, London WC2R 2LS, England
关键词
D O I
10.1002/rsa.20040
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We study random r-uniform n vertex hypergraphs with fixed degree sequenced d = (d(1),...,d(n)), maximum degree Delta = o(n(1/24)) and total degree thetan, where theta is bounded. We give the size, number of edges and degree sequence of the kappa-cores (kappa greater than or equal to 2) up to a whp error of O(n(2/3)Delta(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. (C) 2004 Wiley Periodicals, Inc.
引用
收藏
页码:353 / 375
页数:23
相关论文
共 24 条