## Seminars and Colloquia by Series

Series
Combinatorics Seminar
Time
Friday, April 21, 2023 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker

TBA

### TBA by Zachary Hamaker

Series
Combinatorics Seminar
Time
Friday, March 31, 2023 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker
Zachary HamakerUniversity of Florida

TBA

### Path odd-covers of graphs

Series
Combinatorics Seminar
Time
Friday, March 17, 2023 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker
Youngho YooTexas A&amp;M

We study the minimum number of paths needed to express the edge set of a given graph as the symmetric difference of the edge sets of the paths. This can be seen as a weakening of Gallai’s path decomposition problem, and a variant of the “odd cover” problem of Babai and Frankl which asks for the minimum number of complete bipartite graphs whose symmetric difference gives the complete graph. We relate this “path odd-cover” number of a graph to other known graph parameters and prove some bounds. Joint work with Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, and Puck Rombach.

### Factors in graphs with randomness

Series
Combinatorics Seminar
Time
Thursday, March 16, 2023 - 15:00 for 1 hour (actually 50 minutes)
Location
G08 ESM (ground floor)
Speaker
Jie HanBeijing Institute of Technology

The celebrated Hajnal-Szemerédi theorem gives best possible minimum degree conditions for clique-factors in graphs. There have been some recent variants of this result into several settings, each of which has some sort of randomness come into play. We will give a survey on these problems and the recent developments.

### On the zeroes of hypergraph independence polynomials

Series
Combinatorics Seminar
Time
Wednesday, March 8, 2023 - 16:00 for 1 hour (actually 50 minutes)
Location
C457 Classroom Van Leer
Speaker
Michail SarantisCarnegie Mellon University

We study the locations of complex zeroes of independence polynomials of bounded degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer's result on the optimal zero-free disk, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disk almost as large as the optimal disk for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim1/(e\Delta)$). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge-sizes strictly greater than $2$. We conjecture that for $k\geq 3$, there exist families of $k$-uniform linear hypergraphs that have a much larger zero-free disk of radius $\Omega(\Delta^{-1/(k-1)})$. We establish this in the case of linear hypertrees. Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali.

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