most recent 30 from http://mathoverflow.net 2013-05-22T03:41:40Z http://mathoverflow.net/feeds/question/29469 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29469/negative-association-of-component-size-in-random-hypergraph Eric Price 2010-06-25T05:28:48Z 2010-06-25T10:53:28Z

<p>I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d &lt;&lt; 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.</p> <p>For instance, if $X$ is the size of the component containing the first hyperedge, it seems like we should have $\Pr[X > t] &lt; 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.</p> <p>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$.</p> <p>But I'm not sure how to rigorously show either property.</p>

http://mathoverflow.net/questions/29469/negative-association-of-component-size-in-random-hypergraph/29492#29492 Joseph O'Rourke 2010-06-25T10:52:21Z 2010-06-25T10:52:21Z

<p>The paper "<a href="http://portal.acm.org/citation.cfm?id=586795.586806" rel="nofollow">The phase transition in a random hypergraph</a>" by Michal Karoskia and Tomasz Luczak (<em>Journal of Computational and Applied Mathematics</em>, 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 <em>d</em>-uniform hypergraph] in the subcritical and in the early supercritical phase." A second source could be "<a href="http://arxiv.org/pdf/math/0401208" rel="nofollow">Critical Random Hypergraphs: The emergence of a giant set of identifiable vertices</a>" by Christina Goldschmidt (<em>The Annals of Probability</em>, 2005, Vol. 33, No. 4, 1573–1600), although she follows the Poisson random hypergraph model.</p>