Seminar

Title: List Colouring and Ohba's Conjecture

Abstract:

The question of when the list-chromatic number of a graph G, denoted chi_l(G), equals its chromatic number is fundamental to the theory of list colouring.

Title: The Aggregation Closure is Polyhedral for Packing and Covering Integer Programs

Abstract:

Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta introduced the concept of aggregation cuts for packing and covering integer programs.

Title: An Introduction to the Circuits of Polyhedra, The Circuit Diameter, and Their Applications

Abstract:

The combinatorial diameter of a polyhedron P is the maximum value of a shortest path between two vertices of P, where the path moves along edges of P. Its study is motivated largely by its implications on the running time of the Simplex algorithm.

Title: Minimum degree conditions for Hamilton cycles in hypergrahs

Abstract:

A classic result of Dirac states that a graph in which every vertex is connected to at least half of the other vertices contains a Hamilton cycle. How can we generalize Dirac's theorem to hypergraphs?

Title: Random Pattern-Avoiding Permutations

Abstract:

A "pattern of length k" is simply a permutation of {1,..,k}.  This pattern is said to be contained in a permutation of {1,...,N} (for N>k) if there is a subsequence of k elements of the (long) permutation that appears in the same relative order as the pattern.

Title: Excluding a ladder

Abstract:

A folklore result says that if a graph does not contain the path of length k as a subgraph, then it has tree-depth at most k.

Title: Network Design $s$-$t$ Effective Resistance

Abstract:

We consider a problem of designing a network with small $s$-$t$ effective resistance. In the problem, we are given an undirected graph $G=(V,E)$, two designated vertices $s,t \in V$, and a budget $k$.

Title: Some places matroids appear in quantum field theory and some places I would like them to

Abstract:

I will discuss some places matroids have appeared in my work in quantum field theory, including some older work on numerator structure with Dirk Kreimer and some work in progress with Iain Crump on period identities.

Title: Uniformly generate graphs with given degrees rapidly

Abstract:

I will survey the research on exact/approximate uniform generation of graphs with prescribed degrees.

Title: On the Strong Nine Dragon Tree Conjecture

Abstract:

Nash-Williams forest covering theorem says that a graph decomposes into $k$ forests if and only if it has fractional arboricity at most $k$. In 2012 Mickeal Montassier, Patrice Ossona de Mendez, Andre Raspaud, and Xuding Zhu  proposed a significant strengthening of Nash-Williams Theorem, called the Strong Nine Dragon Tree Conjecture.