Seminars and Colloquia by Series

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 MartinIowa 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 ZerbibIowa 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 DingBrandeis 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 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.

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 LavrovKennesaw 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 LiuUniversity 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.

Induced subgraphs and treewidth

Series
Graph Theory Seminar
Time
Tuesday, September 14, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Sophie SpirklUniversity of Waterloo

Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area. Joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Kristina Vuskovic.

Polynomial $\chi$-binding functions for $t$-broom-free graphs

Series
Graph Theory Seminar
Time
Tuesday, September 7, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Joshua SchroederGeorgia Institute of Technology

For any positive integer $t$, a $t$-broom is a graph obtained from $K_{1,t+1}$ by subdividing an edge once.  In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $\chi(G) =  o(\omega(G)^{t+1})$, where  $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of  Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $\chi(G)$ to $7.5\omega(G)^2$, confirming a conjecture of Sivaraman. For $t\geq 3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(\omega^{t-1+\frac{2}{t+1}})$. Joint work with Xiaonan Liu, Zhiyu Wang, and Xingxing Yu.

Long cycles in essentially 4-connected projective-planar graphs

Series
Graph Theory Seminar
Time
Tuesday, August 31, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael WigalGeorgia Institute of Technology

Tutte paths have a critical role in the study of Hamiltonicity for 4-connected planar and other graph classes. We show quantitative Tutte path results in which we bound the number of bridges of the path. A corollary of this result is near optimal circumference bounds for essentially 4-connected planar and projective-planar graphs. Joint work with Xingxing Yu.

Pages