Skip to content
DraconiticResearch
Search Sources API
197,578 studies31 sourcesUpdated 34 min ago
PreprintarXiv licencearXiv

Avoidability of Digraphs with Height Functions and Orientations of C4

  • Hui Lei
  • Xiaoyi Wang
  • Zhijun Xu
  • Zhenyu Yang
Open at sourcePDFDOICite

Abstract

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 C4 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 C4 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 C4 that is not Eulerian-avoidable, completing the classification of C4-orientations.

Related

  1. Degree conditions for k-strong orientations of digraphs
    Jørgen Bang-Jensen, Shuo Wei
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
    Rostislav Klech
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  3. Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs
    Rostislav Klech
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Kloosterman Sums and Plücker Height Zeta Functions
    Li Cai, Jingsong Chai, Yadi Liu +1
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Height functions on singular surfaces parameterized by smooth maps 𝒜-equivalent to Hk
    Masaru Hasegawa
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{lei2026avoidability,
  title = {{Avoidability of Digraphs with Height Functions and Orientations of $C_4$}},
  author = {Hui Lei and Xiaoyi Wang and Zhijun Xu and Zhenyu Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.14368},
  eprint = {2609.14368},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14368},
}
RIS
TY  - UNPB
TI  - Avoidability of Digraphs with Height Functions and Orientations of C_4
AU  - Hui Lei
AU  - Xiaoyi Wang
AU  - Zhijun Xu
AU  - Zhenyu Yang
PY  - 2026
DA  - 2026/09/13
PB  - arXiv
DO  - 10.48550/arxiv.2609.14368
UR  - https://arxiv.org/abs/2609.14368
AB  - 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.
ER  -