ONE-DEPENDENT COLORINGS OF THE STAR GRAPH

• 成果类型: Article
• 署名作者: Ligget, Thomas m.; Tang, Wenpin
• 署名单位: University of California System; University of California Los Angeles; Columbia University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1920
• 发表日期: 2023
• 页码: 4341-4365
• 关键词: permutations; statistics

摘要

This paper is concerned with symmetric 1-dependent colorings of the dray star graph S-d for d >= 2. We compute the critical point of the 1-dependent hard-core processes on S-d, which gives a lower bound for the number of colors needed for a 1-dependent coloring of S-d. We provide an explicit construction of a 1-dependent q-coloring for any q >= 5 of the infinite subgraph S-(1,1,infinity)(3), which is symmetric in the colors and whose restriction to any path is some symmetric 1-dependent q-coloring. We also prove that there is no such coloring of S-(1,1,infinity)(3) with q = 4 colors. A list of open problems are presented.