Phase transitions of the Erdős-Gyárfás function

2025/04/08 by Xinyu Hu, Hu, Xinyu, Qizhong Lin +5
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Combinatorial Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2504.05647

Abstract

Given positive integers p,q. For any integer k≥2, an edge coloring of the complete k-graph K_n^(k) is said to be a (p,q)-coloring if every copy of K_p^(k) receives at least q colors. The Erdős-Gyárfás function f_k(n,p,q) is the minimum number of colors that are needed for K_n^(k) to have a (p,q)-coloring. Conlon, Fox, Lee and Sudakov (IMRN, 2015) conjectured that for any positive integers p, k and i with k≥3 and 1≤ i

Related

• Lower bounds on the Erdős-Gyárfás problem via color energy graphs
• A new variant of the Erdős-Gyárfás problem on K₅
• The Erdős-Gyárfás function f(n, 4, 5) = \frac 56 n + o(n) -- so Gyárfás was right
• A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
• New Upper Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers