EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Almost Gallai Colorings in Complete Graphs

Alexandr Grebennikov, Letícia Mattos, Tibor Szabó

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →