2025/03/21 by Alexandr Grebennikov, Grebennikov, Alexandr, Letícia Mattos +3
Mathematics · #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2503.17334
For t ∈ ℕ, we say that a colouring of E(Kn) is almost t-Gallai if no two rainbow t-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 τt(n) of rainbow t-cliques in an almost t-Gallai colouring of E(Kn). For every t ≥ 4, we show that n2-o(1) ≤ τt(n) = o(n2). For t=3, surprisingly, the behaviour is substantially different. Our main result establishes that ( (1)/(2)-o(1) ) nlog n ≤ τ3(n) = O (n√(2)log n ), which gives the first non-trivial improvements over the simple lower and upper bounds. Our proof combines various applications of the probabilistic method and a generalisation of the edge-isoperimetric inequality for the hypercube.