{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}