Metraipolis › archive › dc_d2dbd081c877
Avoidability of Digraphs with Height Functions and Orientations of $C_4$ — arXiv:2609.14368
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14368
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T01:25:18.164Z
- SHA-256 of the archived text
b68a7cbcc5db4ee1e7c1aaaae5847ff4d0b5fc01990be294e3d4ec2631e39865- Stable URL of this page
https://metraipolis.com/documento/dc_d2dbd081c877
How to cite
Avoidability of Digraphs with Height Functions and Orientations of $C_4$ — arXiv:2609.14368 — arXiv (en), https://arxiv.org/abs/2609.14368 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d2dbd081c877 (Metraipolis archive dc_d2dbd081c877, sha256 b68a7cbcc5db4ee1e7c1aaaae5847ff4d0b5fc01990be294e3d4ec2631e39865)
BibTeX
@misc{dcd2dbd081c877,
title = {Avoidability of Digraphs with Height Functions and Orientations of $C_4$ — arXiv:2609.14368},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14368},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d2dbd081c877; sha256 b68a7cbcc5db4ee1e7c1aaaae5847ff4d0b5fc01990be294e3d4ec2631e39865},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14368. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A digraph $F$ is avoidable if, for every positive integer $k$, there exists an integer $d$ such that every digraph of minimum out-degree at least $d$ contains an $F$-free subdigraph of minimum out-degree at least $k$. We prove that no digraph admitting a height function is avoidable, where a height function increases by one along every arc. This answers a question of Christoph, Janzer, Petrova, and Steiner and, together with an additional avoidance argument, determines which orientations of $C_4$ are avoidable. Motivated by a further question of Christoph, Janzer, Petrova, and Steiner, we also study Eulerian avoidability, in which the host digraph is required to have equal in-degree and out-degree at every vertex. We show that no one-directed complete bipartite digraph with nonempty parts is Eulerian-avoidable. In contrast, the orientation of $C_4$ consisting of two directed paths of length two with common endpoints is Eulerian-avoidable. Consequently, the one-directed complete bipartite orientation is the only orientation of $C_4$ that is not Eulerian-avoidable, completing the classification of $C_4$-orientations. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.14368 — 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-16T00:39:30.210Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).