Workshop on Topological Methods in Combinatorics, Computational Geometry, and the Study of Algorithms

Monday, October 2

10:30 am: Alex Suciu (Northeastern University): Fundamental group computations in the theory of arrangements and related spaces
From the very beginning, the theory of hyperplane arrangements has been intimately connected to that of Artin braid groups and configuration spaces. The rich interplay between the combinatorics and the topology of a hyperplane arrangement is reflected in the fundamental group and the cohomology ring of the complement. Useful information about these objects can be extracted from the jumping loci for cohomology with coefficients in rank one local systems. I will discuss how to compute these varieties, for arrangements and for related spaces. Finally, I will show how they can be used to answer questions about the geometric realizability and homological finiteness properties of various classes of groups.

2:00 pm: Dmitry Feichtner-Kozlov (ETH Zurich/University of Bremen): Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
Abstract: Combinatorics, in particular graph theory, has a rich history of being a domain of successful applications of tools from other areas of mathematics, including topological methods. In this talk I will survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs.

The structural theory will be developed and put in the historical context, encompassing in particular the Lovasz Conjecture, which can be stated as follows:

For a graph $G$, such that the complex $Hom(C_{2r+1},G)$ is $k$-connected for some integers $r$ and $k$, $r>0$, $k>-2$, we know that the chromatic number of $G$ is at least $k+4$.

Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. The latter are used to state the more general Babson-Kozlov conjecture which says:

For any graph $G$, we have $\chi(G)\geq h(Hom(C_{2r+1},G))+3$.

Here, for a ${\mathbb Z}_2$-space $X$, $h(X)$ denotes the maximal exponent of the non-zero power of the Stiefel-Whitney characteristic class of the associated line bundle.

I shall give an extremely short combinatorial proof of the Babson-Kozlov conjecture. Furthermore, I shall describe how to use the spectral sequences to perform a complete calculation of the cohomology groups of the colorings of cycles. If time permits, I will also say a few words about homological tests for graph colorings based on our theoretical results.

(part of the talk is based on joint work with Eric Babson and with Sonja Cukic)

3:30 pm: Contributed 30 minute talks
-Raghavan Dhandapani: Greedy drawings of planar triangulations
Abstract: A path v_1,v_2,...,v_m in a planar drawing of a graph G(V,E) is said to be "distance decreasing" if d(v_i,v_m) < d(v_{i-1},v_m).

The drawing is said to be "greedy" if a distance decreasing path exists for every pair of distinct vertices (s,t) in V\times V.

It was conjectured by Papadimitriou and Ratajczak that a greedy drawing exists for every 3-connected planar graph. We settle this conjecture in the affirmative for the case of triangulations.

A partitioning of the edges of a triangulation G into 3 trees, called the "realizer" of G, was first developed by Walter Schnyder who also gave a drawing algorithm based on this.

We generalize Schnyder's algorithm to obtain a whole class of drawings of any given triangulation G. We show, using the Knaster-Kuratowski-Mazurkiewicz Theorem, that some drawing of G belonging to this class is greedy.

-Matthew Kahle (U Washington): The neighborhood complex of a random graph
Abstract: Since Lovasz's proof of Kneser's conjecture in 1979, there has been continuing work on using topological techniques to establish lower bounds on chromatic numbers on graphs. In this talk the main questions we're motivated by are: "How often are such bounds good?" and "For which kinds of graphs are they likely to work well?", and our approach is probabilistic.

We first consider the Erdos-Renyi random graph as our model of a "typical" graph and find that we can understand what Lovasz's original bound tells us in this setting quite well, within a small constant factor, almost always. Unfortunately, in this setting the bound is quite far from the truth, but the proofs also shed some light on why: there are, in some sense, too many cliques and comparatively not enough complete bipartite subgraphs. This suggests a different model of random graph defined geometrically, and which should provide large classes of examples for which the Lovasz bound is tight. We'll briefly discuss ongoing work in this area and end with open problems.

Tuesday, October 3

11:00 am: Michael Joswig (Technische Universität, Darmstadt): Explicit computations in algebraic topology
Abstract: This is a survey of known algorithms in algebraic topology with a focus on finite simplicial complexes and, in particular, simplicial manifolds.

2:00 pm: Carsten Schultz (Technische Universität Berlin): Homomorphism complexes of graphs: Constructions and Computations
Abstract: We discuss the topological graph coloring bounds by Lovász and by Babson and Kozlov, their strengths and relation to each other, and how they inspire the construction of interesting classes of graphs.

We also comment on algorithms for the computation of these bounds and how they may lead to the detection of interesting subgraphs of a given graph.

Parts of this work are joint with Eric Babson and Anton Dochtermann.

3:30 pm: Persi Diaconis (Stanford University): Graph homomorphisms and the birthday problem

4:30 pm: Poster session/reception

Wednesday, October 4

