2024/09/17 by Igor Araujo, Araujo, Igor, Peng, Dadong
Mathematics · #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Analysis and Transform Methods #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2409.11574
openalex publication_date 2024/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Erdős and Rado [P. Erdős, R. Rado, A combinatorial theorem, Journal of the London Mathematical Society 25 (4) (1950) 249-255] introduced the Canonical Ramsey numbers er(t) as the minimum number n such that every edge-coloring of the ordered complete graph Kn contains either a monochromatic, rainbow, upper lexical, or lower lexical clique of order t. Richer [D. Richer, Unordered canonical Ramsey numbers, Journal of Combinatorial Theory Series B 80 (2000) 172-177] introduced the unordered asymmetric version of the Canonical Ramsey numbers CR(s,r) as the minimum n such that every edge-coloring of the (unorderd) complete graph Kn contains either a rainbow clique of order r, or an orderable clique of order s. We show that CR(s,r) = O(r3/log r)s-2, which, up to the multiplicative constant, matches the known lower bound and improves the previously best known bound CR(s,r) = O(r3/log r)s-1 by Jiang [T. Jiang, Canonical Ramsey numbers and proporly colored cycles, Discrete Mathematics 309 (2009) 4247-4252]. We also obtain bounds on the further variant ER(m,ℓ,r), defined as the minimum n such that every edge-coloring of the (unorderd) complete graph Kn contains either a monochromatic Km, lexical K_ℓ, or rainbow Kr.