Spring 2024
April 4, 2024, Time 3-4pm
Location: 245AH
Speaker: Steven Karp (Notre Dame)
Title: Positivity in real Schubert calculus
Abstract:
Schubert calculus involves studying intersection problems among linear subspaces of C^n. A classical example of a Schubert problem is to find all 2-dimensional subspaces of C^4 which intersect 4 given 2-dimensional subspaces nontrivially (it turns out there are 2 of them). In the 1990’s, B. and M. Shapiro conjectured that a certain family of Schubert problems has the remarkable property that all of its complex solutions are real. This conjecture inspired a lot of work in the area, including its proof by Mukhin-Tarasov-Varchenko in 2009. I will present a strengthening of this result which resolves some conjectures of Sottile, Eremenko, Mukhin-Tarasov, and myself, based on surprising connections with total positivity, the representation theory of symmetric groups, symmetric functions, and the KP hierarchy. This is joint work with Kevin Purbhoo.
March 21, 2024, Time 4-5pm
Location: 245 Altgeld Hall
Speaker: Greta Panova (University of Southern California)
Title: Computational Complexity in Algebraic Combinatorics
Abstract:
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 \neq 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.
February 22, 2024, Time 4-5pm
Location: 245 Altgeld Hall
Speaker: Hal Kirstead (Arizona State)
Title: Sparsity from a game theoretic perspective
Abstract:
In many applications of graph theory to computer science, operations research, logic, and
game theory, people are interested in various notions of sparse graphs—graphs with few edges.
Common examples include graph classes whose members have bounded maximum degree,
bounded genus, or bounded tree-width. Nesetril and Ossona de Mendez introduced a formal
classification of sparsity for infinite classes of finite graphs with the notion of classes with
bounded expansion and the more general notion of nowhere-dense classes. This classification,
which includes the motivating examples mentioned above, is informative as there are many
interesting properties shared by all such sparse classes. Furthermore, interesting properties
of specific classes can often be generalized to all classes, while results on general classes can
often be sharpened for specific classes. Additionally, this formulation is remarkably robust;
there are many apparently disparate notions that are in fact equivalent. In this talk I will
discuss how this theory has benefitted from the study of graph coloring games and graph
ordering games
February 1, 2024, Time 1-1:50pm
Location: Gregory Hall 223
Speaker: Adam Wagner (Worcester Polytechnic Institute)
Title: The largest isosceles triangle-free subset of the grid
Abstract:
How many points can we pick in the N by N grid, without choosing three points that satisfy d(a,b) = d(b,c), i.e. a (possibly flat) isosceles triangle? This beautiful question was recently asked by Jordan Ellenberg. I will start by discussing the little we managed to prove about the asymptotics of this function. In the second half of the talk, we will look at the structure of the optimal constructions for small values of N. The best known constructions, found by computer searches for small values of N, clearly follow a pattern which we do not yet understand. We will discuss how one can train transformers to understand this pattern, and use this trained transformer to help us find a bit better constructions for various N.
This is joint work with Jordan Ellenberg, Marijn Heule, Yuval Wigderson, and Geordie Williamson
Fall 2023
November 30, 2023, Time 11AM-11:50PM
Location: Transportation Building 114
Speaker: Hoi Nguyen (Ohio State University)
Title: Algebraic and Combinatorial statistics of random integral matrices
Abstract:
For many random matrix models of integral entries (including 0-1 matrices) we discuss the distribution of their coranks and cokernels. Using tools from combinatorics and probability, we show that these statistics are universal within their symmetry class, given by precise formulas involving zeta values, and agree with distributions defined by Cohen and Lenstra.
November 2, 2023, Time 4-4:50PM (Department Colloquium)
Location: 180 Bevier Hall
Speaker: Jinyoung Park (NYU)
Title: On some variants of Dedekind’s Problem
Abstract:
The Dedekind’s Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice [2]^n. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean lattice is an antichain, the logarithm of a(n) is trivially bounded below by the size of the middle layer. In 1960’s, Kleitman proved that this trivial lower bound is optimal in the logarithmic scale, and the actual asymptotics was also proved by Korshunov in 1980’s. In this talk, we will discuss recent developments on some variants of Dedekind’s Problem. Based on joint work with Matthew Jenssen, Alex Malekshahian, Michail Sarantis, and Prasad Tetali.
September 26, 2023, Time 1pm-1:50PM
Location: Transportation Building 112
Speaker: Dhruv Mubayi (UIC)
Title: Randomness and determinism in Ramsey theory
Abstract:
For many decades randomness proved to be the central paradigm in Ramsey theory. Recent results suggest, however, that optimal constructions in the field may involve a subtle blend of randomness and determinism. We will illustrate this by surveying many recent results, mainly about graph and hypergraph Ramsey numbers.
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.