組合數學研討會
主講者: | 1. 黃國卿 教授 (靜宜大學財務與計算數學系) 2. 賴欣豪 教授 (國立高雄師範大學數學系) |
講題: | 1. On the Near-factor-critical Graphs 2. An Intorduction of Entropy Compression |
時間: | 2014-05-09 (Fri.) 14:00 - 16:15 |
地點: | 數學所 617 研討室 (台大院區) |
Abstract: | 1. A near-factor of a finite simple graph $G$ is a matching that saturates all vertices except one. A graph $G$ is said to be near-factor-critical if the deletion of any vertex from $G$ results in a subgraph that has a near-factor. We prove that a connected graph $G$ is near-factor-critical if and only if it has a perfect matching. We also characterize disconnected near-factor-critical graphs.
2. The entropy compression is a new developed and inspiring method. And it was widely discussed by combinatorists. For example, see [6]. In this talk, I will describe the idea behind the method. Also, I will introduce the results obtained by entropy compression and sketch their proofs in [1],[2],[3],[5]. References: [1] V. Dujmovic, G. Joret, J. Kozik, D. R. Wood, Nonrepetitive colouring via entropy compression, arXiv:1112.5524, 2012. [2] J. Grytczuk, J. Kozik, P. Micek, New approach to nonrepetitive sequences, Random Structures Algorithms 42 (2013), 214-225. [3] L. Esperet, A. Parreau, Acyclic edge-coloring using entropy compression, Eu- ropean J. Combin. 34 (2013), 1019-1027. [4] R. Moser, G. Tardos, A constructive proof of the general Lovasz local lemma, J. ACM 57 (2010), Art. 11. [5] Jakub Przyby lo, On the Facial Thue Choice Index via Entropy Compression, J. Graph Theory, DOI: 10.1002/jgt.21781. [6] T. Tao, Mosers entorpy compression argument (blog post), available at: http://terrytao.wordpress.com/2009/08/05/mosers-entropy-compression- argument/. |
|| Close window || |