## Negative Association of Component Size in Random Hypergraph

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.

-

## 1 Answer

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.

-