On Almost Gallai Colorings in Complete Graphs
Random Structures & Algorithms · 2026-12 · 69 (4)
DOI: 10.1002/rsa.70105 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 05.11.2026. Verfasst von Alexandr Grebennikov und 2 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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 the characteristic function of clique counts in random graphs, we study the maximum number of rainbow ‐cliques in an almost ‐Gallai coloring of . For every , we show that . For , surprisingly, the behavior is substantially different. Our main result establishes that 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.
Zitieren
APA
Grebennikov, A., Mattos, L., & Szabó, T. (2026). On Almost Gallai Colorings in Complete Graphs. Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70105
Vancouver
Grebennikov A, Mattos L, Szabó T. On Almost Gallai Colorings in Complete Graphs. Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70105
BibTeX
@article{Grebennikov2026,
author = {Grebennikov, Alexandr and Mattos, Letícia and Szabó, Tibor},
title = {On Almost Gallai Colorings in Complete Graphs},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {69},
number = {4},
doi = {10.1002/rsa.70105}
}
EUVIMED