Speaker
Description
A graph class $\mathcal{G}$ has the strong EH(Erd\H{o}s-Hajnal) 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 c \left| V(G) \right|$. We prove that the chordal graphs satisfy strong Erd\H{o}s-Hajnal property with constant $c = 2/9$.
On the other hand, a strengthening of strong EH which we call the colorful strong EH property was discussed in geometric settings by Alon, Pach, Pinchasi, Radoi\v{c}i\'c, Sharir in 2005 and by Fox, Gromov, Lafforgue, Naor, Pach in 2012. Inspired by their results, we show that for every pair $\mathcal{F}_1, \mathcal{F}_2$ of subtree families of the same size in a tree with $k$ leaves, there exists subfamilies $\mathcal{F}'_1 \subseteq \mathcal{F}_1$ and $\mathcal{F}'_2 \subseteq \mathcal{F}_2$ of size $\frac{\ln k}{20 k} \left| \mathcal{F}_1 \right|$ such that either every pair of representatives from distinct subfamilies intersect or every such pair do not intersect.
Finally, we propose some questions on the intersection pattern of convex sets in terms of Erd\H{o}s-Hajnal type properties.
