Chromatic Extremal Thresholds and the Multipartite K4-Free Problem
Abstract
For positive integers n,r,t, let δ(n,r,t) denote the maximum possible minimum degree of a balanced r-partite graph with parts of size n and chromatic number at most t. 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 r=mt−a, m≥2, t≥3, 2≤ a≤ min{m,t−1}. 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 f(n,r,t+1)=δ(n,r,t). In particular, for t=3 it removes the remaining size restrictions at r=10 and r=13. Together with the r=7 result in arXiv:2609.19177, the classical r=4 case, and the known congruence classes, this gives a formula for the multipartite K4-free problem for every admissible r≥4 and every n≥1.
Related
- The Remaining K4-Free Case in the Multipartite Clique Problem
- A Turán-type extremal problem for the number of spanning trees in C4-free graphs
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- Extremal States of Multipartite Quantum Spin Systems
- Even cycle decomposition thresholds for dense multipartite graphs
BibTeX
@misc{kasugai2026chromatic,
title = {{Chromatic Extremal Thresholds and the Multipartite $K_4$-Free Problem}},
author = {Yuuki Kasugai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.27503},
eprint = {2609.27503},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27503},
}
RIS
TY - UNPB
TI - Chromatic Extremal Thresholds and the Multipartite K_4-Free Problem
AU - Yuuki Kasugai
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2609.27503
UR - https://arxiv.org/abs/2609.27503
AB - For positive integers n,r,t, let δ(n,r,t) denote the maximum possible minimum degree of a balanced r-partite graph with parts of size n and chromatic number at most t. 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 r=mt−a, m≥2, t≥3, 2≤ a≤ min{m,t−1}. 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 f(n,r,t+1)=δ(n,r,t). In particular, for t=3 it removes the remaining size restrictions at r=10 and r=13. Together with the r=7 result in arXiv:2609.19177, the classical r=4 case, and the known congruence classes, this gives a formula for the multipartite K_4-free problem for every admissible r≥4 and every n≥1.
ER -