HOẠT ĐỘNG TRONG TUẦN

A maximizing characteristic for critical configurations of chip-firing games on digraphs
Người báo cáo: Nguyễn Hoàng Thạch
Thời gian: 9h30, Thứ 5, ngày 19 tháng 1 năm 2017

Địa điểm: Phòng 201, Nhà A5, Viện Toán học

Tóm tắt: A maximizing characteristic for critical configurations of chip-firing games on digraphs Hoang Thach NGUYEN, Thi Thu Huong TRAN Aval et al. proved in [2] that starting from a critical configuration of a chip-firing game on an undirected graph, one can never achieve a stable configuration by reverse firing any non-empty subsets of its vertices. In this paper, we generalize the result to digraphs with a global sink where reverse firing subsets of vertices is replaced with reverse firing multi-subsets of vertices. Consequently, a combinatorial proof for the duality between critical configurations and superstable configurations on digraphs is given. Finally, by introducing the concept of energy vector of a configuration, we show that the critical configurations and the superstable one are the unique configurations with the greatest and smallest (w.r.t. the containment order), respectively, energy vectors in each of their equivalence classes.

Trở lại