Marcus Michelen's Homepage

10th Lake Michigan Workshop on Combinatorics and Graph Theory

The Lake Michigan Workshop on Combinatorics and Graph Theory is an annual two-day workshop that rotates between universities in the Lake Michigan region. This year's workshop is taking place on April 5 and 6, 2025 at the University of Illinois, Chicago. Support for travel and accommodation is available for early-career participants.

Registration

Registration opens on February 6 and is available here. If you are seeking travel funding, please register before March 5. Otherwise, please register before April 1.

Program

The workshop consists of three two-lecture tutorials and two other shorter talks. The tutorials will be given by:

Rose McCarty (Georgia Tech)

Greta Panova (USC)

Mehtaab Sawhney (Columbia)

Our two other speakers are:

Swee Hong Chan (Rutgers)

Abhishek Methuku (UIUC)

Schedule

Day 1: April 5

8-9: Welcome and coffee
9-10: Rose McCarty Lecture 1
10:30-11:30: Rose McCarty Lecture 2

11:30-12PM: Abhishek Methuku

12-2: Lunch break

2-3: Greta Panova Lecture 1
3:30-4:30: Greta Panova Lecture 2

Day 2: April 6

8-9: Coffee part 2
9-9:30: Swee Hong Chan
9:30-10:30: Mehtaab Sawhney Lecture 1
11-12: Mehtaab Sawhney Lecture 2

Titles and Abstracts

Rose McCarty

Structural graph theory and first-order logic

Over the last ten years, many wonderful connections have been established between structural graph theory and finite model theory. The goal is to understand which classes of graphs are 'complicated' and which are 'simple'. We discuss this area with an eye towards open problems. We do not assume any familiarity with logic or model theory.

Greta Panova

Talk 1: Computational Complexity in Algebraic Combinatorics

Algebraic Combinatorics studies objects and quantities originating in Algebra, Representation Theory and Algebraic Geometry via combinatorial methods, finding formulas and neat interpretations. Some of its feats include the hook-length formula for the dimension of an irreducible symmetric group (S_n) module, or the Littlewood-Richardson rule to determine multiplicities of GL irreducibles in tensor products. Yet some natural multiplicities elude us, among them the fundamental Kronecker coefficients for the decomposition of tensor products of S_n irreducibles, and the plethysm coefficients for compositions of GL modules. Answering those questions could help Geometric Complexity Theory towards establishing lower bounds for the far-reaching goal to show that P is not NP.
We will discuss how Computational Complexity Theory provides a theoretical framework for understanding what kind of formulas or rules we could have. As a proof of concept we show that the square of a symmetric group character could not have a combinatorial interpretation. Based on joint works with Christian Ikenmeyer and Igor Pak.

Talk 2: Algebra meets probability: permutons from pipe dreams via integrable probability

Pipe dreams are tiling models originally introduced to study objects related to the Schubert calculus and K-theory of the Grassmannian. They can also be viewed as ensembles of random lattice walks with various interaction constraints. In our quest to understand what the maximal and typical algebraic objects look like, we revealed some interesting permutons. The proofs use the theory of the Totally Asymmetric Simple Exclusion Process (TASEP). Deeper connections with free fermion 6 vertex models and domino tilings of the Aztec diamond and Alternating Sign Matrices allow us to describe the extreme cases of the original algebraic problem.
This is based on joint work with A. H. Morales, L. Petrov, D. Yeliussizov.

Mehtaab Sawhney

Hypercontractivity, Global Hypercontractivity and applications to Additive Combinatorics

Hypercontractivity, in the context of Boolean functions, is a powerful tool that states any sparse function on {0,1}n{0,1}ncannot place too much mass on "low degrees." These results form a cornerstone for the "Analysis of Boolean Functions." A known deficiency of hypercontractivity is that it does not apply in full generality to arbitrary product spaces. Recent works by Keevash, Lifshitz, Long, and Minzer, as well as Keller, Lifshitz, and Marcus, have clarified that one may prove a complete analog of hypercontractivity, provided that one assumes the underlying functions are "global." These results have been used in a host of applications, including intersecting families of permutations, diameter bounds for Cayley graphs on SnSn, character bounds on SnSn, and in recent work with Green on the Furstenberg–Sarkozy problem concerning sets avoiding square differences.

This tutorial will seek to provide an introduction to hypercontractivity, explore the role of global hypercontractivity, and offer glimpses of the proof of recent work with Green on the Furstenberg–Sarkozy problem.

Swee Hong Chan

Spanning trees and continued fractions

Consider the set of positive integers representing the number of spanning trees in simple graphs with n vertices. How quickly can this set grow as a function of n? In this talk, we discuss a proof of the exponential growth of this set, which resolves an open problem of Sedlacek from 1966. The proof uses a connection with continued fractions and advances towards Zaremba’s conjecture in number theory. This is joint work with Alex Kontorovich and Igor Pak.

Abhishek Methuku

New methods for sublinear expanders and applications

I will talk about some novel methods for sublinear expanders and their applications to some longstanding problems.

(a) We show that every graph with at least n polylog(n) edges contains two edge-disjoint cycles with the same vertex set. This resolves a problem of Erdős from 1975, which was also reiterated in different contexts by Bollobás in 1978, by Pyber, Rödl, and Szemerédi in 1995, and by Chen, Erdős, and Staton in 1996. A well-known construction of Pyber, Rödl, and Szemerédi of graphs without 4-regular subgraphs shows that the polylogarithmic factor in our result cannot be completely removed. Our proof combines a variety of techniques including absorption and a novel tool for regularisation, which is of independent interest and has several other applications. This is joint work with Chakraborti, Janzer and Montgomery.

(b) We present novel tools for constructing nearly Hamiltonian cycles in sublinear expanders, along with new techniques for finding sublinear expanders with good regularity properties in general graphs. In particular, using these tools, we make significant progress towards a long-standing conjecture of Verstraëte from 2002, which asserts that for any graph F, nearly all vertices of every d-regular graph G of order n can be covered by vertex-disjoint F-subdivisions. Among other applications, our methods also show that in every d-regular graph with sufficiently large degree, nearly all vertices can be partitioned into n/(d+1) cycles, asymptotically confirming a conjecture of Magnant and Martin (2009). This is joint work with Letzter and Sudakov.

Location and Hotels

The workshop will take place at UIC's "Academic and Residential Complex" (ARC), 507 S Morgan St, Chicago, IL 60607. There are several options of hotels nearby:

Holiday Inn & Suites Chicago-Downtown, located a 0.5 mile walk from ARC.

Crowne Plaza Chicago West Loop, located a 0.7 mile walk from ARC.

Chicago Marriott at Medical District/UIC, located a 0.8 mile walk from ARC.

ARC is also very easy to get to via public transportation from downtown Chicago, both by train and bus. The Blue Line can be taken to the UIC-Halsted stop (a 0.1 mile walk to ARC), and so many more hotels in Chicago's downtown provide easy access to UIC's campus.

Organizers

Vishesh Jain, Marcus Michelen and Dhruv Mubayi.

Acknowledgements

This workshop is supported by NSF grants TBD. We also thank UIC for hosting this workshop.
NSF Logo