# Combinatorics Colloquium

## Spring 2023

### February 9, 2023, 4pm CT Location: TBA

Speaker: Gregg Musiker (U. Minnesota)
Title: Super Cluster Algebras from Surfaces
Abstract:
This talk will provide an introduction to cluster algebras from surfaces, and their generators, known as cluster variables. We will also describe how certain combinatorial objects known as snake graphs yield generating functions that agree with Laurent expansions of said cluster variables. In recent years, a lot of progress has been made on the problem of defining a super-commutative analogue of Fomin-Zelevinsky’s cluster algebras. In recent joint works with Nick Ovenhouse and Sylvester Zhang, we began the project of exploring the super cluster algebra structure from Penner-Zeitlin’s decorated super Teichmüller space, generalizing the notion of (classical) cluster algebras from triangulated surfaces. In this colloquium talk, I will survey our recent works on combinatorial and matrix formulas for super lambda-lengths, proving super-analogues of combinatorial features such as the Laurent Phenomenon and positivity. Such formulas again utilize snake graphs but using double dimer covers rather than single dimer covers. If time permits I will also discuss applications to super Fibonacci and super Markov numbers, as well as connections to super-frieze patterns. This talk is based on joint works with Nick Ovenhouse and Sylvester Zhang (arXiv 2102.09143, 2110.06497 and 2208.13664) and will not assume prior knowledge of cluster algebras.

### January 19, 2023, 2pm CT Everitt Lab (room number 2310)

Speaker: Sarah Peluse (Princeton U.)
Title: Arithmetic patterns in dense sets
Abstract:
Some of the most important problems in combinatorial number theory ask for the size of the largest subset of the integers in an interval lacking points in a fixed arithmetically defined pattern. One example of such a problem is to prove the best possible bounds in Szemer\’edi’s theorem on arithmetic progressions, i.e., to determine the size of the largest subset of {1,…,N} with no nontrivial k-term arithmetic progression x,x+y,…,x+(k-1)y. Gowers initiated the study of higher order Fourier analysis while seeking to answer this question, and used it to give the first reasonable upper bounds for arbitrary k. In this talk, I’ll discuss recent progress on quantitative polynomial, multidimensional, and nonabelian variants of Szemer\’edi’s theorem and on related problems in harmonic analysis and ergodic theory.

## Fall 2022

### November 17, 2022, 4pm CT Altgeld Hall (room number 245)

Speaker: Laura Escobar (Washington University, St. Louis)
Title: Measuring polytopes
Abstract: This will be an expository talk aimed at a broad audience, including beginning graduate students.

A polytope is a convex bounded polyhedron. There are many ways to measure a polytope: dimension, number of vertices, volume, number of lattice points inside the polytope, etc. A wide variety of problems in pure and applied mathematics involve measuring a polytope. For example, as we will see, even computing the dimension of a polytope can have geometric consequences for subvarieties of the flag variety. However, many of these measuring problems are very complex: there is no procedure that can efficiently measure any polytope. In this talk we will discuss these problems concentrating on families of polytopes which are of special interest due to their symmetries.

Addendum to department-wide announcement: There will be an opportunity to meet with Professor Escobar over pizza (confirmed) in 321 AH at noon on Nov 17, and over cookies (confirmed) in the same room at 3pm.

### October 24, 2022, 2pm CT Altgeld Hall (room number 245)

Speaker: Martin Mandelberg
Title: What you should learn about Richard Wesley Hamming
Abstract: This lecture presents the life, legacy and some timeless lessons from Dr.  Wesley Hamming (1915-1998), a remarkable
mathematician (alumnus of Illinois Math (PhD Trjitzinsky)), computer scientist, educator, mentor, and polymath.

During his career, Hamming developed numerous solutions in academia, government service, and industry. He helped form the foundation of modern computing science, coding and information theory, digital filters, and numerical methods. His better-known contributions include Error Correcting Codes (ECC), the Hamming window, and the Hamming distance.

Hamming wrote ten books, over a hundred articles, and gave many notable lectures. He received significant recognition for his work, including the 1968 ACM Turing Award, the 1986 IEEE Hamming Award, and the 1996 Eduard Rhein Foundation Award. Besides these and additional honors, many of his other contributions over decades generally remain unknown to subsequent generations of mathematicians, and engineers.

The speaker undertook the Richard Wesley Hamming Legacy Project to establish and perpetuate Hamming’s legacy.
Project results include the Hamming Open Access Archive (HOAA) and the legacy tribute biography – MAN, MATHEMATICIAN, AND MENTOR: RICHARD WESLEY HAMMING. Drawing from the archive and the biography, this lecture presents a chronology with photographs, videos, and anecdotes to describe this determined and innovative deep thinker who strove for excellence. After paraphrasing some of Hamming’s guidance for scientists and engineers, Dr. Mandelberg will entertain questions from the audience.

