Id: arxiv/2608.24623 Url: https://arxiv.org/abs/2608.24623 Tags: math.CO Score: 0 Title: Homomorphism and VC-dimension thresholds: spectra and separations Domain: math.CO Source: arxiv Authors: Lior Gishboliner, Xinqi Huang, Hong Liu Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-25 Page: https://delphi.science/r/arxiv/2608.24623 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 $δ_{\mathrm{hom}}(K_{1,s,t}) \ge \max\left\{\frac13,\frac{s}{1+s+t}\right\}$, with…