Erdős and Rado [Journal of the London Mathematical Society 25 (1950)] introduced the Canonical Ramsey numbers $\text{er}(t)$ as the minimum number $n$ such that every edge-coloring of the ordered complete graph $K_n$ contains either a monochromatic, rainbow, upper lexical, or lower lexical clique of order $t$. Richer [Journal of Combinatorial Theory Series B 80 (2000)] introduced the unordered asymmetric version of the Canonical Ramsey numbers $\text{CR}(s,r)$ as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a rainbow clique of order $r$, or an orderable clique of order $s$.We show that $\text{CR}(s,r) = O(r^3/\log r)^{s-2}$, which, up to the multiplicative constant, matches the known lower bound and improves the previously best known bound $\text{CR}(s,r) = O(r^3/\log r)^{s-1}$ by Jiang [Discrete Mathematics 309 (2009)]. We also obtain bounds on the further variant $\text{ER}(m,\ell,r)$, defined as the minimum $n$ such that every edge-coloring of the (unordered) complete graph $K_n$ contains either a monochromatic $K_m$, lexical $K_\ell$, or rainbow $K_r$.
@article{10_37236_13420,
author = {Igor Araujo and Dadong Peng},
title = {On the off-diagonal unordered {Erd\H{o}s-Rado} numbers},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/13420},
zbl = {1569.05233},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13420/}
}
TY - JOUR
AU - Igor Araujo
AU - Dadong Peng
TI - On the off-diagonal unordered Erdős-Rado numbers
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/13420/
DO - 10.37236/13420
ID - 10_37236_13420
ER -
%0 Journal Article
%A Igor Araujo
%A Dadong Peng
%T On the off-diagonal unordered Erdős-Rado numbers
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/13420/
%R 10.37236/13420
%F 10_37236_13420
Igor Araujo; Dadong Peng. On the off-diagonal unordered Erdős-Rado numbers. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/13420
