Some advances on Sidorenko's conjecture
A bipartite graph H is said to have Sidorenko's property if the probability that the uniform random mapping from V(H) to the vertex set of any graph G is a homomorphism is at least the product over all edges in H of the probability that the edge is mapped to an edge of G. In this paper, we provide three distinct families of bipartite graphs that have Sidorenko's property. First, using branching random walks, we develop an embedding algorithm which allows us to prove that bipartite graphs admitting a certain type of tree decomposition have Sidorenko's property. Second, we use the concept of locally dense graphs to prove that subdivisions of certain graphs, including cliques, have Sidorenko's property. Third, we prove that if H has Sidorenko's property, then the Cartesian product of H with an even cycle also has Sidorenko's property.
Additional Information© 2018 London Mathematical Society. Manuscript received 22 October 2015; manuscript revised 03 May 2018; version of Record online 27 June 2018; issue online 02 December 2018. The first author was supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. The second author was supported by the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) (NRF‐2016R1A5A1008055) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT (NRF‐2017R1E1A1A03070701), and KIAS internal Research Fund CG046002. This work was partially carried out while the second author was visiting Microsoft Research, Redmond and Microsoft Research, New England. The third author was supported by NSF Grant DMS‐1362326. The fourth author was supported by the ILJU Foundation of Education and Culture and by ERC Starting Grant 676632. We would like to thank Olaf Parczyk for sharing his Master's thesis with us. We would also like to thank Balázs Szegedy for a number of valuable discussions.
Submitted - 1510.06533.pdf