ºÚÁÏÍø´óʼÇ

About the lecture

The Polynomial Hirsch Conjecture states that the diameter of the edge-vertex graph of polytopes is bounded by a polynomial of the number of their facets. This natural geometric problem is strongly connected to the central algorithmic question on the worst case running time of the simplex algorithm and its study motivated a number of abstractions and generalizations.
Santos in particular asked for the maximum diameter of d-dimensional abstract simplicial complexes on n vertices. Following a sequence of works by Santos, Criado, Newman, and Bohman, we determine this maximum for every n when d=2, and for every large enough n when d ≥ 3. The former construction is explicit, the latter one uses the probabilistic combinatorial technique of iterative absorption. Based on joint works with Stefan Glock, Olaf Parczyk, and Silas Rathke.

About the speaker

Tibor Szabó is Professor of Mathematics at Freie Universität Berlin, working in extremal and probabilistic combinatorics. He received his Ph.D. at The Ohio State University and has held positions at McGill University, ETH Zürich, the University of Illinois, and the Institute for Advanced Study. His research interests include extremal graph theory, random and pseudorandom structures, and combinatorial games.

Schedule

12-1pm: Presentation by Prof. Tibor Szabó in Room 4082/3 of the Anita B. Lawrence Centre, ºÚÁÏÍø´óʼÇ
1-3±è³¾:ÌýLight lunch in Room 3082, Anita B. Lawrence Centre, ºÚÁÏÍø´óʼÇ

Venue

Please enter the Anita B. Lawrence Centre building via the Centre Wing or East Wing entrances of the School of Mathematics and Statistics (ref: ).

*Please note that the School of Mathematics and Statistics is not accessible via the West Wing of the building.

Accessibility

Please note that the Anita B. Lawrence Building rooms 3082 and 4082 are wheelchair accessible. When you register, please indicate if you have any accessibility requirements and we will get in touch with you to ensure they can be accommodated.

Frontiers in Fundamental Mathematics Research Nexus

This event is presented by the ºÚÁÏÍø´óÊÂ¼Ç School of Mathematics and Statistics and is part of our Frontiers in Fundamental Mathematics Research Nexus series, which aims to highlight fundamental research in the mathematical sciences, with an emphasis on the significance and impact of fundamental mathematics to a diverse range of areas within mathematics and beyond.
Learn more about the Nexus Program.

Enquiries

Please contact Jan Lin if you have any enquiries about this event (j.lin@unsw.edu.au).