Showing 2026Show all
3 papers · 1 filter
math.CO2026
Homomorphism and VC-dimension thresholds: spectra and separations
Lior Gishboliner, Xinqi Huang, Hong Liu
Minimum-degree thresholds ask when excluding a fixed graph forces a dense graph to admit a simple global description. For each fixed chromatic number, the chromatic threshold h…
math.CO2026
On the spectrum and structure of blowup thresholds
Xinqi Huang, Hong Liu, Mingyuan Rong
The chromatic threshold of Erdős and Simonovits asks when a minimum-degree condition forces every \(H\)-free graph to have bounded chromatic number. Thomassen's homomorphism thresh…
math.CO2026
Triangle packings in randomly perturbed graphs
Xinbu Cheng, Hong Liu, Lanchao Wang +1
The longstanding Nash-Williams conjecture asserts that every -divisible graph with admits a triangle decomposition. In the random setting, Frankl and Rödl s…