Sidorenko-Type Inequalities for Pairs of Trees

2023/05/25 by Natalie Behague, Behague, Natalie, Gabriel Crudele +5 · 1 citation
Mathematics · Computer Science · Physics and Astronomy · #Graph theory and applications #Advanced Graph Theory Research #Complex Network Analysis Techniques

paper · pdf · doi:10.48550/arxiv.2305.16542

Abstract

Given two non-empty graphs H and T, write H\succcurlyeq T to mean that t(H,G)^|E(T)|≥ t(T,G)^|E(H)| for every graph G, where t(⋅,⋅) 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₄, where S_k is the k-vertex star and P₄ is the 4-vertex path and resolve a problem of Csikvári and Lin.

Cited by

• Entropy methods in combinatorics

Related

• A very short proof of Sidorenko's inequality for counts of homomorphism between graphs
• Two Approaches to Sidorenko's Conjecture
• Non-trivial squares and Sidorenko's conjecture
• Sidorenko-Type Inequalities for Even Subdivisions over Finite Abelian Groups
• Sidorenko's conjecture for higher tree decompositions