학과 세미나 및 콜로퀴엄

구분 IBS-KAIST 세미나
분류 이산수학
제목 Strong Erdős-Hajnal property on chordal graphs and its variants
Abstract 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$. On 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. Joint work with Andreas Holmsen, Jinha Kim and Minki Kim.
일시 2023-06-13 (Tue) / 16:30 ~ 17:30
장소 Room B332, IBS (기초과학연구원)
강연언어 영어
강연자성명 조민호
강연자소속 IBS 극단조합및확률그룹
강연자홈페이지
기타정보
초청인 Sang-il Oum
URL https://dimag.ibs.re.kr/event/2023-06-13/
담당자
연락처