# Combinatorics Colloquium

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