Seminars and Colloquia by Series

Constructions in combinatorics via neural networks

Series
Graph Theory Seminar
Time
Tuesday, November 30, 2021 - 12:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Adam Zsolt Wagner – Tel 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 McDonald – Auburn 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.

Irregular $\mathbf{d_n}$-Process is distinguishable from Uniform Random $\mathbf{d_n}$-graph

Series
Graph Theory Seminar
Time
Tuesday, November 16, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Erlang Surya – Georgia Institute of Technology –

For a graphic degree sequence $\mathbf{d_n}= (d_1 , . . . , d_n)$ of graphs with vertices $v_1 , . . . , v_n$, $\mathbf{d_n}$-process is the random graph process that inserts one edge at a time at random with the restriction that the degree of $v_i$ is at most $d_i$ . In 1999, N. Wormald asked whether the final graph of random $\mathbf{d_n}$-process is "similar" to the uniform random graph with degree sequence $\mathbf{d_n}$ when $\mathbf{d_n}=(d,\dots, d)$. We answer this question for the $\mathbf{d_n}$-process when the degree sequence $\mathbf{d_n}$ that is not close to being regular. We used the method of switching for stochastic processes; this allows us to track the edge statistics of the $\mathbf{d_n}$-process. Joint work with Mike Molloy and Lutz Warnke.

Counting paths, cycles, and other subgraphs in planar graphs

Series
Graph Theory Seminar
Time
Tuesday, November 9, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ryan Martin – Iowa State University –

For a planar graph $H$, let ${\bf N}_{\mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. The case where $H$ is the path on $3$ vertices, $H=P_3$, was established by Alon and Caro. The case of $H=P_4$ was determined, also exactly, by Gy\H{o}ri, Paulos, Salia, Tompkins, and Zamora. In this talk, we will give the asymptotic values for $H$ equal to $P_5$ and $P_7$ as well as the cycles $C_6$, $C_8$, $C_{10}$ and $C_{12}$ and discuss the general approach which can be used to compute the asymptotic value for many other graphs $H$. This is joint work with Debarun Ghosh, Ervin Győri, Addisu Paulos, Nika Salia, Chuanqi Xiao, and Oscar Zamora and also joint work with Chris Cox.

Line transversals in families of connected sets in the plane

Series
Graph Theory Seminar
Time
Tuesday, November 2, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Shira Zerbib – Iowa State University –

We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff from 1993, who proved that under the same condition there are four lines intersecting all the sets. We also prove a colorful version of this result under weakened conditions on the sets, improving results of Holmsen from 2013. Our proofs use the topological KKM theorem. Joint with Daniel McGinnis.

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 Ding – Brandeis University –

Please Note: Zoom link: https://us04web.zoom.us/j/77238664391 Password: graphs!

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 Cao – Georgia 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 Yuan – Georgia 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.

Counting comparisons in the Erdős–Szekeres theorem

Series
Graph Theory Seminar
Time
Tuesday, September 28, 2021 - 15:45 for
Location
Skiles 005
Speaker
Misha Lavrov – Kennesaw State University –

This talk is motivated by the Erdős–Szekeres theorem on monotone subsequences: given a sequence of $rs+1$ distinct numbers, there is either a subsequence of $r+1$ of them in increasing order, or a subsequence of $s+1$ of them in decreasing order.

We'll consider many related questions with an algorithmic flavor, such as: if we want to find one of the subsequences promised, how many comparisons do we need to make? What if we have to pre-register our comparisons ahead of time? Does it help if we search a longer sequence instead?

Some of these questions are still open; some of them have answers. The results I will discuss are joint work with Jozsef Balogh, Felix Clemen, and Emily Heath at UIUC.

The feasible region of induced graphs

Series
Graph Theory Seminar
Time
Tuesday, September 21, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xizhi Liu – University of Illinois at Chicago –

Fix a graph $F$. A classical problem in extremal graph theory asks about how many induced copies of $F$ can a graph with edge density $\rho$ have? The only case in which we know the asymptotic solution is when $F$ is a complete graph, and it was solved completely only recently by Reiher using the flag algebra machinery. We will consider the other cases and show some results when $F$ is a complete bipartite graph or a complete graph minus one edge. Many interesting related open problems will also be introduced. Joint work with Dhruv Mubayi and Christian Reiher.

Pages