Sidorenko's conjecture for subdivisions and theta substitutions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910580422475776 |
|---|---|
| author | Im, Seonghyuk Li, Ruonan Liu, Hong |
| author_facet | Im, Seonghyuk Li, Ruonan Liu, Hong |
| contents | The famous Sidorenko's conjecture asserts that for every bipartite graph $H$, the number of homomorphisms from $H$ to a graph $G$ with given edge density is minimized when $G$ is pseudorandom. We prove that for any graph $H$, a graph obtained from replacing edges of $H$ by generalized theta graphs consisting of even paths satisfies Sidorenko's conjecture, provided a certain divisibility condition on the number of paths. To achieve this, we prove unconditionally that bipartite graphs obtained from replacing each edge of a complete graph with a generalized theta graph satisfy Sidorenko's conjecture, which extends a result of Conlon, Kim, Lee and Lee [J. Lond. Math. Soc., 2018]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03491 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sidorenko's conjecture for subdivisions and theta substitutions Im, Seonghyuk Li, Ruonan Liu, Hong Combinatorics The famous Sidorenko's conjecture asserts that for every bipartite graph $H$, the number of homomorphisms from $H$ to a graph $G$ with given edge density is minimized when $G$ is pseudorandom. We prove that for any graph $H$, a graph obtained from replacing edges of $H$ by generalized theta graphs consisting of even paths satisfies Sidorenko's conjecture, provided a certain divisibility condition on the number of paths. To achieve this, we prove unconditionally that bipartite graphs obtained from replacing each edge of a complete graph with a generalized theta graph satisfy Sidorenko's conjecture, which extends a result of Conlon, Kim, Lee and Lee [J. Lond. Math. Soc., 2018]. |
| title | Sidorenko's conjecture for subdivisions and theta substitutions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.03491 |