Park City Math Institute '25

For the last three weeks, I attended the IAS/PCMI on Extremal and Probabilistic Combinatorics in Utah. Here is a recap of my experience:

Table of Contents

Undergraduate Summer School

The Undergraduate Summer School was composed of two parts: a lecture series and a project portion called the experimental math lab.

Lectures

Yuval Wigderson gave 12 lectures total; 6 on extremal combinatorics and 6 on Ramsey theory.

Extremal Combinatorics

I really enjoyed these lectures. Even though I don't have as much background in graph theory as some of my classmates, I've been able to keep up. I also found the content far more interesting than I expected. The problem sets can get tough, but that’s part of what makes them fun. I’ve noticed that I’m especially drawn to the probabilistic arguments. There’s something elegant about using randomness to prove that certain structures must exist, without knowing anything about how to actually construct that structure. Maybe it's time I finally read Alon and Spencer's The Probabilistic Method.

Here's what we covered:

6 Lectures on Extremal Combinatorics
  • Lecture 1:
  • What is Extremal Combinatorics: Erdös's Distinct Sums Conjecture (Bohman's upper bound; Erdös-Moser's lower bound, Dubroff-Fox-Xu lower bound);
  • What is Extremal Graph Theory: Mantel's theorem; Turán's theorem
  • Lecture 2:
  • Beyond Turan's Theorem Erdös-Stone-Simonovits theorem (and proof of lower bound)
  • Upper bounds for extremal numbers of bipartite graphs: a theorem about $C_4$ in $d$-regular graphs; a useful variant of Jensen's inequality; Kövári-Sós-Turán theorem
  • Lecture 3:
  • Lower bounds for extremal numbers of bipartite graphs: Klein's $C_4$-free graph theorem; Brown's $K_{3,3}$-free graph theorem; conjecture that Kövári-Sós-Turán is tight in general (Kollár-Rónyai-Szabo, Alon-Rónyai-Szabó, Bukh, 2-density variant)
  • Extremal numbers for hypergraphs: Extremal numbers for Turán's conjecture on the analogue of Mantel's theorem for hypergraphs (Túran's 5/9 construction; de Caen's lower bound, Sidorenko's upper bound)
  • Lecture 4:
  • More on hypergraphs: Erdös's generalization of Kövári-Sós-Turán for hypergraphs
  • Supersaturation: supersaturation version of Turán's theorem
  • Lecture 5:
  • Erdös-Stone-Simonovits and beyond: Proof of the Erdös-Stone-Simonovits theorem; Simonovits color critical theorem; Theorem about pseudo-coloring and decomposition family
  • Lecture 6:
  • Extremal numbers of general bipartite graphs: Bondy–Simonovits theorem on even cycles; Erdös–Simonovits rational exponents conjecture; Bukh–Conlon 2018's rational exponents theorem
  • Stability: Füredi stability version of Turán's theorem; Stability method for $C_5$-free graphs

Ramsey Theory

I first saw the Hales–Jewett theorem almost exactly three years ago. Back then, I said I didn’t like Ramsey theory, as it felt like every proof was just stacking layers of induction on top of each other, with lots of power towers. To be honest, I still feel that way. But, this course was more enjoyable than the last one. The topics were a better fit for me, and I really enjoyed the last lecture on Folkman's theorem.

Here's what we covered:

6 Lectures on Ramsey Theory
  • Lecture 7:
  • Ramsey Theory before Ramsey: Schur's FLT Theorem; (Combinatorial) Schur's Hilfssatz
  • Upper Bounds on Ramsey Numbers: Ramsey's theorem; (off-diagonal) Ramsey number; Erdös-Szekeres (and off-diagonal generalization)
  • Lower Bounds on Ramsey Numbers: Turán coloring lower bound for Ramsey numbers
  • Lecture 8:
  • More on Lower Bounds for Ramsey Numbers: Erdös's lower bound for Ramsey numbers; Erdös's open problem on $2$-colorings with no monochromatic $K_k$ (Li's theorem); Campos–Griffiths–Morris–Sahasrabudh's theorem; Ma-Shen-Xie's theorem;
  • Hypergraph Ramsey Numbers: Ramsey's theorem for hypergraphs; Klein's result for convex position; Erdös-Szekeres theorem; Carathéodory theorem
  • Bounds on Hypergraph Ramsey Numbers: Erdös-Rado theorem; Corollary for Erdös-Rado theorem; Erdös-Hajnal-Rado (theorem, corollary, and conjecture); Hajnal's theorem
  • Lecture 9:
  • Graph Ramsey numbers: Graph Ramseum numbers; Ramsey numbers of trees; Ramsey numbers of $K_{s,t}$; high average degree implies Ramsey number is large (and converse is false); $d$-degenerate; $d$ degenerate implies $r(H)>2^{\frac{d-1}{2}}$; Burr-Erdös Conjecture (and Lee's proof); Conlon-Fox-Sudakov conjecture
  • Lecture 10:
  • More on Graph Ramsey Numbers: Chvatál-Rödl-Szemerédi-Trotter theorem; Graham-Rödl-Ruciński bounds
  • Canonical Ramsey theorems: Erdös-Szekeres on long monotone subsequences (and Seidenberg's proof)
  • Lecture 11:
  • More on Canonical Ramsey theorems: rainbow coloring; starry coloring; the canonical Ramsey theorem; Lefmann-Rödl theorem; best lower bound for $ER(k)$; Abbott's theorem (improvements by Conlon-Ferber; Wigderson; Sawin)
  • Lecture 12:
  • Folkman's theorem and beyond: $q$-color Ramsey; Galluccio-Simonovits-Simonyi-Szabó theorem; Folkman's theorem; Neśetřil-Rödl $q$-color Ramsey theorem via cliques; random Ramsey theorem; maximal $2$-density; threshold; Ramsey obligatory; Triangle trees; Reiher-Rödl theorem

Experimental Math Lab

This was designed to be a "mini" REU. The core idea behind it was great, but in practice, things felt way too rushed.

Overall Thoughts

The first week was packed with lectures covering topics like spectral graph theory, Cayley graphs, polyhedra, convexity, and optimization. For me, much of this material was a review, and the pace was quite slow. The few problems we were given to solve seemed to focus heavily on calculations, and honestly, none of them really sparked my interest. I wished that they had simply replaced the lecture with a handout, which I could've read much faster.

By the second week, there were suddenly too many problems that I wanted to try. Most of this came from the open problem session, the GSS lectures, and some problems that my friends gave me.

However, just as I was getting into the swing of things, the start of the third week arrived, and with it we needed to present our work. The presentation itself was a good experience, as a large crowd of about 100 people showed up, and it was fun to share what we'd been doing. The challenge was that I had only five minutes to present on a problem I had been exploring for just two days! You can see the initial ideas in our slides here.

What I Worked On
  • $P_3$ intersecting families: This problem was incredibly frustrating. After analyzing the graph that achieved the 17/128 bound, we gained no intuition about why this graph works and how we might extend it to beat the bound. We wrote a lot of code and tested countless possibilities, trying to force a solution. Our efforts led us to believe there likely isn't a simple, small counterexample. We're stuck without a clear plan for what to do next. I've come to think that 17/128 might be the best possible answer, though I have no idea how to prove it. I also suspect the Christofides graph is the only graph that achieves this result, but my research partner doesn't agree. I'm done with thinking about this problem for now, since I don't have any ideas.

  • Polyomino bisections: I spent most of my time working on this problem, and consistently made progress. I'm pretty sure we can push the lower bound to 2.1, and I think the conjectured upper bound is correct too. The only "issues" are that I haven't written all of the details up (and fear that it will be 50+ pages), and that my methods mix percolation theory, statistical mechanics, and saddle point methods. I'd never worked with any of these before this project, so there's a chance I'm making a silly beginner error. Hopefully everything is correct, as I'm going to keep working on this problem after PCMI since I think we're reasonably close to a paper.

Update (as of November 2): Ironically, the first paper has led to a paper, whereas the second project is more or less abandoned.

Graduate Summer School

There were 9 graduate summer school lectures, which we were allowed to attend. I generally slacked off and did not show up to too many of these, but attempted to read the lecture notes afterwards so I could go at my own pace.

Week 1

Intersecting Families by Imre Leader
  • Harper's Theorem: Boundary; Isoperimetric inequality; neighborhood; ball; set system; discrete cube $Q_n$; lexicographic order; simplicial ordering; Harper's theorem (lemma; corollary); Hamming ball; Kruskal-Katona theorem; $i$-sections; $i$-compression; $t$-neighborhood
  • Intersecting Families: Intersecting family; maximum size of intersecting family; Erdös-Ko-Rado theorem; Katona's $t$-intersecting theorem; Second Erdös-Ko-Rado theorem; Frankl conjecture
  • Covering by Intersecting Families: Kneser's conjecture; Borsuk-Ulam theorem (and equivalent statements via antipodals); Lusternik-Schnirelmann theorem; Kneser graph; chromatic color of Kneser graph
  • Modular Intersection Theorems: Theorem on odd $r$-uniform $|x\cap y|$ families; Frankl-Wilson theorem (and corollary)
  • Borsuk's Conjecture: Kahn-Kalai theorem
  • Projections: projection; brick/box; body; $|S|^2 \le |S_{12}| |S_{13}| |S_{23}|$ for bodies in $\mathbb{R}^3$; $n$-sections; $k$-uniform cover; Uniform covers theorem (Loomis-Whitney theorem; Corollary for $A\subset Q_n; Bollobás-Thomason box theorem)
  • Intersecting Families of Graphs: Ellis-Filmus-Friedgut theorem (and $|A|\le (1/4)2^{\binom{n}{2}}$ theorem); common graph; Alon's common graphs conjecture

Asymptotic Enumeration via Graph Containers and Entropy by Jinyoung Park
  • Introduction and Entropy: Independent sets and examples ($d$ regular $n$ vertices bipartite; $Q_d$); Korshunov-Sapazhenko theorem; graph homomorphism and examples (proper coloring; $1$-Lipshitz function); Entropy (properties; Shearer's lemma); $i(G) \le 2^{(1+O\left(\frac{1}{d}\right))n/2}$ theorem
  • Graph Containers: (system of) containers; proof of $i(G) \le 2^{(1+O\left(\frac{1}{d}\right))n/2}$ theorem using containers; $i(Q_d) \sim 2\sqrt{e}2^{N/2}$ proof; $2$-linked
  • Independent Sets & Containers (Lectures 3, 5): Bounding $i(Q_d)$; 2-linked sets; "closure" $[A]$; basic containers too expensive; $\psi$-Approximation (S,F) (defined by degree conditions $d_F \ge d-2\psi$, $d_S \le \psi$); CL1 (Constructing Containers); CL2 (Specifying from Containers); CL2 proof (specify $N(A) \setminus F$ then $A \subseteq [A]$, savings from $t = |N(A)| - |[A]|$); CL1 proof (crude cover $B$, refinement algorithm: Phase 1 Grow $F'$, Phase 2 Shrink $S'$).
  • Colorings of $Q_d$ (Lecture 4): Graph colorings; graph homomorphisms; "flaws" vs. "ground state"; $C_4(Q_d) \sim 6 \cdot e \cdot 2^N$ (Kahn-P.); problematic 2-linked flaw sets; containers (CL2) too expensive; Method: Entropy ($H(f) = \sum T(x)$); specify colorings directly from container (S,F); "driving force penalty" from $z \in F$ (small $T(z)$) overcomes "overpay" from $y \in N(S) \setminus F$.

Extremal Graph Theory by Daniel Conlon
  • Classical Results: Mantel's theorem; Turán's theorem; Erdös-Stone theorem; Kövari-Sós-Turán theorem; examples ($K_{2,2}$ free construction; $K_{3,3}$ free construction; $K_{s,t}$ when $t=(s-1)!+1$; Wegner's construction)
  • Random Algebraic Method: $\text{ex}(n, K_{2,t})\ge cn^{2-\frac{1}{s}}$; 5 algebraic geometry lemmas; Conlon's theorem on Kollár-Rónyai-Szabó for the even cycle problem; Bukh-Conlon theorem on rational exponents conjecture; converse of rational exponents conjecture; compactness conjecture
  • General Upper Bounds: Dependent random choice; $\text{ex}(n,H)\le cn^{2-\frac{1}{\Delta}}$ theorem; $d$-degenerate (Erdös conjecture; Alon-Krivelevich-Sudakov theorem); Conlon-Lee on $\text{ex}(n,H)\le cn^{3/2-\delta}$; almost $K$-regular; 3 lemmas, reduction statement, and corollary for $\text{ex}(n, C_6)=O\left(n^{4/3}\right)$; Conlon-Lee conjecure and analogs (Sudakov-Tomon; Janzer-Sudakov; Baek-Conlon-Lee); Mubayi-Verstraëte connecton between extremal number of subdivisions with off-diagonal Ramsey numbers (and subsequent work by Mattheus-Verstraëte)
  • Counting Results: Conlon-Fox-Sudakov theorem (3 lemmas proof and entropy proof);

Week 2

Statistical Physics Approach to Asymptotic Enumeration and Large Deviations in Random Graphs by Will Perkins
  • Foundations: spin models on graphs; spin configurations; energy functions; hard constraint; partition function; Gibbs measure; (anti)ferromagnetic Ising model; hard-core lattice gas; Potts model; ground states; monomer-dimer model (edge coloring model); spin models on hypergraphs (multibody interaction); Gibbs point processes (continuum models); Markov random field; local function; observable; cumulants; multivariate hardcore partition function; (consistency) for a non-uniform external fields; correlations; marginal probability; $k$-point correlation function; truncated 2-point correlation function; decay of correlations; joint cumulants; truncated $k$-point correlation; equilibrium measure; mixing time; phase transitions (and three examples); boundary conditions on a Gibbs measure; specification of a spin model; pressure at inverse temperature; notions of phase transition (uniqueness, analyticity, correlation decay)
  • Combinatorics and Statistical Physics: Kahn's theorem for independent sets in $d$-regular graphs; Kahn-Galvin-Tetali-Zhao extension; Shearer's theorem (and resulting upper bound on $R(3,k)$); occupancy fraction; Davies-Jenssen-Perkins-Roberts two theorems (and corollary); primal LP; dual LP; weak/strong duality theorems for LP; (theorem) on complementary slackness; two conjectures on lower bound of $R(3,k)$; Bregman's matching theorem (and corollary); Kahn-Lovasz perfect matching theorem; Davis-Jenssen-Perkins-Roberts theorem
  • Cluster Expansion: equation of state; ideal gas; Ursell function; clusters; Shearer's theorem on optimal zero-free (poly)disk for graphs; Shearer's theorem on rate of convergence; theorem specializing the Kotecký-Preiss condition; Shearer's connection to Lovász Local Lemma (and corollary); lemma deducing correlation decay from cluster expansion; examples of polymor models (multivariate hard-core model; ferromagnetic Ising model); Kotecký-Preiss condition for convergence of cluster expansion for abstract polymer models; expander graphs; $\alpha$-edge-expander; $\alpha$-vertex expander; $\epsilon$-spectral expander; bipartite $\alpha$ expander; lemma on ferromagnetic Potts model on expander graphs

Ramsey Theory on Graphs by Julian Sahasrabudhe
  • Basics: Erdös-Szekeres theorem; corollary for diagonal Ramsey numbers; upper bounds for $R(3,k)$; lower bound for $(1-o(1))\frac{k}{2\sqrt{2}}2^{k/2}$; Erdös $R(3,k)$ lower bound; Markov's inequality (corollary and two facts)
  • Deletion methods and upper bounds: Erdös $R(k)$ lower bound (proof via theorem and 2 lemmas); Ajtai-Komlós-Szemerédi upper bound on $R(3;k)$; Shearer's random greedy process theorem
  • Kim's theorem: Kim's bound for $R(3,k)$; heurestic for the terminating density of the triangle-free process; heuristic for the independence number; the triangle-free nible process; proof of well-running

Sublinear Expander Graphs by Matija Bucić
  • (Sub)linear Expanders: $\epsilon$-expanders; Diameter bound lemma; lemma on a weaker version of the DFS method of Ben-Elize-Krivelevich-Sudakov; robust sublinear expander (and lemma)
  • Applications of pass to expander lemmas: topological clique; Bollobás-Thomason-Komlós-Szemerédi theorem; rainbow coloring; proper edge coloring; 2 major theorems on rainbow cycles
  • Decomposition: $(\epsilon, s)$-expander (and lemma); Erdös-Gallai cycle decomposition conjecture (Lovász theorem; corollary; $O(n\log^*n)$ cycles and edges theorem; $O(n)$ cycles and $n\log^{O(1)}n$ edges theorem; $O(n)$ cycles and $n\log^{O(1)}d$ edges; $O(n)$ cyles and $O(n^{2-\epsilon})$ edges)

Week 3

Enumeration of Regular Graphs by Anita Liebenau
  • Asymptotic Enumeration of Regular Graphs: Main problem (counting $|\mathcal{G}(d)|$); degree sequences; $d$-regular graphs $\mathcal{G}(n,d)$; exact counting (1-reg, 2-reg); overview of sparse, dense, and intermediate methods.
  • Method 1: The Configuration Model (Sparse): Bender, Canfield, Wormald, Bollobás ($d=o(n^{1/2})$); cells, points, configurations $P$, multigraph $G(P)$; $Pr(Simple)$; loops ($X_1$), double edges ($X_2$); Theorem 3.3 (Bollobás 1983); Poisson heuristic; Method of Moments (Lemma 3.4, 3.5); McKay-Wormald switchings ($d=o(n^{1/3})$, $d=o(n^{1/2})$); factorial moments $M_k$; Theorem 3.6.
  • The Binomial Approximation Conjecture: $G_{n,m}$; edge density $\mu(d)$; scaled variance $\gamma_2(d)$; independent binomials $\mathcal{B}_p(n)$; conditioned binomials $\mathcal{B}_m(n)$; Formula (4).
  • Method 2: Generating Functions & Saddle-Point (Dense): $d=\Omega(n/log~n)$; $\prod (1+x_i x_j)$ generating function; coefficient extraction; multivariate Cauchy's integral formula; Saddle-point method.
  • Method 3: Recursive Relations (Intermediate): $d=o(n^{2/5}/\log n)$; probabilistic view $\Omega_m$; Lemma 5.1 (ratio/sum approximation); concentration (Hypergeometric, $\mathcal{D}_m$); local change graph $S$; degree switch ($d \to d-e_a+e_b$); Crucial Ratio Lemma (CRL, Lemma 5.6); recursive formulae for ratios ($R_{(a,b)}$), edge probability ($P_{av}$), 2-path probability ($Y_{avb}$); $Bad$ events; iterative approximation; fixed point method; operators ($\mathcal{R}, \mathcal{P}, \mathcal{Y}$); Contraction Lemma.

From Sunflowers to Thresholds by Shachar Lovett
  • Introduction to the sunflower conjecture: sunflower; $SF(n,r)$ (definition and bound); Erdös-Rado sunflower conjecture (lemma; Kostochka; Fukuyama; Alweiss-Lovett-Wu-Zhang; Frankston-Kahn-Narayanan-Park; Rao + Tao's applications in information theory; Bell-Chueluecha-Warnke; Park-Pham); $\text{ES}(N,r)$ (definition and upper bound); Erdös-Szemerédi sunflower conjecture; Erdös-Rado implies Erdös-Szemeredi (Alon-Shipilka-Umans; Ellenberg-Gijswijt on cap-set conjecture)
  • Improved bounds via spread lemma: improved bound for the sunflower conjecture; link; spread family; reduction to spread families; $p$-biased set; spread lemma; spread families contain many disjoint sets; robust sunflower; robust sunflower lemma; spread lemma for high success probability; spread lemma for fixed set size; minimal fragments (and 4 claims)
  • Threshold phenomena, and a proof of the Kahn-Kalai conjecture: critical probability; Hamiltonian cycles; "naive" expectation threshold; $p_C(\mathcal{F}) \ge p_E^*(\mathcal{F})$; unions of Hamiltonian cycles and 4-cliques; span; cover; $p_C(\mathcal{F})\ge p_C(\mathcal{G})$; expectation threshold; expectation threshold lower/upper bound; Kahn-Kalai conjecture; minimal fragments
  • Application: lower bounds of monotone circuits: partial order; monotone function; min-term of a monotone function; majority function; monotone circuit; $\text{Clique}_{m,k}(x)$; Rossman theorem; non-monotone circuits; closed monotone functions (lemma and definition); closure of monotone function (and generalization lemma); connection between min-terms of closed monotone functions and robust sunflowers (and corollary); circuit closure; if $\mathcal{C}$ is small then $\overline{\mathcal{C}}$ approximates $\mathcal{C}$ well; Janson's inequality

Arithmetic Ramsey Theory by Sarah Peluse
  • Coloring Results: van der Waerden's theorem
  • Density Results: Szemerédi's theorem (and equivalent formulation); Bergelson-Leibman theorem; Roth ($k=3$) and Gowers ($k\ge 4$) bounds for Szemerédi's theorem; Peluse-Prendiville theorem
  • Repeatedly applying the Cauchy-Schwarz inequality: Bourgain-Chang theorem; Shkredov theorem; definition of $\Lambda$; theorem on $\Lambda(f,g,h)$ for 1-bounded $f,g,h$ (lemma and proposition for proof)
  • Density-Increment Method: Furstenberg-Sárközy theorem; density increement lemma
  • Fourier-analytic preliminaries: Fourier transform; convolution; standard properties of the Fourier transform; log-free variant of the quadratic Weyl inequality
  • Control by Gowers Norms: Basic properties of the Fejer kernel; discrete derivatives; Gowers box and uniformity norms; can der Corput's inequality; $U^2$ control of three-term APs; $U^2$ inverse theorem
  • PET Induction and Concatenation: PET induction scheme; PET lemma (Peluse-SEAN?? variant and corollary)
  • Quantitative Concatenation: 2 lemmas; stashing; Peluse's degree lowering theorem; Major arc lemma

Other

Nonacademics

I guess I did some nonacademic stuff too, though most of what I remember is walking through Walmart aisles looking for food, making dinner, and playing basketball/tennis. Still, there were a few things that stood out.

  • The Clayton Peak Hike. The hike was scarier than I expected. We had to climb over tall, jagged rocks, and the drops beside the trail were steep enough to make my stomach twist. I didn’t know anyone in the group, and we barely talked. But reaching the top felt peaceful, like the silence finally made sense. On the way back, the clouds spread out in strange shapes, soft and gray, like they were watching over us.
  • Climbing The Largest Ski Resort in the US. I did this one alone. I got lost for a while, and the sun was starting to go down. The mountain was quiet and beautiful in that late light. On the way down, I somehow ended up on a half-built biking trail with huge dirt jumps and loose gravel everywhere. I even saw a few snakes along the way. It felt a little sketchy, but I made it back just before dark.
  • Old Town and the Art Galleries. There was one street lined with art galleries, one after another. I didn’t expect much, but every place had something that made me stop: a painting, a sculpture, a small detail that felt full of care. It was quiet and colorful all at once. Strange how one street could hold so much beauty, just sitting there, waiting for people to notice.
  • 80's Night Out Concert. On the last night, there was a concert right by the hotel. I wandered up a little ways on the nearby mountain and ended up watching it for free. I’ve never been to a concert before, so it felt a bit strange, but it was amazing to see all the lights dancing in patterns and to watch so many people just enjoying themselves. There was something quietly magical about being just far enough away to feel part of it, but still on my own.

Final Reflection

It's over. Three weeks feels like a whole season in the mountains. My head is still full of the noise of Ramsey numbers and the strange, quiet beauty of probabilistic proofs. It felt good, the chase.

But the real secret of this place wasn’t on the blackboards. It was the mountains. They were just there, huge and silent, watching us work. The climb up the resort alone, those moments of getting lost in the late light, the trip to that beautiful street of art... together, they brought a quiet I didn't know I needed.

I think the math and the mountains taught the same thing: You just keep moving, keep climbing, even when you can’t see the top. You just trust that the hard work (the layers of induction, the steep gravel trails) will eventually lead you to a point of peace, a point where the view finally makes sense. Now, it's time to head down, but I’m bringing a piece of the stillness and the struggle back with me. I feel full. And very, very tired.