Twin peaks
From MaRDI portal
Publication:5113945
DOI10.1002/RSA.20883zbMATH Open1436.05091arXiv1606.08025OpenAlexW4210449381MaRDI QIDQ5113945FDOQ5113945
Publication date: 19 June 2020
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Abstract: We study random labelings of graphs conditioned on a small number (typically one or two) peaks, i.e., local maxima. We show that the boundaries of level sets of a random labeling of a square with a single peak have dimension 2, in a suitable asymptotic sense. The gradient line of a random labeling of a long ladder graph conditioned on a single peak consists mostly of straight line segments. We show that for some tree-graphs, if a random labeling is conditioned on exactly two peaks then the peaks can be very close to each other. We also study random labelings of regular trees conditioned on having exactly two peaks. Our results suggest that the top peak is likely to be at the root and the second peak is equally likely, more or less, to be any vertex not adjacent to the root.
Full work available at URL: https://arxiv.org/abs/1606.08025
Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Cited In (1)
This page was built for publication: Twin peaks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113945)
