- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

We discuss open research questions surrounding the traveling salesman problem.
A focus will be on topics having potential impact on the computational
solution of large-scale problem instances.

Series: Graph Theory Seminar

Tree-width is a well-known metric on undirected graphs that measures how tree-like a
graph is and gives a notion of graph decomposition that proves useful in
fixed-parameter tractable (FPT) algorithm development. In the directed setting, many
similar notions have been proposed - none of which has been accepted widely as a
natural generalization of tree-width. Among the many suggested equivalent parameters
were the "directed tree-width" by Johnson et al, and DAG-width by Berwanger et al and
Odbrzalek.
In this talk, I will present a recent paper by Hunter and Kreutzer, that defines
another such directed width parameter, celled "kelly-width". I will discuss the
equivalent complexity measures for graphs such as elimination orderings, k-trees and
cops and robber games and study their natural generalizations to digraphs. I will
discuss its usefulness by discussing potential applications including polynomial-time
algorithms for NP-complete problems on graphs of bounded Kelly-width (FPT). I will
also briefly discuss our work in progress (joint with Shiva Kintali) towards
designing an approximation algorithm for Kelly Width.

Series: Graph Theory Seminar

Rota asked in the 1960's how one might construct an axiom system for
infinite matroids. Among the many suggested answers
were the B-matroids of Higgs. In 1978, Oxley proved that any infinite
matroid system with the notions of duality and minors must be equivalent to
B-matroids. He also provided a simpler mixed basis-independence axiom system
for B-matroids, as opposed to the complicated closure system developed by
Higgs. In this talk, we examine a recent paper of Bruhn et al that gives
independence, basis, circuit, rank, and closure axiom systems for
B-matroids. We will also discuss some open problems for infinite matroids.

Series: Graph Theory Seminar

A graph is k-choosable if it can be properly colored from any assignment of lists of colors of length at least k to its vertices. A well-known results of Thomassen state that every planar graph is 5-choosable and every planar graph of girth 5 is 3-choosable. These results are tight, as shown by constructions of Voigt. We review some new results in this area, concerning 3-choosability of planar graphs with constraints on triangles and 4-cycles.

Series: Graph Theory Seminar

We present some geometric properties of the Laplacian lattice and the lattice of integer flows of a given graph and discuss some applications and open problems.

Series: Graph Theory Seminar

A deep theorem of Thomassen shows that for any surface there are only finitely many 6-critical graphs that embed on that surface. We give a shorter self-contained proof that for any 6-critical graph G that embeds on a surface of genus g, that |V(G)| is at most linear in g. Joint work with Robin Thomas.

Series: Graph Theory Seminar

The theory of graph minors developed by Robertson and Seymour is
perhaps one of the deepest developments in graph theory. The theory is
developed in a sequence of 23 papers, appearing from the 80's through
today. The major algorithmic application of the work is a polynomial
time algorithm for the k disjoint paths problem when k is fixed. The
algorithm is relatively simple to state - however the proof uses the
full power of the Robertson Seymour theory, and consequently runs
approximately 400-500 pages. We will discuss a new proof of
correctness that dramatically simplifies this result, eliminating many
of the technicalities of the original proof.
This is joint work with Ken-ichi Kawarabayashi.

Series: Graph Theory Seminar

We consider a the minimum k-way cut problem for unweighted graphs
with a bound $s$ on the number of cut edges allowed. Thus we seek to remove as
few
edges as possible so as to split a graph into k components, or
report that this requires cutting more than s edges. We show that this
problem is fixed-parameter tractable (FPT) in s.
More precisely, for s=O(1), our algorithm runs in quadratic time
while we have a different linear time algorithm
for planar graphs and bounded genus graphs.
Our result solves some open problems and contrasts W[1] hardness (no
FPT unless P=NP) of related formulations of the k-way cut
problem. Without the size bound, Downey et al.~[2003] proved that
the minimum k-way cut problem is W[1] hard in k even for simple
unweighted graphs.
A simple reduction shows that vertex cuts are at least as hard as edge cuts,
so the minimum k-way vertex cut is also W[1] hard in terms of
k. Marx [2004] proved that finding a minimum
k-way vertex cut of size s is also W[1] hard in s. Marx asked about
FPT status with edge cuts, which is what we resolve here.
We also survey approximation results for the minimum k-way cut problem, and
conclude
some open problems. Joint work with Mikkel Thorup (AT&T Research).

Series: Graph Theory Seminar

Please note the location: Last minute room change to Skiles 270.

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. It is known that every such inequality follows from the positive semi-definiteness of a certain infinite matrix. As an immediate consequence every algebraic inequality between the homomorphism densities follows from an infinite number of certain applications of the Cauchy-Schwarz inequality. Lovasz and, in a slightly different formulation, Razborov asked whether it is true or not that every algebraic inequality between the homomorphism densities follows from a _finite_ number of applications of the Cauchy-Schwarz inequality. In this talk, we show that the answer to this question is negative by exhibiting explicit valid inequalities that do not follow from such proofs. Further, we show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Joint work with Hamed Hatami.

Series: Graph Theory Seminar

In 1997 Kannan and Frieze defined the \emph{cut-norm} $\left\Vert A\right\Vert_{\square}$ of a $p\times q$ matrix $A=\left[ a_{ij}\right] $ as%\[\left\Vert A\right\Vert _{\square}=\frac{1}{pq}\max\left\{ \left\vert\sum_{i\in X}\sum_{j\in Y}a_{ij}\right\vert :X\subset\left[ p\right],Y\subset\left[ q\right] ,\text{ }X,Y\neq\varnothing\right\} .\]More recently, Lov\'{a}sz and his collaborators used the norm $\left\VertA\right\Vert _{\square}$ to define a useful measure of similarity between anytwo graphs, which they called \emph{cut-distance. }It turns out that the cut-distance can be extended to arbitrary complexmatrices, even non-square ones. This talk will introduce the basics of thecut-norm and \ cut-distance for arbitrary matrices, and present relationsbetween these functions and some fundamental matricial norms, like theoperator norm. In particular, these relations give a solution to a problem of Lov\'{a}sz.Similar questions are discussed about the related norm\[\left\Vert A\right\Vert _{\boxdot}=\max\left\{ \frac{1}{\sqrt{\left\vertX\right\vert \left\vert Y\right\vert }}\left\vert \sum_{i\in X}\sum_{j\inY}a_{ij}\right\vert :X\subset\left[ p\right] ,Y\subset\left[ q\right],\text{ }X,Y\neq\varnothing\right\} .\]which plays a central role in the \textquotedblleft expander mixinglemma\textquotedblright.