On June 13, 2023, Minho Cho (조민호) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on determining the maximum size of a pure pair in graph classes regarding the strong Erdős-Hajnal property. The title of his talk was “Strong Erdős-Hajnal property on chordal graphs and its variants.”

## Minho Cho (조민호), Strong Erdős-Hajnal property on chordal graphs and its variants

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.

## Welcome Younjin Kim (김연진) and Minho Cho (조민호), new members of the IBS Extremal Combinatorics and Probability Group

The IBS discrete mathematics group welcomes Dr. Younjin Kim (김연진) and Dr. Minho Cho (조민호), new research fellows at the IBS Extremal Combinatorics and Probability Group.

Dr. Younjin Kim received her Ph.D. from UIUC in 2011 under the supervision of Prof. Zoltan Furedi.

Dr. Minho Cho received his Ph.D. from KAIST in 2023 under the supervision of Prof. Andreas Holmsen.

Both start their positions on March 1.