Metraipolis › archive › dc_41e60258a5fb

Polynomial Compressibility and Forbidden Oriented Forests — arXiv:2609.33600

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33600
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:06.156Z
SHA-256 of the archived text
6d63023a3a864600ac3806fdfd2d8a0e652215970780d80ea1896d5b0f317766
Stable URL of this page
https://metraipolis.com/documento/dc_41e60258a5fb

How to cite

Polynomial Compressibility and Forbidden Oriented Forests — arXiv:2609.33600 — arXiv (en), https://arxiv.org/abs/2609.33600 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_41e60258a5fb (Metraipolis archive dc_41e60258a5fb, sha256 6d63023a3a864600ac3806fdfd2d8a0e652215970780d80ea1896d5b0f317766)
BibTeX
@misc{dc41e60258a5fb,
  title = {Polynomial Compressibility and Forbidden Oriented Forests — arXiv:2609.33600},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33600},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_41e60258a5fb; sha256 6d63023a3a864600ac3806fdfd2d8a0e652215970780d80ea1896d5b0f317766},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33600. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a nonempty acyclic oriented graph $H$, let $p(H)$ be the order of a longest directed path and let $\tau(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 \tau(H)=r_{\mathrm{tr}}(p), \] where $r_{\mathrm{tr}}(p)=2^{\Theta(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 $\tau$-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^{\Theta(g)}$. We also establish polynomial $\tau$-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\ge2$, and bounds $4$ and $3p-2$ for the directed and alternating orientations of $P_4$, respectively. In the alternating case, $\tau(H)=p(H)$ when the underlying graph is triangle-free.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.33600 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.815Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).