Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d << k$ and $n = 4k d^2$ or so. The hyperedges are placed independently uniformly at random. I would like to have a handle on the behavior of the sizes of the connected components. By "size" I refer to the number of edges in the component, but understanding the number of vertices would be fine too.

For instance, if $X$ is the size of the component containing the first hyperedge, it seems like we should have $\Pr[X > t] < 1/2^t$. This is because each hyperedge has a less than $1/4$ chance of intersecting any other hyperedge, so this seems like some sort of exponentially decaying branching process.

Furthermore, it seems like there should be a negative association among component sizes: the larger one component is, the smaller the other ones are. Suppose I give each component in the graph a unique random label in $[k]$, and let $Y_i$ be the size of the component labeled $i$ (or 0 if no component has label $i$). Then I expect that $E[Y_i | Y_j = t]$ for $j \neq i$ is decreasing in $t$. Moreover, I expect that the random variable $(Y_i | Y_j = t)$ is decreasing in $t$: the variable with small $t$ dominates the variable with large $t$.

But I'm not sure how to rigorously show either property.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

The paper "The phase transition in a random hypergraph" by Michal Karoskia and Tomasz Luczak (Journal of Computational and Applied Mathematics, Volume 142, Issue 1, May 2002, Pages 125-135) seems relevant. They "prove local limit theorems for the distribution of the size of the largest component of [the random d-uniform hypergraph] in the subcritical and in the early supercritical phase." A second source could be "Critical Random Hypergraphs: The emergence of a giant set of identifiable vertices" by Christina Goldschmidt (The Annals of Probability, 2005, Vol. 33, No. 4, 1573–1600), although she follows the Poisson random hypergraph model.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.