Seminars and Colloquia by Series

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 Yoo – Georgia 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 Yoo – Georgia 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 Sarantis – Georgia 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 Anderson – Georgia 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 Yoo – Georgia 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 Wigal – Georgia 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 Wigal – Georgia 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.

Strong edge coloring of subcubic planar graphs

Series
Graph Theory Working Seminar
Time
Wednesday, February 6, 2019 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Joshua Schroeder – Georgia Tech

Strong edge coloring of a graph $G$ is a coloring of the edges of the graph such that each color class is an induced subgraph. The strong chromatic index of $G$ is the smallest number $k$ such that $G$ has a $k$-strong edge coloring. Erdős and Nešetřil conjecture that the strong chromatic index of a graph of max degree $\Delta$ is at most $5\Delta^2/4$ if $\Delta$ is even and $(5\Delta^2-2\Delta + 1)/4$ if $\Delta$ is odd. It is known for $\Delta=3$ that the conjecture holds, and in this talk I will present part of Anderson's proof that the strong chromatic index of a subcubic planar graph is at most $10$

Exposition on the entropy method and the occupancy method

Series
Graph Theory Working Seminar
Time
Wednesday, November 28, 2018 - 16:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Prasad Tetali – Georgia Tech
Continuing on the theme mentioned in my recent research horizons lecture, I will illustrate two techniques by deriving upper and lower bounds on the number of independent sets in bipartite and triangle-free graphs.

Finding small simple cycle separators for 2-connected planar graphs

Series
Graph Theory Working Seminar
Time
Wednesday, November 14, 2018 - 16:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 006
Speaker
Michael Wigal – Georgia Tech
Continuation of last week's talk. For a graph on n vertices, a vertex partition A,B,C is a f(n)-vertex separator if |C|≤f(n) and |A|,|B|≤2n/3 and (A,B)=∅. A theorem from Gary Miller states for an embedded 2-connected planar graph with maximum face size d there exists a simple cycle such that it is vertex separator of size at most 2√dn. This has applications in divide and conquer algorithms.

Pages