Behague, Natalie
ORCID: 0000-0001-6616-1606, Crudele, Gabriel, Noel, Jonathan A.
ORCID: 0000-0002-8281-8249 and Simbaqueba, Lina M.
(2025)
Sidorenko‐Type Inequalities for Pairs of Trees.
Random Structures & Algorithms, 67
(1).
ISSN 1042-9832
Abstract
Given two non‐empty graphs and , write to mean that for every graph , where is the homomorphism density function. We obtain various necessary and sufficient conditions for two trees and to satisfy and determine all such pairs on at most 8 vertices. This extends the results of Leontovich and Sidorenko from the 1980s and 1990s. Our approach applies an information‐theoretic technique to reduce the problem of showing that for two forests and to solving a linear program of Kopparty and Rossman (2011). We also characterize trees which satisfy or , where is the ‐vertex star and is the 4‐vertex path and resolve a problem of Csikvári and Lin (2015).
Metadata
| Item Type: | Article (Published) |
|---|---|
| Refereed: | Yes |
| Uncontrolled Keywords: | Combinatorics |
| Subjects: | Mathematics |
| DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Science and Health DCU Faculties and Schools > Faculty of Science and Health > School of Mathematical Sciences |
| Publisher: | John Wiley & Sons, Inc. |
| Official URL: | https://onlinelibrary.wiley.com/doi/10.1002/rsa.70... |
| Copyright Information: | Authors |
| ID Code: | 33289 |
| Deposited On: | 01 Sep 2026 10:13 by Natalie Behague . Last Modified 01 Sep 2026 10:13 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Creative Commons: Attribution 4.0 1MB |
Metrics
Altmetric Badge
Dimensions Badge
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record