학과 세미나 및 콜로퀴엄

구분 IBS-KAIST 세미나
분류 이산수학
제목 The hat guessing number of graphs
Abstract Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. 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$ possible colors. In 2008, Butler, Hajiaghayi, Kleinberg, and Leighton asked whether the hat guessing number of the complete bipartite graph $K_{n,n}$ is at least some fixed positive (fractional) power of $n$. We answer this question affirmatively, showing that for sufficiently large $n$, $HG(K_{n,n})\ge n^{0.5-o(1)}$. Our guessing strategy is based on some ideas from coding theory and probabilistic method. Based on a joint work with Noga Alon, Omri Ben-Eliezer, and Itzhak Tamo.
일시 2023-06-27 (Tue) / 16:30 ~ 17:30 ** 날짜에 유의하세요. **
장소 Room B332, IBS (기초과학연구원)
강연언어 영어
강연자성명 Chong Shangguan
강연자소속 Shandong University
강연자홈페이지 https://faculty.sdu.edu.cn/shangguanchong/en/index
기타정보
초청인 Sang-il Oum
URL https://dimag.ibs.re.kr/event/2023-06-27/
담당자
연락처