11:00 am: Nikolaus Witte (Institute of Mathematics, Berlin): Branched covers: A combinatorial model and applications
Abstract: Branched covers have been used widely to study and classify manifolds. Most prominently, Hilden and (independently) Montesinos constructed closed oriented 3-manifolds as branched covers of the 3-sphere branched over a link. Piergallini generalized their result to closed oriented PL 4-manifolds.

We present a combinatorial construction of branched covers, the unfoldings introduced by Izmestiev & Joswig. The unfoldings are then applied in an explicit construction of closed oriented combinatorial 4-manifolds.

2:00 pm: Kevin Knudson (Mississippi State University): Algorithms in discrete Morse theory
Abstract: Suppose we are given a real-valued function f on the vertices of a finite simplicial complex K. In this talk, I will describe an algorithm to extend f to a discrete Morse function (in the sense of Forman) on all of K in an efficient manner that mirrors the large-scale behavior of f. As time permits, I will also discuss a parameterized version which allows one to trace birth and death of critical points.

The talk will be self-contained; no prior knowledge of discrete Morse theory will be assumed.

This is joint work with Henry King (U. of Maryland) and Neza Mramor (U. of Ljubljana).

3:30 pm: Graham Denham (University of Western Ontario): Generalized moment-angle complexes
Abstract: A construction originating in work of Davis and Januszkiewicz gives an interesting "combinatorial" family of spaces which are parameterized by a finite simplicial complex and a pair of spaces. By making suitable choices, one obtains a range of familiar and less familiar spaces: classifying spaces for right-angled Artin groups, Coxeter groups, and Bestvina-Brady groups; the moment-angle complexes of Buchstaber and Panov; the complements of certain real and complex subspace arrangements.

The topological invariants of some of these spaces can be described particularly explicitly, via combinatorial commutative algebra. The talk will give some new results of this sort, and will attempt to promote the construction as interesting and useful. (joint work with Alex Suciu)

Thursday, October 5

11:00 am:Martin Raussen (University of Aalborg): Invariance of directed spaces and persistence
Abstract: With motivations arising from concurrency theory within Computer Science, a new field of research, directed algebraic topology, has emerged. The main characteristic is, that it involves spaces of "directed paths'' (or timed paths, executions) in a "directed space''; these directed paths can be concatenated, but in general /not/ reversed; time is not reversable. The combinatorics of spaces of directed paths with fixed endpoints can be studied via (homotopy or homology) functors from the preorder category of the directed space to a category like /Ho-Top/ or /Ab/; this point of view allows to generalize previous work on the fundamental category of such a space. Birth and death of homology classes indicate structural changes at various levels. We give a definition of a directed homotopy equivalence (which is not the obvious generalization of the classical notion), and we describe "smaller" models for the homotopy and homology functors mentioned above.

2:00 pm: Michael Joswig (Technische Universität, Darmstadt): Bounds for the f-vectors of tight spans
Abstract: The tight span T_d of a metric d on a finite set is the subcomplex of bounded faces of an unbounded polyhedron defined by d. If d is generic then T_d is known to be dual to a regular triangulation of a second hypersimplex. A tight upper and a partial lower bound for the face numbers of T_d (or the dual regular triangulation) are presented. This is joint work with Sven Herrmann (TU Darmstadt).

4:10 pm at UC Berkeley - Math Department Colloquium: Herbert Edelsbrunner (Duke): Global methods for high-dimensional data sets
Abstract: Considering the problem of learning about the structure of large and possible high-dimensional datasets, we take a global approach aimed at determining their gross topology. Specifically, we introduce a parametrized family of witness complexes modeling the data and methods to extract the persistent topology from the family. We explain this construction in two steps, first introducing Cech, Rips, Alpha, and almost Alpha complexes for modeling the datasets. The extension to witness complexes rests on the Weak Delaunay Theorem by de Silva, which we generalize from Delaunay to almost Alpha complexes. Building on these ideas, we propose the family of alpha-beta witness complexes as a general global method to study datasets.

Friday, October 6

11:00 am: Raman Sanyal (Technische Universitaet Berlin): Topological obstructions to polytope projection
In this talk we will outline a strategy for deciding whether polytopes with prescribed combinatorial and/or geometric properties exist. We will exemplify the strategy, which makes use of Gale transforms and methods from combinatorial equivariant topology, by presenting two new results as well as a guided tour through the proofs. The first result gives topological obstructions to the realization of products of odd polygons having certain properties under projection. The second complements a recent result of Fukuda & Weibel concerning the number of vertices of Minkowski sums.

1:00 pm - 3:30 pm: Contributed talks:

• Anton Dochtermann (U Washington): Universality of Hom-complexes
• Shripad Thite (Eindhoven): Pants decomposition of the punctured plane
• Javier Arsuaga (SFSU): Using computational knot theory to understand DNA packing in viruses
• Abhishek Bhattacharya (Arizona): Statistics on the planar shape space