Some Advances in Sidorenko’s Conjecture

Joonkyung Lee

University of Oxford, UK

University of Oxford, UK

2014/09/04 *Thursday* 4PM-5PM

Room 1409

Room 1409

Sidorenko’s conjecture states that for every bipartite graph \(H\) on \(\{1,\cdots,k\}\)

\begin{eqnarray*}

\int \prod_{(i,j)\in E(H)} h(x_i, y_j) d\mu^{|V(H)|}

\ge \left( \int h(x,y) \,d\mu^2 \right)^{|E(H)|}

\end{eqnarray*}

holds, where \(\mu\) is the Lebesgue measure on \([0,1]\) and \(h\) is a bounded, non-negative, symmetric, measurable function on \([0,1]^2\). An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph \(H\) to a graph \(G\) is asymptotically at least the expected number of homomorphisms from \(H\) to the Erdos-Renyi random graph with the same expected edge density as \(G\). In this talk, we will give an overview on known results and new approaches to attack Sidorenko’s conjecture.

This is a joint work with Jeong Han Kim and Choongbum Lee.

\begin{eqnarray*}

\int \prod_{(i,j)\in E(H)} h(x_i, y_j) d\mu^{|V(H)|}

\ge \left( \int h(x,y) \,d\mu^2 \right)^{|E(H)|}

\end{eqnarray*}

holds, where \(\mu\) is the Lebesgue measure on \([0,1]\) and \(h\) is a bounded, non-negative, symmetric, measurable function on \([0,1]^2\). An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph \(H\) to a graph \(G\) is asymptotically at least the expected number of homomorphisms from \(H\) to the Erdos-Renyi random graph with the same expected edge density as \(G\). In this talk, we will give an overview on known results and new approaches to attack Sidorenko’s conjecture.

This is a joint work with Jeong Han Kim and Choongbum Lee.

Tags: 이준경