Exact homomorphism density domination exponents are determined for all path pairs and for even cycles against Hamiltonian-cycle graphs, with asymptotically sharp bounds for odd cycles.
Domination inequalities and dominating graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We say that a graph $H$ dominates another graph $H'$ if the number of homomorphisms from $H'$ to any graph $G$ is dominated, in an appropriate sense, by the number of homomorphisms from $H$ to $G$. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
On Domination Exponents for Pairs of Graphs
Exact homomorphism density domination exponents are determined for all path pairs and for even cycles against Hamiltonian-cycle graphs, with asymptotically sharp bounds for odd cycles.