Generalized Turán problem for directed cycles

Andrzej Grzesik, Justyna Jaworska, Bartłomiej Kielak, Piotr Kuc, Tomasz Ślusarczyk · 2025

Read Generalized Turán problem for directed cycles by Andrzej Grzesik, Justyna Jaworska, Bartłomiej Kielak, Piotr Kuc, Tomasz Ślusarczyk (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22189.txt.

Description

Andrzej Grzesik and co-authors solve a counting problem about directed cycles in a 2025 combinatorics paper. They ask how many directed cycles of one length an oriented graph can hold while avoiding cycles of another length. The question is a directed version of a classic extremal problem named for Turan.

The authors settle the growth rate of that maximum for every pair of cycle lengths. When the forbidden length is large and does not divide the counted length, they pin the value down up to a small error. Exact values follow for further cases, completing a broad picture of the problem.

Catalog record

CREATORAndrzej Grzesik, Justyna Jaworska, Bartłomiej Kielak, Piotr Kuc, Tomasz Ślusarczyk
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22189

Browse the full library · About the Tower of Babel