Name
Abstract | ||
|---|---|---|
In the binomial random graph $mathcal{G}(n,p)$, when $p$ changes from $(1-varepsilon)/n$ (subcritical case) to $1/n$ and then to $(1+varepsilon)/n$ (supercritical case) for $varepsilonu003e0$, with high probability the order of the largest component increases smoothly from $O(varepsilon^{-2}log(varepsilon^3 n))$ to $Theta(n^{2/3})$ and then to $(1 pm o(1)) 2 varepsilon n$. As a natural generalisation of random graphs and connectedness, we consider the binomial random $k$-uniform hypergraph $mathcal{H}^k(n,p)$ (where each $k$-tuple of vertices is present as a hyperedge with probability $p$ independently) and the following notion of high-order connectedness. Given an integer $1 leq j leq k-1$, two sets of $j$ vertices are called emph{$j$-connected} if there is a walk of hyperedges between them such that any two consecutive hyperedges intersect in at least $j$ vertices. A $j$-connected component is a maximal collection of pairwise $j$-connected $j$-tuples of vertices. Recently, the threshold for the appearance of the giant $j$-connected component in $mathcal{H}^k(n,p)$ and its order were determined. In this article, we take a closer look at the subcritical random hypergraph. We determine the structure, order, and size of the largest $j$-connected components, with the help of a certain class of `hypertreesu0027 and related objects. In our proofs, we combine various probabilistic and enumerative techniques, such as generating functions and couplings with branching processes. Our study will pave the way to establishing a symmetry between the subcritical random hypergraph and the hypergraph obtained from the supercritical random hypergraph by deleting its giant $j$-connected component. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/1.9781611975505.12 | ANALCO |
Field | DocType | Citations |
Combinatorics,Constraint graph,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Cooley | 1 | 3 | 2.13 |
| Wenjie Fang | 2 | 28 | 7.68 |
| Nicola Del Giudice | 3 | 0 | 0.34 |
| Mihyun Kang | 4 | 163 | 29.18 |