Seminars and Colloquia by Series

Constructions in combinatorics via neural networks

Series
Graph Theory Seminar
Time
Tuesday, November 30, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Adam Zsolt WagnerTel Aviv University

Please Note: Note the unusual time!

Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go, purely through self-play. In this talk I will give a basic introduction to neural networks and reinforcement learning algorithms. I will also indicate how these methods can be adapted to the "game" of trying to find a counterexample to a mathematical conjecture, and show some examples where this approach was successful.

Strong 4-colourings of graphs

Series
Graph Theory Seminar
Time
Tuesday, November 23, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Jessica McDonaldAuburn University

In this talk we’ll discuss strong 4-colourings of graphs and prove two new cases of the Strong Colouring Conjecture. Let H be a graph with maximum degree at most 2, and let G be obtained from H by gluing in vertex-disjoint copies of K_4. We’ll show that if H contains at most one odd cycle of length exceeding 3, or if H contains at most 3 triangles, then G is 4-colourable. This is joint work with Greg Puleo.

Geometric bijections between subgraphs and orientations of a graph

Series
Graph Theory Seminar
Time
Tuesday, October 26, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Zoom
Speaker
Changxin DingBrandeis University

Let $G$ be a connected finite graph. Backman, Baker, and Yuen have constructed a family of explicit and easy-to-describe bijections $g_{\sigma,\sigma^*}$ between spanning trees of $G$ and $(\sigma,\sigma^*)$-compatible orientations, where the $(\sigma,\sigma^*)$-compatible orientations are the representatives of equivalence classes of orientations up to cycle-cocycle reversal which are determined by a cycle signature $\sigma$ and a cocycle signature $\sigma^*$. Their proof makes use of zonotopal subdivisions and the bijections $g_{\sigma,\sigma^*}$ are called geometric bijections. Recently we have extended the geometric bijections to  subgraph-orientation correspondences. In this talk, I will introduce the bijections and the geometry behind them.

Counting colorings of triangle-free graphs

Series
Graph Theory Seminar
Time
Tuesday, October 19, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ruijia CaoGeorgia Institute of Technology

Please Note: Note the unusual time!

In this talk, we will discuss the main results of our paper, Counting Colorings of Triangle-Free Graphs, in which we prove the Johansson-Molloy theorem for the upper bound on the chromatic number of a triangle free graph using a novel counting approach developed by Matthieu Rosenfeld, and also extend this result to obtain a lower bound on the number of proper q-colorings for a triangle free graph.  The talk will go over the history of the problem, an outline of our approach, and a high-level sketch of the main proofs. This is joint work with Anton Bernshteyn, Tyler Brazelton, and Akum Kang.

Turán numbers of some complete degenerate hypergraphs

Series
Graph Theory Seminar
Time
Tuesday, October 5, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiaofan YuanGeorgia Institute of Technology

Please Note: Note the unusual time!

Let $K^{(r)}_{s_1,s_2,\cdots,s_r}$ be the complete $r$-partite $r$-uniform hypergraph and $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})$ be the maximum number of edges in any $n$-vertex $K^{(r)}_{s_1,s_2,\cdots,s_r}$-free $r$-uniform hypergraph. It is well-known in the graph case that $ex(n,K_{s,t})=\Theta(n^{2-1/s})$ when $t$ is sufficiently larger than $s$. We generalize the above to hypergraphs by showing that if $s_r$ is sufficiently larger than $s_1,s_2,\cdots,s_{r-1}$ then $$ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})=\Theta\left(n^{r-\frac{1}{s_1s_2\cdots s_{r-1}}}\right).$$ This is joint work with Jie Ma and Mingwei Zhang.

Pages