We introduce a notion of the crux of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalizations of known results about cycles, offering an interesting paradigm of “replacing average degree by crux.” In particular, we prove that every graph contains a cycle of length linear in its crux. Long proved that every subgraph of a hypercube $Q^m$ (resp., discrete torus $C_3^m$) with average degree $d$ contains a path of length $2^{d/2}$ (resp., $2^{d/4}$) and conjectured that there should be a path of length $2^{d}-1$ (resp., $3^{d/2}-1$). As a corollary of our result, together with isoperimetric inequalities, we close these exponential gaps giving asymptotically optimal bounds on long paths in hypercubes, discrete tori, and more generally Hamming graphs. We also consider random subgraphs of $C_4$-free graphs and hypercubes, proving near optimal lower bounds on the lengths of long cycles.

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 $\ell$-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.