Passer à la navigation principale Passer à la recherche Passer au contenu principal

Quasirandomness in Graphs

  • Max-Planck-Institut fur Informatik

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

Jim Propp's rotor router model is a simple deterministic analogue of a random walk. Instead of distributing chips randomly, it serves the neighbors in a fixed order. We analyze the difference between Propp machine and random walk on the infinite two-dimensional grid. We show that, independent of the starting configuration, at each time, the number of chips on each vertex deviates from the expected number of chips in the random walk model by at most a constant c, which is 7.83 for clockwise rotor sequences and 7.28 otherwise. This is the first paper which demonstrates that the order in which the neighbors are served makes a difference.

langue originaleAnglais
Pages (de - à)61-64
Nombre de pages4
journalElectronic Notes in Discrete Mathematics
Volume25
Numéro de publicationSPEC. ISS.
Les DOIs
étatPublié - 1 août 2006
Modification externeOui

Empreinte digitale

Examiner les sujets de recherche de « Quasirandomness in Graphs ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation