{"id":"arxiv/2606.30885","url":"https://arxiv.org/abs/2606.30885","tags":["math.LO","math.CO"],"score":0,"title":"The finite big Ramsey degrees of Henson graphs are provable in $\\mathrm{ACA}_0$","domain":"math.LO","source":"arxiv","authors":["Peter Cholak","Natasha Dobrinen","Henry Towsner"],"reviews":0,"subject":"math.LO","summary":"Let $\\mathbb{H}_{n+1}$ denote a computable copy of the $(n+1)$-clique free universal homogeneous Henson graph, $G$ denote a finite subgraph of $\\mathbb{H}_{n+1}$, and $k(G,n)$ denote the big Ramsey degree of $G$ in $\\mathbb{H}_{n+1}$. We prove that for any computable coloring $χ$ of the copies of $G$ in $\\mathbb{H}_{n+1}$, there is a copy $\\mathbb{H}'$ of $\\mathbb{H}_{n+1}$ that is computable from $0^{(2δ(G,n)-1)}$ in which $χ$ takes no more than $k(G,n)$ colors, where $δ(G,n)$ denotes the maximum number of levels of a diary for $G$ in $\\mathbb{H}_{n+1}$ (this is a finite number). It follows…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}