- Series
- Graph Theory Seminar
- Time
- Tuesday, February 13, 2024 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Daniel Brosch – University of Klagenfurt – daniel.brosch@aau.at – https://www.danielbrosch.com/
- Organizer
- Evelyne Smith-Roberge
Sidorenko's conjecture can be formulated as "Let $H$ be a bipartite graph, and $\rho\in [0,1]$. Of all the graphs with edge density $\rho$, the graph(-limit) obtained by picking edges uniformly at random minimizes the homomorphism density of $H$." This conjecture, first formulated in 1991 by Sidorenko, has received considerable attention over the last decades, and yet remains open in the general case.
It was shown recently [Blekherman, Raymond, Singh, Thomas, 2020] that sums-of-squares in Razborov's flag algebra are not strong enough to prove even small, known cases of the conjecture. To circumvent this, we introduce a novel kind of derivation of flags. Due to their combinatoric nature, we can use them to systematically gain knowledge on global minimizers of problems in extremal graph theory. We combine them with the flag algebra method to find new proofs for various cases of Sidorenko's conjecture.