CaltechAUTHORS
  A Caltech Library Service

Some advances on Sidorenko's conjecture

Conlon, David and Kim, Jeong Han and Lee, Choongbum and Lee, Joonkyung (2018) Some advances on Sidorenko's conjecture. Journal of the London Mathematical Society, 98 (3). pp. 593-608. ISSN 0024-6107. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958339

[img] PDF - Submitted Version
See Usage Policy.

389kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958339

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1112/jlms.12142DOIArticle
https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/jlms.12142PublisherArticle
https://arxiv.org/abs/1510.06533arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
National Research Foundation of KoreaNRF‐2016R1A5A1008055
National Research Foundation of KoreaNRF-2017R1E1A1A03070701
Korea Institute for Advanced StudyCG046002
Microsoft ResearchUNSPECIFIED
NSFDMS-1362326
ILJU Foundation of Education and CultureUNSPECIFIED
Issue or Number:3
Classification Code:05C35 (primary)
Record Number:CaltechAUTHORS:20190812-162958339
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958339
Official Citation:Conlon, D. , Kim, J. H., Lee, C. and Lee, J. (2018), Some advances on Sidorenko's conjecture. J. London Math. Soc., 98: 593-608. doi:10.1112/jlms.12142
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97817
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 22:58
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page