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 prov...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
London Mathematical Society
2018
|
| _version_ | 1797074335084576768 |
|---|---|
| author | Conlon, D Kim, J Lee, C Lee, J |
| author_facet | Conlon, D Kim, J Lee, C Lee, J |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:34:37Z |
| format | Journal article |
| id | oxford-uuid:6d3935a1-02fb-46ab-8127-24f8824f546c |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:34:37Z |
| publishDate | 2018 |
| publisher | London Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:6d3935a1-02fb-46ab-8127-24f8824f546c2022-03-26T19:16:26ZSome advances on Sidorenko's conjectureJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6d3935a1-02fb-46ab-8127-24f8824f546cSymplectic Elements at OxfordLondon Mathematical Society2018Conlon, DKim, JLee, CLee, JA 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. |
| spellingShingle | Conlon, D Kim, J Lee, C Lee, J Some advances on Sidorenko's conjecture |
| title | Some advances on Sidorenko's conjecture |
| title_full | Some advances on Sidorenko's conjecture |
| title_fullStr | Some advances on Sidorenko's conjecture |
| title_full_unstemmed | Some advances on Sidorenko's conjecture |
| title_short | Some advances on Sidorenko's conjecture |
| title_sort | some advances on sidorenko s conjecture |
| work_keys_str_mv | AT conlond someadvancesonsidorenkosconjecture AT kimj someadvancesonsidorenkosconjecture AT leec someadvancesonsidorenkosconjecture AT leej someadvancesonsidorenkosconjecture |