Talks will begin at 9am on Saturday morning, and go through to 1pm on Sunday.
Lutz Warnke will speak on Concentration inequalities: beyond worst-case changes.
Abstract: Concentration inequalities are fundamental tools for showing that functions of random variables are tightly concentrated around their means. For a function $f(X)$ of independent random variables $X=(X_1, \ldots, X_n)$, the classic bounded differences inequality (also known as McDiarmid’s or Hoeffding–Azuma inequality) establishes sharp concentration when no single variable $X_i$ has too much influence on $f$. However, because it depends on worst-case changes, it often yields bounds that are too weak for applications. This two-talk series explores modern variants that guarantee sharp concentration when typical changes to $f$ are small, even if worst-case changes are large. We illustrate the power and broad applicability of these tools through examples from different areas.
Fan Wei will speak on Removal lemmas.
Igor Pak will speak on Combinatorial inequalities and combinatorial interpretations.
Abstract: I will give a broad survey of classical inequalities that arise in enumerative and algebraic combinatorics and how they lead to questions about combinatorial interpretations. I will then present a complexity theoretic setup which allows one to formulate negative results, and review some recent results in this direction.
Abhishek Dhawan will speak on Graph coloring via the nibble method
Abstract: Kim (1995) famously proved that graphs with maximum degree $\Delta$ and girth at least 5 satisfy $\chi(G) \leq (1+o(1))\Delta/\log \Delta$. He developed a variant of the R\”odl nibble method for graph coloring to prove this result, relying on the girth constraint to control the Lipschitz parameter when applying Talagrand’s inequality to concentrate certain random variables of interest.
In recent works, we extended this result to $K_{t, t}$-free graphs and graphs with maximum co-degree at most $\Delta^{1-o(1)}$ (the co-degree of a pair of vertices is the number of common neighbors they share). Our argument crucially relies on recent refinements of Talagrand’s inequality that accommodate exceptional outcomes.
This talk is based on joint works with James Anderson, Anton Bernshteyn, Peter Bradshaw, Abhishek Methuku, and Michael C. Wigal.
Ruilin Shi will speak on Local Permutation Removal
The permutation removal lemma was first proved by Klimosová and Král’, and later reproved by Fox and Wei in the context of permutation property testing. In this talk, we study a local version of the permutation removal problem. We show that for any permutation σ not equal to 12, 21, 132, 231, 213, or 312, there exists ε(σ) > 0 such that for any sufficiently large integer N, there is a permutation π of length N that is ε-far from being σ-free with respect to the ρ∞ distance, yet contains only a single copy of σ. Here, the ρ∞ distance is defined as an L∞-variant of the Earth Mover’s Distance between two permutations. This is joint work with Fan Wei.
Tentative schedule
Saturday 8am — Registration and breakfast, Hurley 257
Saturday 9am — Lutz Warnke talk 1, Hayes-Healy 127
Saturday 10am — Abhishek Dhawan short talk, Hayes-Healy 127
Saturday 10.30am — Break (refreshments in Hurley 257)
Saturday 11am — Lutz Warnke talk 2, Hayes-Healy 127
Saturday noon — Lunch and free discussion time
Saturday 2pm — Fan Wei talk 1, Hayes-Healy 127
Saturday 3pm — Ruilin Shi short talk, Hayes-Healy 127
Saturday 3.30pm — Break (refreshments in Hurley 257)
Saturday 4pm — Fan Wei talk 2 Hayes-Healy 127
Saturday 5pm — Break and free discussion time
Saturday 6.30pm — Workshop dinner, Jordan Hall Reading Room
Sunday 8am — Breakfast, Hurley 257
Sunday 9am — Igor Pak talk 1, Hayes-Healy 127
Sunday 10am — Swee Hong Chan short talk, Hayes-Healy 127
Sunday 10.30am — Break and free discussion time
Sunday 11.30am — Open problem session, Hayes-Healy 127
Sunday noon — Igor Pak talk 2, Hayes-Healy 127
Sunday 1pm — Lunch and free discussion time
Sunday 3pm — Workshop ends