Chromatic Extremal Thresholds and the Multipartite -Free Problem
In the authors' words
For positive integers , let denote the maximum possible minimum degree of a balanced -partite graph with parts of size and chromatic number at most . Lo, Treglown and Zhao established a general upper bound for this parameter and used it, together with explicit constructions, to determine the corresponding multipartite clique threshold up to an additive constant in a broad parameter range. I determine the chromatic parameter throughout the range , , , . The answer differs from the Lo--Treglown--Zhao upper bound by at most one. I give an explicit arithmetic criterion deciding when this one-unit correction occurs. The proof reduces the problem to an integer matrix extremum. In the boundary case, equality forces the supports of all mixed rows to form a spanning star, after which the only remaining obstruction is a divisibility condition. Combining this formula with the Andrasfai--Erdos--Sos theorem sharpens the known equality range for . In particular, for it removes the remaining size restrictions at and . Together with the result in arXiv:2609.19177, the classical case, and the known congruence classes, this gives a formula for the multipartite -free problem for every admissible and every .
Appeared: Thursday, September 24. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 13