수학과

안녕하세요. 수학과입니다.

 

03/30 (목)에 열리는 위상조합 세미나에 대해 안내드립니다.

많은 관심과 참여 요청드립니다.

 

 

------------------------------------------------------

 

1. 연사 : 조민호 (IBS ECOPRO)

2. 일시 : 3월 30일 목요일 11:00 -- 12:00

3. 방법 : Zoom 활용 온라인 강연회 (온라인 접속 정보는 홈페이지의 조직위원에게 문의바랍니다.)

 

4. 제목 : Strong Erd\H{o}s-Hajnal property on chordal graphs and its variants

 

5. 초록 : A graph class $\mathcal{G}$ has the strong Erd\H{o}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 satisfy SEH-property with constant $c = 2/9$.

 

On the other hand, a strengthening of SEH-property which we call the colorful Erd\H{o}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 exists 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.

 

Finally, we propose some questions on Erd\H{o}s-Hajnal type properties of various graph classes. Joint work with Andreas~Holmsen,~Jinha~Kim~and~Minki~Kim.

 

------------------------------------------------------