Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, October 10, 2024, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Micha Christoph

Improved bounds for zero-sum cycles in Z_p^d

For a finite Abelian group (G,+), let n(G) denote the smallest positive integer n such that for each labelling of the arcs of the complete digraph of order n using elements from G, there exists a directed cycle such that the total sum of the arc-labels along the cycle equals 0. Alon and Krivelevich initiated the study of the parameter n(.) on cyclic groups and proved that n(Z_q)=O(q log(q)). Several improvements and generalizations of this bound have since been obtained. When G is far from being cyclic, significant improvements on the bound can be made. In this direction, studying the prototypical case when G=Z_p^d is a power of a cyclic group of prime order, Letzter and Morrison showed that n(Z_p^d) < O(pd(log d)²) and that n(Z₂^d)< O(d log d). We improve their bound by proving n(Z₂^d)< 5d and n(Z_p^d)< O(pd log d).

Along the way to proving these results, we establish a generalization of a hypergraph matching result by Haxell in a matroidal setting. Concretely, we obtain sufficient conditions for the existence of matchings in a hypergraph whose hyperedges are labelled by the elements of a matroid, with the property that the edges in the matching induce a basis of the matroid. We believe that these statements are of independent interest.

This is joint work with Knierim, Martinsson and Steiner.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login