Sidorenko-Type Inequalities for Pairs of Trees

Abstract

Given two non-empty graphs $H$ and $T$, write $H\succcurlyeq T$ to mean that $t(H,G{)}^{|E(T)|}\ge t(T,G{)}^{|E(H)|}$ for every graph $G$, where $t(\cdot ,\cdot )$ is the homomorphism density function. We obtain various necessary and sufficient conditions for two trees $H$ and $T$ to satisfy $H\succcurlyeq T$ and determine all such pairs on at most 8 vertices. This extends results of Leontovich and Sidorenko from the 1980s and 90s. Our approach applies an information-theoretic technique to reduce the problem of showing that $H\succcurlyeq T$ for two forests $H$ and $T$ to solving a linear program of Kopparty and Rossman. We also characterize trees $H$ which satisfy $H\succcurlyeq S_k$ or $H\succcurlyeq P_4$, where $S_k$ is the $k$-vertex star and $P_4$ is the $4$-vertex path and resolve a problem of Csikvári and Lin.

arXiv comment54 pages