4 papers
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…
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…
Interpolating chromatic and homomorphism thresholds
Xinqi Huang, Hong Liu, Mingyuan Rong +1
The problem of chromatic thresholds seeks for minimum degree conditions that ensure -free graphs to have a bounded chromatic number, or equivalently a bounded size homomorphic i…
Clique density vs blowups
Domagoj Bradač, Hong Liu, Zhuo Wu +1
A well-known theorem of Nikiforov asserts that any graph with a positive -density contains a logarithmic blowup of . In this paper, we explore variants of Nikiforov's r…