Phase transition in a random fragmentation problem with applications to computer science

DOI10.1088/0305-4470/35/32/101zbMATH Open1040.82021arXivcond-mat/0205034OpenAlexW1969116103MaRDI QIDQ4466006FDOQ4466006

Authors: David S. Dean, Satya N. Majumdar 

Publication date: 9 June 2004

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Abstract: We study a fragmentation problem where an initial object of size x is broken into m random pieces provided x>x_0 where x_0 is an atomic cut-off. Subsequently the fragmentation process continues for each of those daughter pieces whose sizes are bigger than x_0. The process stops when all the fragments have sizes smaller than x_0. We show that the fluctuation of the total number of splitting events, characterized by the variance, generically undergoes a nontrivial phase transition as one tunes the branching number m through a critical value m=m_c. For m<m_c, the fluctuations are Gaussian where as for m>m_c they are anomalously large and non-Gaussian. We apply this general result to analyze two different search algorithms in computer science.

Full work available at URL: https://arxiv.org/abs/cond-mat/0205034

Recommendations

• The size of random fragmentation trees
• On two fragmentation schemes with algebraic splitting probability
• A phase transition for the heights of a fragmentation tree
• Statistical aspects of random fragmentations
• On Random Fragmentations Arising From Binary Splitting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Cited In (10)

• On Random Fragmentations Arising From Binary Splitting
• Statistical aspects of random fragmentations
• A phase transition for the heights of a fragmentation tree
• Phase transition in a generalized Eden growth model on a tree
• Fragment size distributions in random fragmentations with cutoff
• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Dependence and phase changes in random \(m\)-ary search trees
• Moments of a non‐homogenous bi‐variate fragmentation process using integral equations tools
• Singularity analysis, Hadamard products, and tree recurrences
• The size of random fragmentation trees

This page was built for publication: Phase transition in a random fragmentation problem with applications to computer science

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