Crux and long cycles in graphs

DOI10.1137/21M143488XMaRDI QIDQ6372014arXivFDO

Authors John Haslegrave, Jie Hu, Jaehoon Kim, Hong Liu, Bingyu Luan, Guanghui Wang

Publication date 5 July 2021

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38) Expander graphs (05C48)

Abstract: We introduce a notion of the emph{crux} of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalisations of known results about cycles, offering an interesting paradigm of `replacing average degree by crux'. In particular, we prove that emph{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 bounds on lengths of long cycles.

This page was built for publication: Crux and long cycles in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6372014)