On almost Gallai colorings in complete graphs
Grebennikov A, Mattos L, Szabó T. 2026. On almost Gallai colorings in complete graphs. Random Structures and Algorithms. 69(4), e70105.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Grebennikov, AleksandrISTA;
Mattos, Letícia;
Szabó, Tibor
Department
Abstract
We investigate a rainbow analog of the Ruzsa–Szemerédi problem. For 𝑡 ∈ ℕ, we say that a coloring of 𝐸(𝐾 𝑛) is almost𝑡-Gallai if no two rainbow 𝑡-cliques share an edge. Motivated by a lemma of Berkowitz on bounding the modulus of thecharacteristic function of clique counts in random graphs, we study the maximum number 𝜏𝑡(𝑛) of rainbow 𝑡-cliquesin an almost 𝑡-Gallai coloring of 𝐸(𝐾 𝑛). For every 𝑡 ≥ 4, we show that 𝑛2−𝑜(1) ≤ 𝜏𝑡(𝑛) = 𝑜(𝑛2). For 𝑡 = 3, surprisingly,the behavior is substantially different. Our main result establishes that ( 1/2 − 𝑜(1))𝑛 log 𝑛 ≤ 𝜏3(𝑛) ≤ 𝑂(𝑛√2 log 𝑛),which gives the first nontrivial improvements over the simple lower and upper bounds. Our proof combines various applications of the probabilistic method and a generalization of the edge-isoperimetric inequality for the hypercube.
Publishing Year
Date Published
2026-12-01
Journal Title
Random Structures and Algorithms
Publisher
Wiley
Volume
69
Issue
4
Article Number
e70105
ISSN
eISSN
IST-REx-ID
Cite this
Grebennikov A, Mattos L, Szabó T. On almost Gallai colorings in complete graphs. Random Structures and Algorithms. 2026;69(4). doi:10.1002/rsa.70105
Grebennikov, A., Mattos, L., & Szabó, T. (2026). On almost Gallai colorings in complete graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.70105
Grebennikov, Aleksandr, Letícia Mattos, and Tibor Szabó. “On Almost Gallai Colorings in Complete Graphs.” Random Structures and Algorithms. Wiley, 2026. https://doi.org/10.1002/rsa.70105.
A. Grebennikov, L. Mattos, and T. Szabó, “On almost Gallai colorings in complete graphs,” Random Structures and Algorithms, vol. 69, no. 4. Wiley, 2026.
Grebennikov A, Mattos L, Szabó T. 2026. On almost Gallai colorings in complete graphs. Random Structures and Algorithms. 69(4), e70105.
Grebennikov, Aleksandr, et al. “On Almost Gallai Colorings in Complete Graphs.” Random Structures and Algorithms, vol. 69, no. 4, e70105, Wiley, 2026, doi:10.1002/rsa.70105.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2026-11-17
MD5 Checksum
ca40ef10174860d69081dfd1a3bd61ad
