Tight Hamilton cycles with high discrepancy | Research seminar in Discrete Mathematics

Time：2024-05-07 Tue 17:05-18:15

Venue：Zoom: 787 662 9899 BIMSA

Organizer： Benjamin Sudakov

Speaker：Stefan Glock University of Passau

Abstract

In discrepancy theory, the basic question is whether a structure can be partitioned in a balancedway, or if there is always some discrepancy no matter how the partition is made.in the context ofgraph theory, a well-studied question is whether for a given host graph, any 2-colouring of its edgesmust contain a specified subgraph "with high discrepancy", meaning that within this subgraph oneof the colour classes is significantly larger than the other. We initiate the study of such questions forhypergraphs. Our main result is a discrepancy version of the celebrated theorem of Ri"odlRuci'nski and Szemer'edi on tight Hamilton cycles in Dirac hypergraphs. Joint work with LiorGishboliner and Amedeo Sgueglia.

Speaker Intro

Stefan Glock is assistant professor at the University of Passau in Germany. Prior to that, hespent 3 years as a junior fellow at ETH Zrich, after completing his PhD at the University ofBirmingham.

DATEMay 6, 2024

Related News

0
Edge-disjoint cycles with the same vertex set | Research seminar in Discrete Mathematics
AbstractIn 1975, Erdős asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. This problem has since been reiterated by several authors including Bollobás in 1978, Pyber, Rödl, and Szemerédi in 1995, and Chen, Erdős, and Staton in 1996. We asymptotically resolve this long-standing problem in a strong form, ...
1
Partitioning a tournament into sub-tournaments of high connectivity | Research seminar in Discrete Mathematics
AbstractA classical result of Hajnal and Thomassen asserts that for every$k$ there exists $K$ such that the vertices of every $K$-connected graph can be partitioned into two sets inducing $k$-connected subgraphs. Moreover they showed $K=O(k)$. There is now a whole area of combinatorial problems concerned with questions of this type; namely, to understand whether for a certain (di)graph property...