TY - JOUR
T1 - Edge correlations in random regular hypergraphs and applications to subgraph testing
AU - Espuny Diaz, Alberto
AU - Joos, Felix
AU - Kuhn, Daniela
AU - Osthus, Deryk
PY - 2019/10/1
Y1 - 2019/10/1
N2 - Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov, and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random d-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński, and Šileikis on the threshold for the existence of an ℓ-overlapping Hamilton cycle in a random d-regular r-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich, and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting.
AB - Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov, and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random d-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński, and Šileikis on the threshold for the existence of an ℓ-overlapping Hamilton cycle in a random d-regular r-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich, and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting.
KW - Hamiltonicity
KW - property testing
KW - random regular hypergraphs
KW - subgraph counts
KW - switching
UR - http://www.scopus.com/inward/record.url?scp=85075379884&partnerID=8YFLogxK
U2 - 10.1137/18M1177159
DO - 10.1137/18M1177159
M3 - Article
SN - 0895-4801
VL - 33
SP - 1837
EP - 1863
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 4
ER -