Skip to content
DraconiticResearch
Search Sources API
190,869 studies31 sourcesUpdated 26 min ago
PreprintCC BY 4.0arXiv

L2 Turán Problems for Small Tournaments and Stability

  • Daniel Iľkovič
Open at sourcePDFDOICite

Abstract

We investigate the L2 Turán problems for various small directed graphs, specifically focusing on self-converse tournaments and stability versions. First, we determine the exact maximum L2 norm squared of the out-degree sequence for digraphs avoiding the transitive tournament TT4 and the strongly connected tournament R4, answering open questions from recent paper. We prove that the complete directed 3-partite Turán graph T3(m) exactly maximizes the L2 norm squared for TT4-free digraphs. For R4-free digraphs, the maximum is achieved by T3(m) except when m ≡ 1 pmod 3, where peeling off a terminal sink vertex to form T3(m−1) → v strictly increases the objective. We complement these results with exact values and a conjecture for the regular tournament Reg5. Furthermore, we prove a stability version for C⃗3-free digraphs: any sequence of digraphs asymptotically achieving the maximum L2 density must have an edit distance of O(δ1/2)m2 to the extremal ordered digon-chain F⃗m,2.

Related

  1. Degree-square Turán problem for two self-converse tournaments
    Zhuoran Han, Yaojun Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Turán-type extremal problems for unbalanced signed graphs
    Linfeng Xie, Keheng Zhu, Xiaogang Liu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The signless Laplacian spectral Turán problems for disjoint triangles
    Ming-Zhu Chen, Ya-Lei Jin, Peng-Li Zhang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Generalized Turán problems for shorter even cycles
    Zhen Liu, Chuanshu Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. NP-Hardness of Generalized-Turán Graph Modification Problems
    Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{iľkovic2026turán,
  title = {{$L_2$ Turán Problems for Small Tournaments and Stability}},
  author = {Daniel Iľkovič},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05042},
  eprint = {2609.05042},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05042},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - L_2 Turán Problems for Small Tournaments and Stability
AU  - Daniel Iľkovič
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.05042
UR  - https://arxiv.org/abs/2609.05042
AB  - We investigate the L_2 Turán problems for various small directed graphs, specifically focusing on self-converse tournaments and stability versions. First, we determine the exact maximum L_2 norm squared of the out-degree sequence for digraphs avoiding the transitive tournament TT_4 and the strongly connected tournament R_4, answering open questions from recent paper. We prove that the complete directed 3-partite Turán graph T_3(m) exactly maximizes the L_2 norm squared for TT_4-free digraphs. For R_4-free digraphs, the maximum is achieved by T_3(m) except when m ≡ 1 pmod 3, where peeling off a terminal sink vertex to form T_3(m−1) → v strictly increases the objective. We complement these results with exact values and a conjecture for the regular tournament Reg_5. Furthermore, we prove a stability version for C⃗_3-free digraphs: any sequence of digraphs asymptotically achieving the maximum L_2 density must have an edit distance of O(δ^1/2)m^2 to the extremal ordered digon-chain F⃗_m,2.
ER  -