Document Type
Lecture
Publication Date
10-16-2024
Abstract
Among all bodies of a fixed volume, the ball has the smallest surface area. Among all ideals in R[x1,..., xn] generated by a fixed number of monomials of degree d, the one with the fewest monomials of degree d + 1 is the lex-ideal. These are two very different sounding facts, but are in fact both examples of isoperimetric problems, which ask: among all objects of a particular size, which has the smallest boundary? In this talk, we’ll focus on the discrete setting, where isoperimetric problems take the form: given a graph G, among all subsets of the vertices of a fixed size, which has the smallest neighborhood? In general, this is a very hard question to answer, but every so often, there is a beautiful solution. Twoof the most amazing solutions arise from nice grids on Zn, namely the ℓ∞ and ℓ1 grids. In both cases, there is a well-ordering of Zn such that initial segments are always optimal for the isoperimetric problem! Motivated by these examples and other evidence, Barber–Erde recently asked if this phenomenon continues for any Cayley graph on Zn. We show that the answer is “no”, even in the case of n = 1 by constructing Cayley graphs whose isoperimetric problem undergoes an abrupt “phase transition”. The construction is motivated by the realization that one can mimick small-scale higherdimensional phenomena in low dimensions. Time permitting, we will also discuss more recent work on the isoperimetric problem on the bounded ℓ∞ grid, which we can show exhibits many phase transitions, and introduce a new notion which we dub “iso-complexity”. (Joint with with Joe Briggs) (Time permitting: joint with Ben Baker, Joe Briggs and Manuel Fernandez)
Relational Format
presentation
Recommended Citation
Wells, Chris, "Phase transitions in isoperimetric problems" (2024). Combinatorics Seminar. 6.
https://egrove.olemiss.edu/math_combinatorics/6
