Homomorphism and VC-dimension thresholds: spectra and separations
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.24623
curl -X POST /api/v1/records/arxiv/2608.24623/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.24623/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'