Sidorenko-Type Inequalities for Pairs of Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909450099490816 |
|---|---|
| author | Behague, Natalie Crudele, Gabriel Noel, Jonathan A. Simbaqueba, Lina M. |
| author_facet | Behague, Natalie Crudele, Gabriel Noel, Jonathan A. Simbaqueba, Lina M. |
| contents | Given two non-empty graphs $H$ and $T$, write $H\succcurlyeq T$ to mean that $t(H,G)^{|E(T)|}\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_16542 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sidorenko-Type Inequalities for Pairs of Trees Behague, Natalie Crudele, Gabriel Noel, Jonathan A. Simbaqueba, Lina M. Combinatorics Discrete Mathematics 05C35, 05C05 Given two non-empty graphs $H$ and $T$, write $H\succcurlyeq T$ to mean that $t(H,G)^{|E(T)|}\geq 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. |
| title | Sidorenko-Type Inequalities for Pairs of Trees |
| topic | Combinatorics Discrete Mathematics 05C35, 05C05 |
| url | https://arxiv.org/abs/2305.16542 |