Combinatorics Colloquium

Fall 2021

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.

Previous Colloquia

Spring 2021

Fall 2020