Tight Hamilton cycles with high discrepancy
Open Access
- 30 May 2025
- journal article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 34 (4) , 565-584
Abstract
In this paper, we study discrepancy questions for spanning subgraphs of $k$ -uniform hypergraphs. Our main result is that, for any integers $k \ge 3$ and $r \ge 2$ , any $r$ -colouring of the edges of a $k$ -uniform $n$ -vertex hypergraph $G$ with minimum $(k-1)$ -degree $\delta (G) \ge (1/2+o(1))n$ contains a tight Hamilton cycle with high discrepancy, that is, with at least $n/r+\Omega (n)$ edges of one colour. The minimum degree condition is asymptotically best possible and our theorem also implies a corresponding result for perfect matchings. Our tools combine various structural techniques such as Turán-type problems and hypergraph shadows with probabilistic techniques such as random walks and the nibble method. We also propose several intriguing problems for future research.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Oriented discrepancy of Hamilton cyclesJournal of Graph Theory, 2023
- Color‐biased Hamilton cycles in random graphsRandom Structures & Algorithms, 2021
- Loose Hamilton cycles in hypergraphsDiscrete Mathematics, 2011
- An approximate Dirac-type theorem for k-uniform hypergraphsCombinatorica, 2008
- Matchings in hypergraphs of large minimum degreeJournal of Graph Theory, 2005
- Hamiltonian chains in hypergraphsJournal of Graph Theory, 1999
- Asymptotic behavior of the chromatic index for hypergraphsJournal of Combinatorial Theory, Series A, 1989
- Kneser's conjecture, chromatic number, and homotopyJournal of Combinatorial Theory, Series A, 1978
- Imbalances in k‐colorationsNetworks, 1971
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964