Polynomial Compressibility and Forbidden Oriented Forests
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.33600
curl -X POST /api/v1/records/arxiv/2609.33600/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.33600/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'