Other formats:
BibTeX
LaTeX
RIS
@article{1860111,
author = {Cooley, Oliver and Garbe, Frederik and Hng, Eng Keat and Kang, Mihyun and SanhuezaandMatamala, Nicolás and Zalla, Julian},
article_number = {4},
doi = {http://dx.doi.org/10.1137/20M1345712},
keywords = {random hypergraphs; paths; phase transition; search algorithm},
language = {eng},
issn = {0895-4801},
journal = {SIAM Journal on Discrete Mathematics},
title = {Longest Paths in Random Hypergraphs},
url = {https://doi.org/10.1137/20M1345712},
volume = {35},
year = {2021}
}
TY - JOUR
ID - 1860111
AU - Cooley, Oliver - Garbe, Frederik - Hng, Eng Keat - Kang, Mihyun - Sanhueza-Matamala, Nicolás - Zalla, Julian
PY - 2021
TI - Longest Paths in Random Hypergraphs
JF - SIAM Journal on Discrete Mathematics
VL - 35
IS - 4
SP - 2430-2458
EP - 2430-2458
SN - 08954801
KW - random hypergraphs
KW - paths
KW - phase transition
KW - search algorithm
UR - https://doi.org/10.1137/20M1345712
N2 - Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the \tt Pathfinder algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
ER -
COOLEY, Oliver, Frederik GARBE, Eng Keat HNG, Mihyun KANG, Nicolás SANHUEZA-MATAMALA and Julian ZALLA. Longest Paths in Random Hypergraphs. \textit{SIAM Journal on Discrete Mathematics}. 2021, vol.~35, No~4, p.~2430-2458. ISSN~0895-4801. Available from: https://dx.doi.org/10.1137/20M1345712.
|
