Tight Hamilton cycles with high discrepancy
Preprint
Abstract
In this paper, we initiate the study of discrepancy questions for spanning subgraphs of $k$-uniform hypergraphs. Our main result is that any $2$-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/2+\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\'an-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 15 references indexed in Scilit:
- An oriented discrepancy version of Dirac's theoremJournal of Combinatorial Theory, Series B, 2024
- 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
- Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degreeJournal of Combinatorial Theory, Series B, 2006
- Asymptotic behavior of the chromatic index for hypergraphsJournal of Combinatorial Theory, Series A, 1989
- Near Perfect Coverings in Graphs and HypergraphsEuropean Journal of Combinatorics, 1985
- 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