Minimum-degree thresholds ask when excluding a fixed graph $H$ forces a dense graph to admit a simple global description. For each fixed chromatic number, the chromatic threshold has only three possible values. We show that this finite-spectrum phenomenon is special to chromatic threshold: already among $3$-chromatic graphs, both the homomorphism and VC-dimension thresholds have infinite spectra and are nonmonotone under taking induced subgraphs. For complete tripartite graphs with a singleton part, we prove $\delta_{\mathrm{hom}}(K_{1,s,t}) \ge \max\left\{\frac13,\frac{s}{1+s+t}\right\}$, with equality for an infinite range of $s,t$; in particular, $\delta_{\mathrm{hom}}(K_{1,s,s})=s/(2s+1)$ for every $s\ge2$. More generally, for every $r\ge3$, the value $(r-2)/(r-1)$ is an accumulation point of the homomorphism thresholds of $r$-chromatic graphs. For maximal $H$-free graphs, we determine the VC-dimension threshold of every complete tripartite graph and prove that it is positive for every nonbipartite $H$, yielding in particular the exact value for every odd cycle. We also classify the chromatic threshold under an a priori VC-dimension bound. Together with known blowup-threshold results, our theorems reveal that $\delta_\chi,\delta_{\mathrm{hom}},\delta_{\mathrm{VC}}$, and $\delta_{\mathrm B}$ are \emph{pairwise distinct}: bounded colorability, homomorphic compressibility, neighborhood complexity, and exact blowup structure are genuinely different forms of global simplicity. The proofs develop random and grid-based obstructions to bounded homomorphic images, saturated gadgets that preserve high VC-dimension under maximal completion, and a core-orientation method for raising minimum degree while preserving $H$-freeness.
Lior Gishboliner, Xinqi Huang, Hong Liu· 0 citations
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.
Lior Gishboliner, Eoin Hurley, Yuval Wigderson· Random Structures & Algo...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
