Geodesic
Cliques and constructors in “Hats” game. II
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 97-118 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We analyze the following general variant of deterministic “Hats” game. Several sages wearing colored hats occupy the vertices of a graph, $k$th sage can have hats of one of $h(k)$ colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbours without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. We demonstarte here winning strategies fo the sages on complete graphs, and analyze the Hats game on almost complete graphs. We prove also a collection of theorems demonstrating how one can construct new graphs for which the sages win. 
@article{ZNSL_2019_488_a4,
     author = {K. P. Kokhas and A. S. Latyshev and V. I. Retinskiy},
     title = {Cliques and constructors in {{\textquotedblleft}Hats{\textquotedblright}} {game.~II}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {97--118},
     year = {2019},
     volume = {488},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a4/}
}
TY  - JOUR
AU  - K. P. Kokhas
AU  - A. S. Latyshev
AU  - V. I. Retinskiy
TI  - Cliques and constructors in “Hats” game. II
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 97
EP  - 118
VL  - 488
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a4/
LA  - ru
ID  - ZNSL_2019_488_a4
ER  - 
%0 Journal Article
%A K. P. Kokhas
%A A. S. Latyshev
%A V. I. Retinskiy
%T Cliques and constructors in “Hats” game. II
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 97-118
%V 488
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a4/
%G ru
%F ZNSL_2019_488_a4
K. P. Kokhas; A. S. Latyshev; V. I. Retinskiy. Cliques and constructors in “Hats” game. II. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 97-118. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a4/

[1] S. Butler, M. T. Hajiaghayi, R. D. Kleinberg, T. Leighton, “Hat guessing games”, SIAM review, 51 (2009), 399–413 | DOI | MR | Zbl

[2] M. Gadouleau, N. Georgiou, “New constructions and bounds for winkler's hat game”, SIAM J. Discr. Math., 29 (2015), 823–834 | DOI | MR | Zbl

[3] M. Gadouleau, “Finite dynamical systems, hat games, and coding theory”, J. Discr. Math. SIAM, 32:3 (2018), 1922–1945 | DOI | MR | Zbl

[4] W. W. Szczechla, “The three colour hat guessing game on cycle graphs”, Electronic J. Combinatorics, 26 (2017), P1.37, arXiv: 1412.3435 | MR

[5] M. Farnik, A hat guessing game, Jagellonian University, 2015

[6] Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo, The hat guessing number of graphs, 2018, arXiv: 1812.09752

[7] B. Bosek, A. Dudek, M. Farnik, J. Grytczuk, P. Mazur, “Hat Chromatic Number of Graphs”, J. CoRR, 2019, arXiv: abs/1905.04108v1

[8] K. P. Kokhas, A. S. Latyshev, “Na kakikh grafakh mudretsy mogut ugadat tsvet khotya by odnoi shlyapy”, Zap. nauchn. semin. POMI, 464, 2017 http://www.pdmi.ras.ru/znsl/2017/v464.html

[9] K. P. Kokhas, A. S. Latyshev, “Kliki i konstruktory v igre “Hats”. I”, Zap. nauchn. semin. POMI, 488, 2019, 66–96