Georgia Institute of Technology College of Sciences

Let $K^{(r)}_{s_1,s_2,\cdots,s_r}$ be the complete $r$-partite $r$-uniform hypergraph and $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})$ be the maximum number of edges in any $n$-vertex $K^{(r)}_{s_1,s_2,\cdots,s_r}$-free $r$-uniform hypergraph. It is well-known in the graph case that $ex(n,K_{s,t})=\Theta(n^{2-1/s})$ when $t$ is sufficiently larger than $s$. We generalize the above to hypergraphs by showing that if $s_r$ is sufficiently larger than $s_1,s_2,\cdots,s_{r-1}$ then $$ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})=\Theta\left(n^{r-\frac{1}{s_1s_2\cdots s_{r-1}}}\right).$$ This is joint work with Jie Ma and Mingwei Zhang.

Fix a graph $F$. A classical problem in extremal graph theory asks about how many induced copies of $F$ can a graph with edge density $\rho$ have? The only case in which we know the asymptotic solution is when $F$ is a complete graph, and it was solved completely only recently by Reiher using the flag algebra machinery. We will consider the other cases and show some results when $F$ is a complete bipartite graph or a complete graph minus one edge. Many interesting related open problems will also be introduced. Joint work with Dhruv Mubayi and Christian Reiher.

For any positive integer $t$, a $t$-broom is a graph obtained from $K_{1,t+1}$ by subdividing an edge once.  In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $\chi(G) =  o(\omega(G)^{t+1})$, where  $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of  Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $\chi(G)$ to $7.5\omega(G)^2$, confirming a conjecture of Sivaraman. For $t\geq 3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(\omega^{t-1+\frac{2}{t+1}})$. Joint work with Xiaonan Liu, Zhiyu Wang, and Xingxing Yu.

The talk starts with Rödl's Theorem that graphs with huge chromatic number contain triangle-free subgraphs with large chromatic number. We will look at various related results and conjectures, with a notable matroid bias; the new results are joint work with Peter Nelson and Raphael Steiner.