Sidorenko‐Type Inequalities for Pairs of Trees

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).