Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

Intersections of Oriented Graphs and Tournaments

  • Zhanping Yang
  • Qinghou Zeng
Open at sourcePDFDOICite

Abstract

Given two tournaments of order n, Bollobás and Scott defined their discrepancy as the largest deviation of their overlap from its random average under relabelling, and they asked whether the resulting discrepancy is always Ω(n3/2). We answer this question by proving that there is an absolute constant c>0 such that every pair of tournaments T,U of order n has discrepancy at least cn3/2. More generally, if D and H are oriented graphs of order n with e(D) = p binomn2 and e(H) = q binomn2 satisfying 16/n ≤ p, q ≤ 1 − 16/n, then there is an absolute constant c > 0 such that their discrepancy is at least c(p(1−p)q(1−q))3n3/2. We also show that these two-graph estimates extend to intersections of any fixed number of graphs, tournaments, and oriented graphs.

Related

  1. Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
    Yihang Liu, Zhenyu Yang, Yuwan Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Intersections of Directed Graphs
    Zhanping Yang, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
    Jia Zhou, Yunshu Gao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Oriented paths with two blocks in bipartite oriented graphs
    Bin Chen, Meishuang Chen, Xinmin Hou +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Every tournament T of order at least 3 admits infinitely many T-irregular oriented graphs
    Tatiana Dovzhenok
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yang2026intersections,
  title = {{Intersections of Oriented Graphs and Tournaments}},
  author = {Zhanping Yang and Qinghou Zeng},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.27965},
  eprint = {2608.27965},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.27965},
}
RIS
TY  - UNPB
TI  - Intersections of Oriented Graphs and Tournaments
AU  - Zhanping Yang
AU  - Qinghou Zeng
PY  - 2026
DA  - 2026/09/07
PB  - arXiv
DO  - 10.48550/arxiv.2608.27965
UR  - https://arxiv.org/abs/2608.27965
AB  - Given two tournaments of order n, Bollobás and Scott defined their discrepancy as the largest deviation of their overlap from its random average under relabelling, and they asked whether the resulting discrepancy is always Ω(n^3/2). We answer this question by proving that there is an absolute constant c>0 such that every pair of tournaments T,U of order n has discrepancy at least cn^3/2. More generally, if D and H are oriented graphs of order n with e(D) = p binomn2 and e(H) = q binomn2 satisfying 16/n ≤ p, q ≤ 1 − 16/n, then there is an absolute constant c > 0 such that their discrepancy is at least c(p(1−p)q(1−q))^3n^3/2. We also show that these two-graph estimates extend to intersections of any fixed number of graphs, tournaments, and oriented graphs.
ER  -