{"id":"arxiv/2609.33600","url":"https://arxiv.org/abs/2609.33600","tags":["math.CO"],"score":0,"title":"Polynomial Compressibility and Forbidden Oriented Forests","domain":"math.CO","source":"arxiv","authors":["Zhenhua Lyu"],"reviews":0,"subject":"math.CO","summary":"For a nonempty acyclic oriented graph $H$, let $p(H)$ be the order of a longest directed path and let $τ(H)$ be the least positive integer $n$ such that $H$ admits a homomorphism to every tournament of order $n$. For all $p\\ge3$ and $g\\ge1$, we construct a connected acyclic oriented graph $H$ with underlying girth greater than $g$, absolute and relative oriented clique numbers equal to three, and \\[ p(H)=p,\\qquad τ(H)=r_{\\mathrm{tr}}(p), \\] where $r_{\\mathrm{tr}}(p)=2^{Θ(p)}$ is the tournament Ramsey number for a transitive $p$-vertex tournament. This disproves the conjectured polynomial…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}