Polynomial Compressibility and Forbidden Oriented Forests
Abstract
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≥3 and g≥1, 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, τ(H)=rtr(p), where rtr(p)=2Θ(p) is the tournament Ramsey number for a transitive p-vertex tournament. This disproves the conjectured polynomial bounds under bounded absolute or relative oriented clique number. It also shows that a forbidden graph can yield a polynomially τ-bounded class only if its underlying graph is a forest. For fixed g, the least order of these examples is bounded by a polynomial in p. A separate construction gives maximum in- and outdegree O(p2), uniformly in g. For p=4, the least order is 2Θ(g). We also establish polynomial τ-boundedness for every orientation of the two four-vertex trees. The pure-claw case follows from the known O(p4) bound. We obtain the bound 2p−2 for mixed claws and one-turn orientations of P4 when p≥2, and bounds $4$ and 3p−2 for the directed and alternating orientations of P4, respectively. In the alternating case, τ(H)=p(H) when the underlying graph is triangle-free.
Related
- Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
- Polynomial-in-r bounds for forbidden traces of uniform hypergraphs
- A Polynomial-Time Test for Peak-Oriented Rationalizability
- An Index-Graded Virtual Intersection Polynomial for Oriented Virtual Knots
- On the compactness of artificial compressibility approximations of weak solutions for fluid problems in deforming domains
BibTeX
@misc{lyu2026polynomial,
title = {{Polynomial Compressibility and Forbidden Oriented Forests}},
author = {Zhenhua Lyu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33600},
eprint = {2609.33600},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33600},
}
RIS
TY - UNPB
TI - Polynomial Compressibility and Forbidden Oriented Forests
AU - Zhenhua Lyu
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33600
UR - https://arxiv.org/abs/2609.33600
AB - 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≥3 and g≥1, 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, τ(H)=r_tr(p), where r_tr(p)=2^Θ(p) is the tournament Ramsey number for a transitive p-vertex tournament. This disproves the conjectured polynomial bounds under bounded absolute or relative oriented clique number. It also shows that a forbidden graph can yield a polynomially τ-bounded class only if its underlying graph is a forest. For fixed g, the least order of these examples is bounded by a polynomial in p. A separate construction gives maximum in- and outdegree O(p^2), uniformly in g. For p=4, the least order is 2^Θ(g). We also establish polynomial τ-boundedness for every orientation of the two four-vertex trees. The pure-claw case follows from the known O(p^4) bound. We obtain the bound 2p−2 for mixed claws and one-turn orientations of P_4 when p≥2, and bounds $4$ and 3p−2 for the directed and alternating orientations of P_4, respectively. In the alternating case, τ(H)=p(H) when the underlying graph is triangle-free.
ER -