The Threshold for Ackermannian Ramsey numbers
| dc.creator | Kojman, Menachem | |
| dc.creator | Omri, Eran | |
| dc.date | 2005-05-05 | |
| dc.date.accessioned | 2026-07-07T05:19:39Z | |
| dc.date.available | 2026-07-07T05:19:39Z | |
| dc.description | For a function $g:\N\to \N$, the \emph{$g$-regressive Ramsey number} of $k$ is the least $N$ so that \[N\stackrel \min \longrightarrow (k)_g\] . This symbol means: for every $c:[N]^2\to \N$ that satisfies $c(m,n)\le g(\min\{m,n\})$ there is a \emph{min-homogeneous} $H\su N$ of size $k$, that is, the color $c(m,n)$ of a pair $\{m,n\}\su H$ depends only on $\min\{m,n\}$. It is known (\cite{km,ks}) that $\id$-regressive Ramsey numbers grow in $k$ as fast as $\Ack(k)$, Ackermann's function in $k$. On the other hand, for constant $g$, the $g$-regressive Ramsey numbers grow exponentially in $k$, and are therefore primitive recursive in $k$. We compute below the threshold in which $g$-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian, by proving: Suppose $g:\N\to \N$ is weakly increasing. Then the $g$-regressive Ramsey numbers are primitive recursive if an only if for every $t>0$ there is some $M_t$ so that for all $n\ge M_t$ it holds that $g(m)<n^{1/t}$ and $M_t$ is bounded by a primitive recursive function in $t$. | |
| dc.identifier | https://arxiv.org/abs/math/0505086 | |
| dc.identifier | http://arxiv.org/abs/math/0505086 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75094 | |
| dc.subject | Combinatorics | |
| dc.title | The Threshold for Ackermannian Ramsey numbers | |
| dc.type | text |