Long induced paths in a configuration model
From MaRDI portal
Large deviations (60F10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamic continuum models (systems of particles, etc.) in time-dependent statistical mechanics (82C21)
Abstract: In an article published in 1987 in Combinatorica cite{MR918397}, Frieze and Jackson established a lower bound on the length of the longest induced path (and cycle) in a sparse random graph. Their bound is obtained through a rough analysis of a greedy algorithm. In the present work, we provide a sharp asymptotic for the length of the induced path constructed by their algorithm. To this end, we introduce an alternative algorithm that builds the same induced path and whose analysis falls into the framework of a previous work by the authors on depth-first exploration of a configuration model cite{EFMN}. We also analyze an extension of our algorithm that mixes depth-first and breadth-first explorations and generates -induced paths.
This page was built for publication: Long induced paths in a configuration model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370831)
