Events

Late points for random walks and the fluctuations of cover times

Abstract:

How long does it take for a random walk to visit all vertices of a finite graph G? What is the distribution of this so-called cover time? And what do the last k vertices to be covered look like?

Path Graphs, PR-trees, and Split Decomposition

Abstract:

Path graphs are the intersection graphs of paths in trees. In this talk we introduce a new data structure, the PR-tree, to characterize the sets of path-tree models of path graphs.

Resource buying games

Abstract:

Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

Abstract:

We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b on nodes.

Tutte's proof of Kuratowski's Theorem

Abstract:

Tutte's theory of peripheral cycles can be used to give a proof of Kuratowski's Planarity Theorem for 3-connected graphs. This expository talk is aimed at giving the main steps of this argument.

On Tutte's 3-flow conjecture

Abstract:

An important element of Tutte's research legacy is his trio of k-flow conjectures. These assert that the famous results on k-coulouring planar maps (for k=3,4,5) hold true, in k-flow translation, for graphs that are nonplanar.

All the King's Horses

Abstract:

A vertex-deleted subgraph of G is a graph we get from G by deleting a single vertex.

A notion of inverse Chvátal rank

Abstract:

The Chvátal rank of a polyhedron Q is the number of times one has to iterate the derivation of the so-called Chvátal closure in order to obtain the integer hull of Q, i.e., the polyhedron P defined as the convex hull of the integer points in Q.

How to draw a graph

Abstract:

Tutte proved that every 3-connected planar graph admits a convex embedding; that is, an embedding in which each face is bounded by a convex polygon. The result itself is attractive, but the method used is truly stunning.

Exact solutions to linear and integer programming problems

Abstract:

The software systems commonly used to solve linear and integer programming problems today make use of floating-point computation and the inexactness of these computations can lead to errors in the returned results.