Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

Sidorenko‐Type Inequalities for Pairs of Trees

Behague, Natalie orcid logoORCID: 0000-0001-6616-1606, Crudele, Gabriel, Noel, Jonathan A. orcid logoORCID: 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:

[thumbnail of 2305.16542v2.pdf]
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