Seminars and Colloquia by Series

High-Girth Steiner Triple Systems

Series
Combinatorics Seminar
Time
Friday, December 2, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ashwin SahMassachusetts Institute of Technology

We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth. Our proof builds on the method of iterative absorption for the existence of designs by Glock, Kü​hn, Lo, and Osthus while incorporating a "high girth triangle removal process". In particular, we develop techniques to handle triangle-decompositions of polynomially sparse graphs, construct efficient high girth absorbers for Steiner triple systems, and introduce a moments technique to understand the probability our random process includes certain configurations of triples.

(Joint with Matthew Kwan, Mehtaab Sawhney, and Michael Simkin) ​

Markov chains and sampling methods for contiguous partitions

Series
Combinatorics Seminar
Time
Friday, November 18, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Wesley PegdenCarnegie Mellon University

With applications in the analysis of political districtings, Markov chains have become and essential tool for studying contiguous partitions of geometric regions. Nevertheless, there remains a dearth of rigorous results on the mixing times of the chains employed for this purpose. In this talk we'll discuss a sub-exponential bound on the mixing time of the Glauber dynamics chain for the case of bounded-size contiguous partition classes on certain grid-like classes of graphs.

The singularity probability of a random symmetric matrix

Series
Combinatorics Seminar
Time
Friday, November 4, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Matthew JenssenUniversity of Birmingham

Let $A$ be drawn uniformly at random from the set of all $n \times n$ symmetric matrices with entries in $\{-1,1\}$. What is the probability that $A$ is singular? This is a classical problem at the intersection of probability and combinatorics. I will give an introduction to this type of question and sketch a proof that the singularity probability of $A$ is exponentially small in $n$. This is joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe.

The Potts model on expander graphs

Series
Combinatorics Seminar
Time
Friday, October 28, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Corrine YapRutgers University

The Potts model is a distribution on q-colorings of a graph, used to represent spin configurations of a system of particles. Intuitively we expect most configurations to be "solid-like" at low temperatures and "gas-like" at high temperatures. We prove a precise version of this statement for d-regular expander graphs. We also consider the question of whether or not there are efficient algorithms for approximate counting and sampling from the model, and show that such algorithms exist at almost all temperatures. In this talk, I will introduce the different tools we use in our proofs, which come from both statistical physics (polymer models, cluster expansion) and combinatorics (a new container-like result, Karger's randomized min-cut algorithm). This is joint work with Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, and Aditya Potukuchi.

Friendly Bisections of Random Graphs

Series
Combinatorics Seminar
Time
Friday, October 21, 2022 - 16:00 for 1 hour (actually 50 minutes)
Location
Instructional Center 105
Speaker
Bhargav NarayananRutgers University

This talk is part of the Atlanta Combinatorics Colloquium. Note the time (4pm) and location (Instructional Center 105).

It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph $G(n,1/2)$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $n−o(n)$ vertices have more neighbours on their own side than across.

TBA by Ruth Luo

Series
Combinatorics Seminar
Time
Friday, October 14, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ruth LuoUniversity of South Carolina

Minimum degree conditions ensuring the existence of long cycles in hypergraphs

Series
Combinatorics Seminar
Time
Friday, October 14, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ruth LuoUniversity of South Carolina

Dirac proved that every $n$-vertex graph with minimum degree at least $n/2$ contains a hamiltonian cycle. Moreover, every graph with minimum degree $k \geq 2$ contains a cycle of length at least $k+1$, and this can be further improved if the graph is 2-connected. In this talk, we prove analogs of these theorems for hypergraphs. That is, we give sharp minimum degree conditions that imply the existence of long Berge cycles in uniform hypergraphs. This is joint work with Alexandr Kostochka and Grace McCourt.

Lawrence polytopes and some invariants of a graph

Series
Combinatorics Seminar
Time
Friday, September 30, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Changxin DingGeorgia Institute of Technology

This is an ongoing project. We make use of two dual Lawrence polytopes $P$ and $P*$ of a graph $G$, to study invariants of the graph. The $h$-vector of the graphic (resp. cographic) matroid complex associated to $G$ coincides with the $h^*$-vector of the Lawrence polytope $P$ (resp. $P^*$). In general, the $h$-vector is an invariant defined for an abstract simplicial complex, which encodes the number of faces of different dimensions. The $h^*$-vector, a.k.a. the $\delta$-polynomial, is an invariant defined for a rational polytope, which is obtained by dilating the polytope. By dissecting the Lawrence polytopes, we may study the $h$-vectors associated to the graph $G$ at a finer level. In particular, we understand activities and reduced divisors of the graph $G$ in a more geometric way. I will try to make the talk self-contained.

On a conjecture of Graham on the p-divisibility of central binomial coefficients

Series
Combinatorics Seminar
Time
Friday, September 16, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ernie CrootGeorgia Institute of Technology

I will discuss an old conjecture of Ron Graham on whether there are infinitely many integers $n$ so that $\mathrm{gcd}({{2n} \choose n}, 105)=1$, as well as recent progress on a version of this problem where 105 is replaced with a product of $r$ distinct primes. This is joint work with Hamed Mousavi and Maxie Schmidt.

The cluster expansion and combinatorics

Series
Combinatorics Seminar
Time
Friday, September 9, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Will PerkinsGeorgia Institute of Technology

The cluster expansion is a classical tool from statistical physics used to understand systems of weakly interacting particles in the high temperature regime of statistical physics models.  It can also be a very useful tool in probabilistic, extremal, and enumerative combinatorics and in the study of large deviations in probability theory.  I will give an introduction to the cluster expansion, present some examples of combinatorial applications, and try to provide some intuition about when the cluster expansion should or should not be a useful tool for a particular problem.

Pages