Seminars and Colloquia by Series

Evasiveness conjecture and topological methods in graph theory III

Series
Graph Theory Working Seminar
Time
Tuesday, March 8, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ruilin ShiGeorgia Institute of Technology

In the third talk of this seminar series, we continue to follow the manuscript of Carl Miller. We will begin with a quick review of chain complexes and simplicial isomorphisms and then we will detour to discuss the geometric interpretation of homology groups in lower dimensions. This work can help us understand the structure of simplicial complexes with boundary maps and their homology groups. Then we go back to abstract homological algebra which is the study of homology groups without reference to simplicial complexes. We will introduce the Snake Lemma without proof. Finally, we will apply this lemma to prove the goal of this chapter: collapsibility for a simplicial complex implies its homology groups are trivial which is called acyclicity.

Evasiveness conjecture and topological methods in graph theory II

Series
Graph Theory Working Seminar
Time
Tuesday, March 1, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jing YuGeorgia Institute of Technology

In the second talk of this seminar series, we continue to follow the manuscript of Carl Miller and building up concepts from algebraic topology. In particular, we will introduce chain complexes to define homology groups and provide some of the standard theory for them.

Evasiveness conjecture and topological methods in graph theory I

Series
Graph Theory Working Seminar
Time
Tuesday, February 8, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James AndersonGeorgia Institute of Technology

In the first talk of this seminar series, we follow the manuscript of Carl Miller and introduce the concept of elusive graph properties—those properties for which any edge-querying algorithm requires all possible queries in the worst case. Karp conjectured in 1973 that all nontrivial monotonic graph properties are elusive, and a celebrated theorem by Kahn in 1984 used topological fixed-point methods to show the conjecture is true in the case of graphs with order equal to a prime power. To set the stage for the proof of this result in later talks, we introduce monotone graph properties and their connection to collapsible simplicial complexes.

Working Seminar Organizational Meeting

Series
Graph Theory Working Seminar
Time
Tuesday, February 1, 2022 - 15:45 for 30 minutes
Location
Skiles 005
Speaker

The goal of the meeting is to decide what paper(s) we will be reading and make a rough plan going forward. The following two possibilities were suggested:

• Topological methods in graph theory and their application to the evasiveness conjecture using these lecture notes by Carl Miller.
• Furstenberg's proof of Szemeredi's theorem via ergodic theory using Yufei Zhao's lecture notes.

Other suggestions are also welcome!

Number of Hamiltonian cycles in planar triangulations

Series
Graph Theory Working Seminar
Time
Tuesday, September 29, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Xiaonan LiuGeorgia Institute of Technology

Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices, then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/\log_2 n)$ separating 4-cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G) \ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a "double wheel" structure, providing further evidence to the above conjecture.

Packing A-paths and cycles in undirected group-labelled graphs

Series
Graph Theory Working Seminar
Time
Tuesday, September 22, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Youngho YooGeorgia Institute of Technology

An $A$-path is a path whose intersection with a vertex set $A$ is exactly its endpoints. We show that, for all primes $p$, the family of $A$-paths of length $0 \,\mathrm{mod}\, p$ satisfies an approximate packing-covering duality known as the Erdős-Pósa property. This answers a recent question of Bruhn and Ulmer. We also show that, if $m$ is an odd prime power, then for all integers $L$, the family of cycles of length $L \,\mathrm{mod}\, m$ satisfies the Erdős-Pósa property. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs $L$ and $m$. Both results are consequences of a structure theorem which refines the Flat Wall Theorem of Robertson and Seymour to undirected group-labelled graphs analogously to a result of Huynh, Joos, and Wollan in the directed setting. Joint work with Robin Thomas.

Chromatic number of graphs with no indeuced 3-matching

Series
Graph Theory Working Seminar
Time
Thursday, March 5, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Joshua SchroederGeorgia Tech
In 1980, Wagon showed that $\chi(G) \leq f_m(n)$ for any $\{mK_2, K_n\}$-free graph $G$, where $f_m$ is a polynomial and $mK_2$ is an induced matching of size $m$. However this bound is not known to be sharp. Recently, Gaspers and Huang helped sharpen this bound by showing for any $\{2K_2, K_4\}$-free graph $G$, that $\chi(G) \leq 4$. This resolves the question raised by Wagon for $m=2$, $n=4$. For the case where $m = 3$, it was shown by Brandt in 2002 that $(K_3, 3K_2)$-free graphs are 4-colorable.  In this talk, I will provide the outline for an alternate proof of this fact, as a byproduct of my research project.

Maximum Weight Internal Spanning Tree Problem

Series
Graph Theory Working Seminar
Time
Thursday, February 20, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Arti Pandey Indian Institute of Technology Ropar

Given a vertex-weighted graph G= (V, E), the MaximumWeight Internal Spanning Tree (MWIST) problem is to find a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted version of this problem, known as Maxi-mum Internal Spanning Tree (MIST) problem, is a generalization of the Hamiltonian path problem, and hence, it is NP-hard. In the literature lot of research has been done on designing approximation algorithms to achieve an approximation ratio close to 1. The best known approximation algorithm achieves an approximation ratio of 17/13 for the MIST problem for general graphs. For the MWIST problem, the current best approximation algorithm achieves an approximation ratio of 2 for general graphs. Researchers have also tried to design exact/approximation algorithms for some special classes of graphs. The MIST problem parameterized by the number of internal vertices k, and its special cases and variants, have also been extensively studied in the literature. The best known kernel for the general problem has size 2k, which leads to the fastest known exact algorithm with running time O(4^kn^{O(1)}). In this talk, we will talk about some selected recent results on the MWIST problem.

Introduction to algebraic graph theory

Series
Graph Theory Working Seminar
Time
Wednesday, February 12, 2020 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James AndersonGeorgia Tech
In this introductory talk, we explore the first 5 chapters of Biggs's Algebraic Graph Theory. We discuss the properties of the adjacency matrix  of graph G, as well as the relationship between the incidence matrix of G and the cycle space and cut space. We also include several other small results. This talk will be followed by later talks in the semester continuing from Biggs's book.

Large cycles in essentially 4-connected planar graphs

Series
Graph Theory Working Seminar
Time
Thursday, January 30, 2020 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michael WigalGeorgia Tech

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but
there are 3-connected $n$-vertex graphs whose longest cycles have length
$\Theta(n^{\log_32})$. On the other hand,  Jackson and Wormald proved that an
essentially 4-connected $n$-vertex planar graph contains a cycle of
length at least $(2n+4)/5$, which was improved to $5(n+2)/8$ by Fabrici {\it et al}.  We improve this bound to $\lceil (2n+6)/3\rceil$ for $n\ge 6$ by proving a quantitative version of a result of Thomassen,
and the bound is best possible.