Exploring the Borsuk-Ulam Theorem: Applications in Geometry and Combinatorics

Instructors  Arijit Ghosh

Teaching assistants Buddhadev Das, Arnab Ray, and Soumi Nandi

Description Introduction to Borsuk-Ulam Theorem and its different relatives. We will also study some fundamental applications of these wonderful results from topology to problems in Combinatorics and Geometry.

Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences

Duration 5th Feb. - 9 Feb. 2024 (Class timings: 9:30 AM to 11:00 AM)

Syllabus

Tools from topology

• Borsuk-Ulam Theorem, and its different relatives

• Brouwer's Fixed Point Theorem

• Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem

• Gale's Colorful KKM Theorem

• Shapley's extension of KKM Theorem, and its colorful extension

Topics from Combinatorics and Geometry

• Sperner's Lemma

• Tucker's Lemma

• Ham-Sandwich Theorem

• Graphs with large chromatic number and no small odd-cycles

• Kneser's Graph and its chromatic number

• Gallai's Theorem connecting matching number and cover of family of intervals

• Colorful Gallai's Theorem

Special topics (if time permits)

• Application of Borsuk-Ulam Theorem in Communication Complexity

• Computational aspects of Borsuk-Ulam Theorem and Brouwer's Fixed Point Theorem

Lecture details

Topics covered in Lecture 1 (5 Feb. 2024)

• Introduction to the short course

• Statements of Borsuk-Ulam Theorem and Brouwer's Fixed Point Theorem

• Connections between the Intermediate Value Theorem and the above theorems 

• Standard notations from geometric simplicial complexes:

  • • Affine independence 

    • Geometric simplex and simplicial complexes

    • Subdivision of simplicial complex 

    • Barycentric subdivision

• Sperner's Theorem 

• References:

  • • Chapter 1 from [M03]

    • Refer to the Wikipedia articles on Sperner's Lemma, Borsuk-Ulam Theorem, and Brouwer's Fixed Point Theorem

Discussion session 1 (by Buddhadev, 5 Feb. 2024)

• Introduction to line transversal of a finite collection of convex sets in the plane

• Improve line transversal bound in the plane by McGinnis and Zerbib using KKM Lemma

• References:

  • • McGinnis and Zerbib's paper [MZ22]

Topics covered in Lecture 2 (6 Feb. 2024)

• Proof of Brouwer's Fixed Point Theorem using Sperner's Theorem and Barycentric subdivision

• Knaster–Kuratowski–Mazurkiewicz (KKM) Lemma and its proof using Brouwer's Fixed Point Theorem

• Statement of Colorful KKM Theorem

• References:

  • • Refer to Chapter 1 from [L13]

    • Lecture 3 from [F08]

    • See the proof of KKM Lemma from [Z21]

    • Refer to the Wikipedia article on KKM Lemma

Discussion session 2 (by Buddhadev, 6 Feb. 2024)

• Completed the proof of the line transversal result by McGinnis and Zerbib from the previous discussion session

• References:

  • • McGinnis and Zerbib's paper [MZ22]

Discussion session 3 (by Soumi, 7 Feb. 2024)

• Discussed infinite generalizations of (p,q)-Theorem of Alon and Kalai for hyperplanes

• References:

  • • Alon and Kalai's paper [AK95]

Lecture 3 (8 Feb. 2024)

• Recalled the statement of Borsuk-Ulam Theorem

• Setting up the different equivalent variants of the Borsuk-Ulam Theorem 

• Symmetric labeling of symmetric polytopes

• Statement of Tucker's Lemma

• References:

  • • Chapter 2 from [M03]

    • Chapter 1 from [L13]

    • Refer to the Wikipedia article on Lusternik–Schnirelmann Theorem

Discussion session 4 (by Arnab, 8 Feb. 2024)

• Gallai’s Theorem, and its proof using KKM Theorem

• Proof of KKM Theorem using Sperner's Lemma

• References:

  • • Refer to [Z21]

Lecture 4 (9 Feb. 2024)

• Construction of graphs with large chromatic number and no small odd-cycles using Borsuk-Ulam Theorem

• Kneser graph and its chromatic number

• Application of Borsuk-Ulam Theorem to find chromatic number of Kneser graph

• Proof of Borsuk-Ulam Theorem using Tucker's Lemma and Barycentric subdivision

• References:

  • • Section 3.3 from [M03]

    • Section 2.1 from [L13]

    • Chapter 5 from [G20]

    • Refer to the Wikipedia article on De Bruijn–Erdős Theorem

Discussion session 5 (by Soumi, 9 Feb. 2024)

• Colorful Borsuk-Ulam Theorem and its applications

• References:

  • • Refer to Frick and Wellner's paper [FW23]