Martin Mandelberg is an engineer, strategist, mathematician, computer scientist, and educator with 50 years experience in government, industry, and academia. Mandelberg is Hamming’s protégé, only Doctoral Student, and created the Richard Wesley Hamming Legacy Foundation, and author of Man, Mathematician, and Mentor: Richard Wesley Hamming.

### Sept 1, 4pm CT Altgeld Hall (room number 245)

Speaker: Igor Pak, UCLA
Title: Combinatorial inequalities
Abstract: In the ocean of combinatorial inequalities, two islands are especially difficult. First, Mason’s conjectures say that the number of forests in a graph with k edges is log-concave. More generally, the number of independent sets of size k in a matroid is log-concave. These results were established just recently, in a remarkable series of papers by Huh and others, inspired by algebro-geometric considerations.

Second, Stanley’s inequality for the numbers of linear extensions of a poset with value k at a given poset element, is log-concave. This was originally conjectured by Chung, Fishburn and Graham, and famously proved by Stanley in 1981 using the Alexandrov–Fenchel inequalities in convex geometry. No direct combinatorial proof for either result is known. Why not?

In the first part of the talk we will survey these and other combinatorial inequalities. We then mention what does it mean not to have a combinatorial interpretation. Finally, I will briefly discuss our new framework of combinatorial atlas which allows one to give elementary proofs of the two results above, and extend them in several directions. The talk is aimed at the general audience.

### Sept 8, 4pm CT Altgeld Hall (room number 245)

Speaker: Xuding Zhu, Zhejiang Normal University, China
Title: List version of the 1-2-3 Conjecture
Abstract: The well-known 1-2-3 Conjecture by Karo\'{n}ski, {\L}uczak, and Thomason states that the edges of any connected graph with at least three vertices can be assigned weights 1, 2 or 3 so that for each edge $uv$ the sums of the weights at $u$ and at $v$ are distinct.

The list version of the 1-2-3 Conjecture by Bartnicki, Grytczuk, and Niwczyk states that the same holds more generally if each edge $e$ has the choice of weights not necessarily from $\{1,2,3\}$, but from any set $\{x(e),y(e),z(e)\}$ of three real numbers.

The goal of this talk is to survey developments on the 1-2-3 Conjecture, especially on the list version of the 1-2-3 Conjecture.

## Spring 2022

### May 18, 11am CT Altgeld Hall (room number TBD)

Speaker: Wojciech Samotij, Tel Aviv University
Title: The upper tail for triangles in random graphs
Abstract: Let $X$ denote the number of triangles in the random graph $G_{n,p}$.  The problem of determining the asymptotics of the logarithimic upper tail probability of $X$, that is, $\log \Pr(X > (1+\delta)\mathbb{E}[X])$, for every fixed positive $\delta$ has attracted considerable attention of both the combinatorics and the probability communities.  We shall present an elementary solution to this problem, obtained recently in a joint work with Matan Harel and Frank Mousset.  The crux of our approach is a simple probabilistic argument, inspired by the work of Janson, Oleszkiewicz and Ruci\’nski, that reduces the estimation of this upper tail probability to a counting problem

### April 14, 10am CT 245 Altgeld Hall

Speaker: Andrew Treglown, U. Birmingham, UK, Fulkerson Prize recipient (2021)
Title: Tiling in graphcs
Abstract: Given two graphs H and G, an H-tiling in G is a collection of vertex disjoint copies of H in G. Thus, an H-tiling is simply a generalisation of the notion of a matching (which corresponds to the case when H is an edge). An H-tiling in G is perfect if every vertex of G is covered by the H-tiling. Over the last 60 years there have been numerous results on perfect H-tilings. In this talk we give a high-level overview of some of the key ideas that permeate the topic. In particular, we will discuss some typical behaviour of extremal examples, and also some complexity questions.

## Fall 2021

### December 2, 4pm CT 245 Altgeld Hall

Speaker: Chandra Checkuri (UIUC Computer Science Dept.)
Title: On Submodular k-Partitioning and Hypergraph k-Cut
Abstract: Submodular $k$-Partition is the following problem: given a submodular set function $f:2^V \rightarrow \mathbb{R}$ and an integer $k$, find a partition of $V$ into $k$ non-empty parts $V_1,V_2,\ldots,V_k$ to minimize $\sum_{i=1}^k f(V_i)$.  Several interesting problems such as Graph $k$-Cut, Hypergraph $k$-Cut and Hypergraph $k$-Partition are special cases.  Submodular $k$-Partition admits a polynomial-time algorithm for $k=2,3$ and when $f$ is symmetric also for $k=4$.  The complexity is open for $k=4$ and when $f$ is symmetric for $k=5$.

