Speaker : 1. Dr. Hong-Bin Chen (Academia Sinica) 2. Dr. Ko-Wei Lih (Academia Sinica)
Title : 1. Entropy compression method applied to graph colorings 2. Survey on equitable coloring of graphs
Time : 2014-11-28 (Fri) 14:00 - 17:00
Place : Seminar Room 617, Institute of Mathematics (NTU Campus)
Abstract: 1. Lovasz local lemma (LLL) is a powerful tool to prove existence of combinatorial objects satisfying certain constraints. Recently, Moser and Tardos gave a constructive proof for LLL, i.e., an algorithmic version of LLL. This method, called entropy compression method, seems to be applicable whenever LLL is, and to be with the benefits of tighter bounds. However, it is still unclear why and when entropy compression method works and provides a tighter bound than that by LLL. In this talk, I will introduce entropy compression method applied to graph colorings.