The hat guessing number of random graphs with constant edge-chosen probability

arXiv2302.04122MaRDI QIDQ6425848FDOQ6425848

Authors: Lanchao Wang, Yaojun Chen 

Publication date: 8 February 2023

Abstract: Let $G$ be a graph with $n$ vertices. The {em hat guessing number} of $G$ is defined in terms of the following game: There are $n$ players and one opponent. The opponent will wear one of the $q$ hats of different colors on the player's head. At this time, the player can only see the player's hat color at the adjacent vertex, and communication between players is not allowed. Once players are assigned hats, each player must guess the color of his hat at the same time. If at least one player guesses right, then they will win collectively. Given a graph $G$, its hat guessing number $HG(G)$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ different colors. Let $mathcalG(n,p)$ denote the ErdH{o}s-R'{e}nyi random graphs with $n$ vertices and edge-chosen probability $pin(0,1)$. Alon-Chizewer and Bosek-Dudek-Farnik-Grytczuk-Mazur investigated the lower and upper bound for $HG(G)$ when $GinmathcalG(n,1/2)$, respectively. In this paper, we extends their results by showing that for any constant number $p$, we have $n^{1-o(1)}leHG(G)le(1-o(1))n$ with high probability when $GinmathcalG(n,p)$.

This page was built for publication: The hat guessing number of random graphs with constant edge-chosen probability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6425848)