Seminars and Colloquia by Series

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.

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.

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

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.

Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems

Series
Combinatorics Seminar
Time
Tuesday, July 26, 2022 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Esther EzraBar Ilan University

Let T be a set of n triangles in 3-space, and let \Gamma be a family of
algebraic arcs of constant complexity in 3-space. We show how to preprocess T
into a data structure that supports various "intersection queries" for
query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any
triangle of T, reporting all such triangles, counting the number of
intersection points between \gamma and the triangles of T, or returning the
first triangle intersected by a directed arc \gamma, if any (i.e., answering
arc-shooting queries). Our technique is based on polynomial partitioning and
other tools from real algebraic geometry, among which is the cylindrical
algebraic decomposition.

Our approach can be extended to many other intersection-searching problems in
three and higher dimensions. We exemplify this versatility by giving an
efficient data structure for answering segment-intersection queries amid a set
of spherical caps in 3-space, and we lay a roadmap for extending our approach
to other intersection-searching problems.

Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.

Two conjectures on the spread of graphs

Series
Combinatorics Seminar
Time
Friday, April 29, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael TaitVillanova University

Given a graph $G$ let $\lambda_1$ and $\lambda_n$ be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of $G$ to be $\lambda_1 - \lambda_n$. In this talk we discuss solutions to a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.
   
The first, referred to as the spread conjecture, states that over all graphs on $n$ vertices the join of a clique of order $\lfloor 2n/3 \rfloor$ and an independent set of order $\lceil n/3 \rceil$ is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed $e\leq n^2/4$, if $G$ has maximum spread over all $n$-vertex graphs with $e$ edges, then $G$ must be bipartite.

We show that the spread conjecture is true for all sufficiently large $n$, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.

Pages