## Spring 2023

### May 9, 2023, Time 11AM-12:20PM

Location: 245 Altgeld Hall

**Speaker:** Marcelo Campos (IMPA/Oxford)

**Title:** An exponential improvement for diagonal Ramsey

**Abstract:**

The Ramsey number R(k) is the minimum natural n such that every red-blue colouring of the edges of the complete graph K_n on n vertices contains a monochromatic copy of K_k. In this talk I will present a recent result that shows R(k) < (4 - c)^k for some constant c > 0. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

This is joint work with Simon Griffiths, Robert Morris and Julian Sahasrabudhe.

### April 26, 2023, Time 2-3:20PM

Location: 119 MSEB (Material Science and Engineering Building)

**Speaker:** Alexander Razborov (U. Chicago)

**Title:** On Sparse Halves in Triangle-Free Graphs

**Abstract:**

One of Erdos’s favorite still unresolved conjectures states that every triangle-free graph on $n$ vertices has an induced subgraph on $n/2$ vertices (a “half”) with at most $n^2/50$

edges. We review known partial results in this direction, including recent contributions by the speaker. Among the latter are the new bound $27n^2/1024$ in the general case and the complete solution

for graphs of girth $\geq 5$, for graphs with independence number $\geq 2n/5$ and for strongly regular graphs. If time permits we will also give a sketch of a proof.

### March 9, 2023, Time 1pm

Location: 223 Gregory Hall

**Speaker:** Zander Kelley (UIUC)

**Title:** Strong Bounds for 3-Progressions

**Abstract:**

We show that for some constant β>0, any subset A of integers {1,…,N} of size at least 2^{−O((log N)^β)} N contains a non-trivial three-term arithmetic progression. Previously, three-term arithmetic progressions were known to exist only for sets of size at least N/(log N)^1+c for a constant c>0.

Our approach is first to develop new analytic techniques for addressing some related questions in the finite-field setting and then to apply some analogous variants of these same techniques, suitably adapted for the more complicated setting of integers.

This is joint work with Raghu Meka.

### February 9, 2023, 4pm CT

Location: 245AH

**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.