Seminars and Colloquia by Series

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.

Tangles and approximate packing-covering duality

Series
Graph Theory Working Seminar
Time
Thursday, October 10, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Tech

 Tangles capture a notion of high-connectivity in graphs which differs from $k$-connectivity. Instead of requiring that a small vertex set $X$ does not disconnect the graph $G$, a tangle “points” to the connected component of $G-X$ that contains most of the “highly connected part”. Developed initially by Robertson and Seymour in the graph minors project, tangles have proven to be a fundamental tool in studying the general structure of graphs and matroids. Tangles are also useful in proving that certain families of graphs satisfy an approximate packing-covering duality, also known as the Erd\H{o}s-P\'osa property. In this talk I will give a gentle introduction to tangles and describe some basic applications related to the Erd\H{o}s-P\'osa property.

 

The Combinatorial Nullstellensatz and its applications

Series
Graph Theory Working Seminar
Time
Thursday, September 5, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Tech

Please Note:

In 1999, Alon proved the “Combinatorial Nullstellensatz” which resembles Hilbert’s Nullstellensatz and gives combinatorial structure on the roots of a multivariate polynomial. This method has numerous applications, most notably in additive number theory, but also in many other areas of combinatorics. We will prove the Combinatorial Nullstellensatz and give some of its applications in graph theory.

 

Caterpillars in Erods-Hajnal

Series
Graph Theory Working Seminar
Time
Wednesday, April 17, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michail SarantisGeorgia Tech

The well known Erdos-Hajnal Conjecture states that every graph has the Erdos-Hajnal (EH) property. That is, for every $H$, there exists a $c=c(H)>0$ such that every graph $G$ with no induced copy of $H$ has the property $hom(G):=max\{\alpha(G),\omega(G)\}\geq |V(G)|^{c}$. Let $H,J$ be subdivisions of caterpillar graphs. Liebenau, Pilipczuk, Seymour and Spirkl proved that the EH property holds if we forbid both $H$ and $\overline{J}.$ We will discuss the proof of this result.

Strong edge colorings and edge cuts

Series
Graph Theory Working Seminar
Time
Wednesday, March 13, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
James AndersonGeorgia Tech
Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most 5/4 Δ^2 colors. The conjecture is still open for Δ=4. We show the conjecture is true when an edge cut of size 1 or 2 exists, and in certain cases when an edge cut of size 4 or 3 exists.

Packing and covering triangles

Series
Graph Theory Working Seminar
Time
Wednesday, March 6, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Youngho YooGeorgia Tech

Let $\nu$ denote the maximum size of a packing of edge-disjoint triangles in a graph $G$. We can clearly make $G$ triangle-free by deleting $3\nu$ edges. Tuza conjectured in 1981 that $2\nu$ edges suffice, and proved it for planar graphs. The best known general bound is $(3-\frac{3}{23})\nu$ proven by Haxell in 1997. We will discuss this proof and some related results.

On Bounding the Number of Automorphisms of a Tournament

Series
Graph Theory Working Seminar
Time
Wednesday, February 20, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michael WigalGeorgia Tech
Let $g(n) = \max_{|T| = n}|\text{Aut}(T)|$ where $T$ is a tournament. Goldberg and Moon conjectured that $g(n) \le \sqrt{3}^{n-1}$ for all $n \ge 1$ with equality holding if and only if $n$ is a power of 3. Dixon proved the conjecture using the Feit-Thompson theorem. Alspach later gave a purely combinatorial proof. We discuss Alspach's proof and and some of its applications.

On Bounding the Number of Automorphisms of a Tournament

Series
Graph Theory Working Seminar
Time
Tuesday, February 19, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michael WigalGeorgia Tech
Let $g(n) = \max_{|T| = n}|\text{Aut}(T)|$ where $T$ is a tournament. Goldberg and Moon conjectured that $g(n) \le \sqrt{3}^{n-1}$ for all $n \ge 1$ with equality holding if and only if $n$ is a power of 3. Dixon proved the conjecture using the Feit-Thompson theorem. Alspach later gave a purely combinatorial proof. We discuss Alspach's proof and and some of its applications.

Pages