Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP

on YouTube ↗32m

" summary

Paper defines a two-player long choice game on 2^n pigeons whose iterated-majority argument yields class PLC; it reduces the classic pigeonhole circuit (PPP) to long choice, so PPP ⊆ PLC. Ramsey (r^n vertices) and a naive sunflower (≈k^3 log k sets, target size k^2) both reduce to long choice. Dual problems short choice and PEPP/PSC mirror iterated-minority/empty-pigeonhole arguments. Konig and Erdos–Ko–Rado are shown PPP-complete; a Turán-style k-hierarchy appears strictly harder, with open separations.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:19TFNP: Preliminaries
3. 2:36TFNP Subclasses
4. 4:15PPP-completeness
5. 6:15Extremal Combinatorics and Pigeonhole
6. 7:28Iterated Majority Argument
7. 9:29Polynomial Long Choice (PLC)
8. 12:27PLC and PPP
9. 13:59Ramsey
10. 16:11Sunflower Lemma
11. 17:49Naive Sunflower: TFNP Problem
12. 20:03"Dual" Pigeonhole Argument
13. 21:51Short Choice: Dual of Long Choice
14. 23:03PSC: Polynomial Short Choice
15. 23:44König's Lemma on Binary Trees
16. 26:59Mantel's Theorem
17. 30:35Conclusion