pith. sign in

arxiv: 1803.02809 · v1 · pith:BWDXGD5Vnew · submitted 2018-03-07 · 🧮 math.CO · math.PR

The size of the giant component in random hypergraphs: a short proof

classification 🧮 math.CO math.PR
keywords componentcomponentsedgesgianthypergraphsproofrandomsets
0
0 comments X
read the original abstract

We consider connected components in $k$-uniform hypergraphs for the following notion of connectedness: given integers $k\ge 2$ and $1\le j \le k-1$, two $j$-sets (of vertices) lie in the same $j$-component if there is a sequence of edges from one to the other such that consecutive edges intersect in at least $j$ vertices. We prove that certain collections of $j$-sets constructed during a breadth-first search process on $j$-components in a random $k$-uniform hypergraph are reasonably regularly distributed with high probability. We use this property to provide a short proof of the asymptotic size of the giant $j$-component shortly after it appears.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.