Sidorenko’s conjecture for subdivisions and theta substitutions
Abstract 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 minimised when $G$ is pseudorandom. We prove that for any graph $H$ , a graph obtained from replacing edges of $H$ by generalised 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 generalised theta graph satisfy Sidorenko’s conjecture, which extends a result of Conlon, Kim, Lee and Lee [J. Lond. Math. Soc., 2018].
Authors
- Seonghyuk Im (ORCID: https://orcid.org/0000-0003-1996-6801)
- Hong Liu (ORCID: https://orcid.org/0000-0002-5735-7321)
- Ruonan Li (ORCID: https://orcid.org/0000-0001-5419-1533)
Institutions
- Korea Advanced Institute of Science and Technology (KR)
- Northwestern Polytechnical University (CN)
- Kootenay Association for Science & Technology (CA)
- Institute for Basic Science (KR)
- Department of Mathematical Sciences (RU)
Publication Details
- Journal
- Combinatorics Probability Computing
- Published
- 2025-12-10
- DOI
- https://doi.org/10.1017/s0963548325100242
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00