BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
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:20230613T163000
DTEND;TZID=Asia/Seoul:20230613T173000
DTSTAMP:20260419T042604
CREATED:20230410T043558Z
LAST-MODIFIED:20240707T073632Z
UID:6992-1686673800-1686677400@dimag.ibs.re.kr
SUMMARY:Minho Cho (조민호)\, Strong Erdős-Hajnal property on chordal graphs and its variants
DESCRIPTION:A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$\, either $G$ or its complement has $K_{m\, m}$ as a subgraph where $m \geq \left\lfloor c|V(G)| \right\rfloor$. We prove that the class of chordal graphs satisfies SEH-property with constant $c = 2/9$. \nOn the other hand\, a strengthening of SEH-property which we call the colorful Erdős-Hajnal property was discussed in geometric settings by Alon et al.(2005) and by Fox et al.(2012). Inspired by their results\, we show that for every pair $F_1\, F_2$ of subtree families of the same size in a tree $T$ with $k$ leaves\, there exist subfamilies $F’_1 \subseteq F_1$ and $F’_2 \subseteq F_2$ of size $\theta \left( \frac{\ln k}{k} \left| F_1 \right|\right)$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect. Our results are asymptotically optimal. \nJoint work with Andreas Holmsen\, Jinha Kim and Minki Kim.
URL:https://dimag.ibs.re.kr/event/2023-06-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230620T163000
DTEND;TZID=Asia/Seoul:20230620T173000
DTSTAMP:20260419T042604
CREATED:20230410T120415Z
LAST-MODIFIED:20240705T164137Z
UID:6995-1687278600-1687282200@dimag.ibs.re.kr
SUMMARY:Guanghui Wang (王光辉)\, Embeddings in uniformly dense  hypergraphs
DESCRIPTION:An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in uniformly dense hypergraphs. In precise\, we will mention the uniform Turan density of some hypergraphs.
URL:https://dimag.ibs.re.kr/event/2023-06-23/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230627T163000
DTEND;TZID=Asia/Seoul:20230627T173000
DTSTAMP:20260419T042604
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