Printable PDF
Department of Mathematics,
Department of Mathematics,
University of California San Diego
****************************
Combinatorics Seminar (Math 269)
Sam Spiro
Rutgers University
Clique and Berge Supersaturation for $K_{2,t}$.
Abstract:
A famous conjecture of Erd\H{o}s and Simonovits says that if $G$ is an $n$ vertex graph with much more than $\ex(n,F)$ edges, then $G$ contains about as many copies of $F$ as the random graph of the same density. In this talk we show that several natural generalizations of this conjecture fails to be true. In particular, we show that for large $t$, there exist $n$ vertex graphs with $\Theta(kn^{3/2})$ triangles such that $G$ contains a total of $k^tn^{3/2+o(1)}$ copies of $K_{2,t}$ (with the random graph of the same triangle density containing $\Theta(k^{2t/3}n^2)$ copies), and we show that this bound is essentially best possible for $k\le n^{1/2t}$. Our constructions rely on solving certain unbalanced bipartite Tur\'an problems using random polynomial graphs. This is joint work with Quentin Dubroff, Benjamin Gunby, and Bhargav Narayanan.
Host: Brendon Rhoades
May 9, 2023
4:00 PM
APM 6402
****************************
