Georgia Institute of Technology College of Sciences

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.

A triangle $T'$ is $\varepsilon$-similar to another triangle $T$ if their angles pairwise differ by at most $\varepsilon$. Given a triangle $T$, $\varepsilon >0$ and $n \in \mathbb{N}$, Bárány and Füredi asked to determine the maximum number of triangles $h(n,T,\varepsilon)$ being $\varepsilon$-similar to $T$ in a planar point set of size $n$. We show that for almost all triangles $T$ there exists $\varepsilon=\varepsilon(T)>0$ such that $h(n,T,\varepsilon)=n^3/24 (1+o(1))$. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Felix Christian Clemen.