### TBA by Mohammad Ghomi

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

TBA

- You are here:
- Home
- News & Events

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

TBA

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

TBA

- Series
- Combinatorics Seminar
- Time
- Friday, March 17, 2023 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 249
- Speaker
- Youngho Yoo – Texas A&M – yyoo@tamu.edu

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.

- Series
- Combinatorics Seminar
- Time
- Thursday, March 16, 2023 - 15:00 for 1 hour (actually 50 minutes)
- Location
- G08 ESM (ground floor)
- Speaker
- Jie Han – Beijing 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.

- Series
- Combinatorics Seminar
- Time
- Wednesday, March 8, 2023 - 16:00 for 1 hour (actually 50 minutes)
- Location
- C457 Classroom Van Leer
- Speaker
- Michail Sarantis – Carnegie 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.

- Series
- Combinatorics Seminar
- Time
- Friday, December 2, 2022 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Ashwin Sah – Massachusetts Institute of Technology – asah@mit.edu

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)

- Series
- Combinatorics Seminar
- Time
- Friday, November 18, 2022 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Wesley Pegden – Carnegie 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.

- Series
- Combinatorics Seminar
- Time
- Friday, November 4, 2022 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Matthew Jenssen – University 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.

- Series
- Combinatorics Seminar
- Time
- Friday, October 28, 2022 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Corrine Yap – Rutgers 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.

- Series
- Combinatorics Seminar
- Time
- Friday, October 21, 2022 - 16:00 for 1 hour (actually 50 minutes)
- Location
- Instructional Center 105
- Speaker
- Bhargav Narayanan – Rutgers 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.