An Ore-type Theorem for Oriented Discrepancy of Hamilton Cycles
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918422776905728 |
|---|---|
| author | Chang, Yufei Cheng, Yangyang Wang, Zhilan Wei, Shuo Yan, Jin |
| author_facet | Chang, Yufei Cheng, Yangyang Wang, Zhilan Wei, Shuo Yan, Jin |
| contents | Oriented graph discrepancy problems focus on finding specific subgraphs within a given oriented graph $G$ that contain a significant number of edges in one direction. This concept was first introduced by Gishboliner, Krivelevich, and Michaeli, and has since been further investigated by Freschi and Lo [J. Combin. Theory, Ser. B 169 (2024)], who gave a tight lower bound for the discrepancy of Hamilton cycles in terms of the minimum degree of $G$. Furthermore, they raised the problem of extending such results to Ore-type conditions. Here, an Ore-type condition refers to the minimum degree-sum of non-adjacent vertices, formally defined as: $σ_2(G)=\min\{d(x)+d(y)\mid x, y \in V(G) \text{ and } xy \notin E(G)\}$. In this paper, we address this question by showing that for every sufficiently large oriented graph $G$, if $σ_2(G)\geq n$, then $G$ contains a Hamilton cycle $C$ with at least $\max\{n/2,σ_2(G)/2-o(n)\}$ edges in one direction. Moreover, this result is asymptotically tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18915 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Ore-type Theorem for Oriented Discrepancy of Hamilton Cycles Chang, Yufei Cheng, Yangyang Wang, Zhilan Wei, Shuo Yan, Jin Combinatorics 05C20, 05C38, 05C40 Oriented graph discrepancy problems focus on finding specific subgraphs within a given oriented graph $G$ that contain a significant number of edges in one direction. This concept was first introduced by Gishboliner, Krivelevich, and Michaeli, and has since been further investigated by Freschi and Lo [J. Combin. Theory, Ser. B 169 (2024)], who gave a tight lower bound for the discrepancy of Hamilton cycles in terms of the minimum degree of $G$. Furthermore, they raised the problem of extending such results to Ore-type conditions. Here, an Ore-type condition refers to the minimum degree-sum of non-adjacent vertices, formally defined as: $σ_2(G)=\min\{d(x)+d(y)\mid x, y \in V(G) \text{ and } xy \notin E(G)\}$. In this paper, we address this question by showing that for every sufficiently large oriented graph $G$, if $σ_2(G)\geq n$, then $G$ contains a Hamilton cycle $C$ with at least $\max\{n/2,σ_2(G)/2-o(n)\}$ edges in one direction. Moreover, this result is asymptotically tight. |
| title | An Ore-type Theorem for Oriented Discrepancy of Hamilton Cycles |
| topic | Combinatorics 05C20, 05C38, 05C40 |
| url | https://arxiv.org/abs/2603.18915 |