In recent work, motivated by this problem, we examined the complexity of Hypergraph $k$-Cut which only recently admitted a randomized polynomial-time algorithm. We obtained a deterministic polynomial-time algorithm for Hypergraph $k$-Cut as well as new insights in to Graph $k$-Cut. The ideas also led to a polynomial-time algorithm for Min-Max Symmetric Submodular $k$-Partition for any fixed $k$.

The talk will discuss these results with the goal of highlighting the open problem of resolving the complexity of Submodular $k$-Partition.

Based on joint work with Karthik Chandrasekharan

### November 4, 2pm CT 443 Altgeld Hall

Speaker: Zoltan Furedi, (Renyi Institute, Hungary and UIUC)
Title: Algebraic constructions in combinatorics
Abstract: There are two main sources to produce non trivial combinatorial structures. One can use probability theory for typical cases and a bit of algebra for symmetric structures. Here we briefly review classical and new developments and also give examples on how to combine these two powerful methods.

The talk is targeting general mathematicians, with little combinatorics backgrounds.

### October 7, 2021, 4 pm CT 245 Altgeld Hall

Speaker: John Shareshian, Washington University of St. Louis
Title: A problem on divisors of binomial coefficients, and a theorem on noncontractibility of coset posets

Abstract: Fix an integer n>1. It follows directly from a theorem of Kummer that the greatest common divisor of the members of the set BC(n) nontrivial binomial coefficients nC1,nC2,…nC(n-1) is one unless n is a prime power. With this in mind, we define b(n) to be the smallest size of a set P of primes such that every member of BC(n) is divisible by at least one member of P. In joint work with Russ Woodroofe, we ask whether b(n) is at most two for every n. The question remains open.

I will discuss what we know about this question, and how we discovered it during our investigation of a problem raised by Ken Brown about certain topological spaces: Given a finite group G, let C(G) the set of all cosets of all proper subgroups of a finite group, partially ordered by containment. The order complex of C(G) is the simplicial complex whose k-dimensional faces are chains of size k+1 from C(G). We show that this order complex has nontrivial reduced homology in characteristic two, and is therefore not contractible.

If time permits, I will discuss also related work on invariable generation of simple groups, joint with Bob Guralnick and Russ Woodroofe.

### September 30, 2021, 4 pm CT 245 Altgeld Hall

Speaker: Bernard Lidicky (Iowa State University)
Title:  Flag algebras and its applications

Abstract: Flag algebras is a method, developed by Razborov, to attack problems in extremal combinatorics. Razborov formulated the method in a very general way which made it applicable to various settings.  The method was introduced in 2007 and since then its applications have led to solutions or significant  improvements of best bounds on many long-standing open problems, including problems of Erd\H{o}s.  The main contribution of the method was transferring problems from finite settings to limits settings. This  allows for clean calculations ignoring lower order terms. The method can utilize semidefinite programming  and computers to produce asymptotic results. This is often followed by stability type arguments with the  goal of obtaining exact results.

In this talk we will give a brief introduction of the basic notions used in flag algebras and demonstrate  how the method works. Then we will discuss applications of the flag algebras in different settings.

Lunch with the speaker: Thursday, September 30, 11:45 a.m., Spoon House Korean Kitchen on Green Street; meet at the restaurant.

Dinner with the speaker: Thursday, September 30, 6:30 p.m., location  to be discussed.

Additional event: Friday, October 1, 1:00-1:50 p.m. AH 447; the speakers talk with the students about their favorite problems.

### September 7, 2021, 11-11:50 am CT 347 Altgeld Hall

Speaker: Tao Jiang (Miami University of Ohio)
Title: Degenerate Turan problems for graphs

Abstract: In Turan type extremal problems, we want to determine how dense a graph or hypergraph is without containing a particular subgraph or family of subgraphs. Such problems are central to extremal graph
theory, because solving them requires one to thoroughly investigate the interaction of global graph parameters with local structures. Efforts in solving these problems have spurred the developments of some powerful tools in extremal graph theory, such as the regularity method, probabilistic and algebraic methods.

While Turan problems have satisfactory solutions for non-bipartite graphs, the  problem is still generally wide-open for bipartite graphs with many intriguing conjectures  and results. In this talk, we will discuss some conjectures on Turan problems for bipartite graphs and some recent progress on them. Time permitting, we will also discuss a colored variant of the Turan problem.

Additional event: September 9, 2021, 11-11:50 am CT, 141 Altgeld Hall, Tao Jiang’s favorite problems.