Subcritical Random Hypergraphs, High-Order Components, and Hypertrees
| Autor: | Oliver Cooley, Wenjie Fang, Mihyun Kang, Nicola Del Giudice |
|---|---|
| Přispěvatelé: | Institute of Discrete Mathematics, Graz University of Technology [Graz] (TU Graz), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Technische Universität Graz (TU Graz), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Phase transition
Binomial (polynomial) General Mathematics 0102 computer and information sciences 01 natural sciences 010305 fluids & plasmas Combinatorics 03 medical and health sciences 010104 statistics & probability 0103 physical sciences [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics 0101 mathematics High order ComputingMilieux_MISCELLANEOUS 030304 developmental biology Mathematics Random graph Discrete mathematics 0303 health sciences Order (ring theory) [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] 05C80 05C65 05C05 010201 computation theory & mathematics Combinatorics (math.CO) |
| Zdroj: | SIAM Journal on Discrete Mathematics SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2020, 34 (4), pp.2033-2062. ⟨10.1137/18M1221527⟩ Scopus-Elsevier ANALCO |
| ISSN: | 0895-4801 |
| DOI: | 10.1137/18M1221527⟩ |
| Popis: | 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 $\varepsilon>0$, 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 `hypertrees' 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. Comment: 27 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|