Negative Association of Component Size in Random Hypergraph - MathOverflow 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 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 Answer by Joseph O'Rourke for Negative Association of Component Size in Random Hypergraph 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>