Speaker: Speaker: Maria Axenovich, KIT

Title:  Homogenous sets in bipartite graphs with forbidden induced subgraphs

Abstract:  Erd\H{o}s and Hajnal conjectured that for any graph $H$ there is a positive constant $c$ such that any $n$-vertex graph not containing $H$ as an induced subgraph has a clique or an independent set of size $\Omega(n^c)$. This conjecture remains open.  Erd\H{o}s, Hajnal, and Pach proved the conjecture restricted to bipartite graphs. Still, determining the optimal exponent $c$ remains a difficult open question even in this case. We focus on $c=1$. We explicitly describe all bipartite graphs $H$ so that any $n\times n$ bipartite graph $G$ not containing $H$ as an induced subgraph has  a bi-clique or co-bi-clique of linear size,  $an$. Moreover, we provide some bounds on the constant $a$ giving a more precise quantitative  Erd\H{o}s-Hajnal-type statement.
The talk is based on a joint work with  J-S. Sereni, R. Snyder, C. Tompkins, and L. Weber.