The 2-core of a Random Inhomogeneous Hypergraph

Stochastics Seminar
Thursday, November 7, 2013 - 3:05pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
The 2-core of a hypergraph is the unique subgraph where all vertices have degree at least 2 and which is the maximal induced subgraph with this property. This talk will be about the investigation of the 2-core for a particular random hypergraph model --- a model which differs from the usual random uniform hypergraph in that the vertex degrees are not identically distributed. For this model the main result proved is that as the size of the vertex set, n, tends to infinity then the number of hyperedges in the 2-core obeys a limit law, and this limit exhibits a threshold where the number of hyperedges in the 2-core transitions from o(n) to Theta(n). We will discuss aspects of the ideas involved and discuss the background motivation for the hypergraph model: factoring random integers into primes.