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

    • Harvard Business Review Digital Articles

    Why Build in Web3

    By: Jad Esber and Scott Duke Kominers
    • Bloomberg Opinion

    Why One Little Goof Drove Wordle Fans Nuts

    By: Scott Duke Kominers
    • Bloomberg Opinion

    The Failure of Covid.gov Is Worse Than Inexcusable

    By: Scott Duke Kominers
More from the Authors
  • Why Build in Web3 By: Jad Esber and Scott Duke Kominers
  • Why One Little Goof Drove Wordle Fans Nuts By: Scott Duke Kominers
  • The Failure of Covid.gov Is Worse Than Inexcusable By: Scott Duke Kominers
ǁ
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
  • Digital Accessibility
Copyright © President & Fellows of Harvard College