Spring 2022

Discrete Geometry

• Time: every Tues and Thur 10:30-11:30am (KST), May 3 – July 14
• Zoom: 890 901 6918, PW: 202204

Announcement

• No class on May 10.
• Class on June 2 will be one hour earlier, i.e. 9:30-10:30am Korean time, due to conflict to our online seminar https://dimag.ibs.re.kr/event/2022-06-02/
• No class on June 28 and 30.
• Classes on July 5, 7, 12 are moved to 16:00 KST.

1. 5/3: affine hull/dependence, convex hull, cone, Separation thm, Farkas lem. Tablet note
2. 5/5: Carathéodory, Radon, Radon ⇒ Helly. Tablet note
3. 5/12: Radon ⇒ Carathéodory, colorful Carathéodory and application to directed cycle. Tablet note
4. 5/17: Polytope reduction trick, 2nd proof of Helly via sweeping argument. Tablet note
5. 5/19: Colorful Helly number could be larger than Helly number, multiple separation thm, 3rd proof of (colorful) Helly via Carathéodory and Farkas. Tablet note
6. 5/24: Infinite Helly requires compactness, applications of Helly: translate intersecting a family, half-spaces covering, Kirchberger’s thm. Tablet note
7. 5/26: Center point thm, Jung’s thm, Helly + Carathéodory ⇒ weak Tverberg. Tablet note
8. 5/31: Tight example for Tverberg and Sarkaria’s proof. Tablet note
9. 6/2: Fractional Helly, 1st proof via Helly, 2nd proof via colorful Helly. Tablet note
10. 6/7: Boros-Füredi, point selection in 2-dim, tight example: stretched grid, staircase convexity. Tablet note
11. 6/9: Tverberg + Colorful Carathéodory or Fractional Helly ⇒ First selection lemma, max covering number realised by random points. Tablet note
12. 6/14: Erdős-Simonovits supersaturation + Colorful Tverberg + Fractional Helly ⇒ Second selection lemma. Tablet note
13. 6/16: Second selection + weak hypergraph regularity + Same type lemma ⇒ Homogeneous selection lemma. Tablet note
14. 6/21: Order type, well-separated tuple, same type tranversal, Ham-Sandwich thm ⇒ Same type lemma. Tablet note
15. 6/23: First selection lemma ⇒ Weak ɛ-net theorem. Tablet note
16. 7/5: Better bound for planar case weak ɛ-net. Tablet note
17. 7/7: Example of families with (p,q)-property, connection of (p,q)-thm to chi-boundedness. Tablet note
18. 7/12: Fractional Helly + Weak ɛ-net + (p,q)-property retained (weakly) in blowups ⇒ (p,q)-thm via doubling argument. Tablet note
19. 7/14: (p,q)-thm via linear programming duality. Tablet note

---