The chromatic threshold, originating in a question of Erd\H{o}s and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to an H-free graph of bounded order. Since the work of Goddard and Lyle determined the clique case, exact homomorphism thresholds for individual non-complete forbidden graphs have remained unknown. In this paper, we extend the clique case to a larger family of forbidden graphs, determining the homomorphism threshold exactly for every graph in this family.
Xin-Qi Huang, Mingyuan Rong, C. Shangguan· 1 citation
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
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
