Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • Article
  • Archiv der Mathematik

A Constant Bound for the Periods of Parallel Chip-firing Games with Many Chips

By: Paul Myer Kominers and Scott Duke Kominers
  • Format:Print
ShareBar

Abstract

We prove that any parallel chip-firing game on a graph G with at least 4|E(G)| − |V(G)| chips stabilizes, i.e., such a game has eventual period of length 1. Furthermore, we obtain a polynomial bound on the number of rounds before stabilization. This result is a counterpoint to previous results which showed that the eventual periods of parallel chip-firing games with few chips need not be polynomially bounded.

Keywords

Chip-firing; Parallel Chip-firing; Stabilization

Citation

Kominers, Paul Myer, and Scott Duke Kominers. "A Constant Bound for the Periods of Parallel Chip-firing Games with Many Chips." Archiv der Mathematik 95, no. 1 (July 2010): 9–13.
  • Find it at Harvard
  • Purchase

About The Author

Scott Duke Kominers

Entrepreneurial Management
→More Publications

More from the Authors

    • October 2023
    • American Economic Review

    Matching Mechanisms for Refugee Resettlement

    By: David Delacrétaz, Scott Duke Kominers and Alexander Teytelboym
    • July 13, 2023
    • Harvard Business Review Digital Articles

    Threads Foreshadows a Big—and Surprising—Shift in Social Media

    By: Scott Duke Kominers and Liang Wu
    • May 2023
    • Faculty Research

    Twitter Blues: Does Paid Verification Check Out?

    By: Scott Duke Kominers, Das Narayandas and Kerry Herman
More from the Authors
  • Matching Mechanisms for Refugee Resettlement By: David Delacrétaz, Scott Duke Kominers and Alexander Teytelboym
  • Threads Foreshadows a Big—and Surprising—Shift in Social Media By: Scott Duke Kominers and Liang Wu
  • Twitter Blues: Does Paid Verification Check Out? By: Scott Duke Kominers, Das Narayandas and Kerry Herman
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College