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:20230613T163000
DTEND;TZID=Asia/Seoul:20230613T173000
DTSTAMP:20260419T061446
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
END:VCALENDAR