The @math -core, defined as the largest subgraph of minimum degree @math , of the random graph @math has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [JCTB 67 (1996) 111--151] determined the threshold @math for the appearance of an extensive @math -core. Here we derive a multi-type Galton-Watson branching process that describes precisely how the @math -core is embedded into the random graph for any @math and any fixed average degree @math . This generalises prior results on, e.g., the internal structure of the @math -core.
 We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of a k-core in a random r-uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r-SAT, r ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 We study random r-uniform n vertex hypergraphs with fixed degree sequence d = (d1…,dn), maximum degree D = o(n1 24) and total degree tn, where t is bounded. We give the size, number of edges and degree sequence of the k ≥ 2) up to a whp error of O(n2 3 D4 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 The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold λc for the emergence of a non-trivial k-core in the random graph G(n, λ n), and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or 'scale-free' graph with a parameter c controlling the overall density of edges. For each k ≥ 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is e above the threshold. In contrast to G(n, λ n), this fraction tends to 0 as e➝0.