Seminar Geometry: Combinatorics and Algorithms FS23 (263-4203-00L)

Bernd Gärtner,	CAB G31.1,	lastname@inf.ethz.ch
Michael Hoffmann,	CAB G33.1,	lastname@inf.ethz.ch
Patrick Schnider,	CAB G33.2,	firstname.lastname@inf.ethz.ch
Emo Welzl,	CAB G39.2,	firstname@inf.ethz.ch

Contents

This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some background in (discrete and computational) geometry and in graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" is a prerequisite.

Topic and Papers

The seminar focuses on two topics: Planar Graph Product Structure and Around Tverberg's Theorem.
(To be able to access some of the papers linked below, you may need to be within the ETH network, e.g. via VPN.)

Schedule

All talks are held in CAB G59. Each talk is 45min. plus 15min. discussion. Between two talks on the same day there is a short break.

• First meeting: Friday Feb 24th 2023, 14:15, CAB G15.2.
• Preparation. Read the following article: Satyan L. Devadoss. Giving Good Talks. Notices AMS 66, 1647-1650, 2019.
• April 21, 2023, 14:15-15:00, Wang Shengzhe:
  Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood. Planar Graphs Have Bounded Queue-Number — Part I: Layered partitions of planar graphs. J. ACM 67/4:1-38, 2020.
• April 21, 2023, 15:30-16:15, Tobias Feigenwinter:
  Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood. Planar Graphs Have Bounded Queue-Number — Part II: 3d straight-line drawings of planar graphs. J. ACM 67/4:1-38, 2020.
• May 5, 2023, 14:15-15:00, Juan Villacis Llobet:
  Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Adv. Combin. 5, 2020.
• May 5, 2023, 15:30-16:15, Gergely Kulcsár:
  Prosenjit Bose, Pat Morin, Saeed Odak. An optimal algorithm for product structure in planar graphs. Proc. 18th SWAT 2022.
• May 12, 2023, 14:15-15:00, Yuda Fan:
  Jean-Pierre Roudneff. Partitions of Points into Simplices with k-dimensional Intersection. Part I: The Conic Tverberg's Theorem. European J. Combin. 22(5), 733-743, 2001.
• May 12, 2023, 15:30-16:15, Patrick Stählin:
  Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, Uli Wagner. The Crossing Tverberg Theorem. Proc. 35th SoCG, 2019.
• May 26, 2023, 14:15-15:00, Luca Pinter:
  Sherry Sarkar, Pablo Soberon. Tolerance for colorful Tverberg partitions. European J. Combin. 103, 2022.

Conditions

The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

1. getting an overview of the related literature;
2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
3. understanding the contents of the paper in all details;
4. selecting parts suitable for the presentation;
5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
2. a satisfactory plenary talk;
3. attendance at all other talks.

---

Last modified: Mon Feb 27 11:08:16 CET 2023 by Michael Hoffmann.

Valid HTML5