8 papers · 1 filter
The asymptotic Erd{ő}s--Frankl--Füredi cover-free conjecture
Xinqi Huang, Hong Liu
In 1985, Erd{ő}s, Frankl and F{ü}redi conjectured that the threshold for the existence of an -cover-free family with more members than points satisfies …
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…
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…
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…
Piercing independent sets in graphs without large induced matching
Jiangdong Ai, Hong Liu, Zixiang Xu +1
Given a graph , denote by the smallest size of a subset of which intersects every maximum independent set of . We prove that any graph without induced match…
Beyond chromatic threshold via the -theorem, and a sharp blow-up phenomenon
Hong Liu, Chong Shangguan, Jozef Skokan +1
We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated -theorem in discrete geometry. In particular,…