Asymmetric Results About Graph Homomorphisms

Abstract

Many important results in extremal graph theory can be roughly summarized as “if a triangle‐free graph G$$ G $$ has certain properties, then it has a homomorphism to a triangle‐free graph Γ$$ \Gamma $$ of bounded size.” For example, bounds on homomorphism thresholds give such a statement if G$$ G $$ has sufficiently high minimum degree, and the approximate homomorphism theorem gives such a statement for all G$$ G $$ if one weakens the notion of homomorphism appropriately. In this paper, we study asymmetric versions of these results, where the assumptions on G$$ G $$ and Γ$$ \Gamma $$ need not match. For example, we prove that if G$$ G $$ is a graph with odd girth at least 9 and minimum degree at least δ|G|$$ \delta \mid G\mid $$ , then G$$ G $$ is homomorphic to a triangle‐free graph whose size depends only on δ$$ \delta $$ . Moreover, the odd girth assumption can be weakened to odd girth at least 7 if G$$ G $$ has bounded VC dimension or bounded domination number. This gives a new and improved proof of a result of Huang, Liu, Rong, and Xu. We also prove that in the asymmetric approximate homomorphism theorem, the bounds exhibit a rather surprising “double phase transition”: the bounds are super‐exponential if G$$ G $$ is only assumed to be triangle‐free, they become exponential if G$$ G $$ is assumed to have odd girth 7 or 9, and become linear if G$$ G $$ has odd girth at least 11. Our proofs use a wide variety of techniques, including entropy arguments, the Frieze–Kannan weak regularity lemma, properties of the generalized Mycielskian construction, and recent work on abundance and the asymmetric removal lemma.