BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230627T163000
DTEND;TZID=Asia/Seoul:20230627T173000
DTSTAMP:20260419T042601
CREATED:20230601T063015Z
LAST-MODIFIED:20240707T073615Z
UID:7223-1687883400-1687887000@dimag.ibs.re.kr
SUMMARY:Chong Shangguan (上官冲)\, The hat guessing number of graphs
DESCRIPTION: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. \nIn 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. \nBased on a joint work with Noga Alon\, Omri Ben-Eliezer\, and Itzhak Tamo.
URL:https://dimag.ibs.re.kr/event/2023-06-27/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR