Computer Science – Discrete Mathematics
Scientific paper
2010-06-08
Computer Science
Discrete Mathematics
9 pages
Scientific paper
A team of players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his or her own hat color by looking at the hat colors of other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom she or he is connected by an arc. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The team aims to maximize the probability of a win, and this maximum is called the hat number of the graph. Previous works focused on the problem on complete graphs and on undirected graphs. Some cases were solved, e.g., complete graphs of certain orders, trees, cycles, bipartite graphs. These led Uriel Feige to conjecture that the hat number of any graph is equal to the hat number of its maximum clique. We show that the conjecture does not hold for directed graphs, and build, for any fixed clique number, a family of directed graphs of asymptotically optimal hat number. We also determine the hat number of tournaments to be one half.
Hod Rani
Krzywkowski Marcin
No associations
LandOfFree
The hat problem on a directed graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The hat problem on a directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hat problem on a directed graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-30512