Random growth on a Ramanujan graph

The behavior of a certain random growth process is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the Expander Mixing Lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maximize the spectral gap. Further, we consider Erdős--...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-10
Main Authors: Boehm, Janko, Joswig, Michael, Kastner, Lars, Newman, Andrew
Format: Article
Language:English
Subjects:
Graphs
Search algorithms
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The behavior of a certain random growth process is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the Expander Mixing Lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maximize the spectral gap. Further, we consider Erdős--Rényi random graphs and compare our theoretical results with computational experiments on flip graphs of point configurations. The latter is relevant for enumerating triangulations.
ISSN:2331-8422