contact us

Use the form on the right to contact us.

You can edit the text in this area, and change where the contact form on the right submits to, by entering edit mode using the modes on the bottom right.

Williams College
Williamstown, MA 01267

(413) 597-3519

Satyan Devadoss, Professor of Mathematics, Williams College



Click on the associated figure to download the PDF version of the paper. Most of this work is supported by the National Science Foundation, with additional funding by DARPA, the Mellon Foundation, and the Whiting Fellowship. Any opinions, findings, and conclusions are those of the author(s) and do not necessarily reflect the views of these organizations.

Cartography of Tree spacE

Leonardo Journal, to appear

O. Schuh (Philadelphia artist)

How can vibrant, contemporary art be produced that deals with vibrant, contemporary mathematics? To address this, a collaboration began between an artist and a mathematician, revolving around recent problems in phylogenetics and the space of evolutionary trees. The result was two-fold: First, a triptych of paintings was created, using acrylic, graphite, watercolor, and metal leaf, that focused on different navigations within this tree space. And second, a novel set of open mathematics problems was discovered solely from this investigation. 

A Space of phylogenetic Networks

arxiv preprint 2016

S. Petti (Georgia Tech)

A classic problem in computational biology is constructing a phylogenetic tree given a set of distances between n species.  In most cases, a tree structure is too constraining.  We consider a circular split network, a generalization of a tree in which multiple parallel edges signify divergence. A geometric space of such networks is introduced, forming a natural extension of the work by Billera, Holmes, and Vogtmann on tree space.  We explore properties of this space, and show a natural embedding of the compactification of the real moduli space of curves within it.

Visualizing Scissors Congruence

Symposium on Computational Geometry:  Multimedia (2016)

Z. Epstein, D. Smirnov (Pomona)

Consider two simple polygons with equal area.  The Wallace-Bolyai-Gerwien theorem states that these polygons are scissors congruent, able to be dissected into finitely many congruent polygonal pieces.  We present an interactive application that visualizes this constructive proof.

Navigation in Tree Spaces

Advances in Applied Mathematics 67 (2015) 75 - 95

J. Morava (Johns Hopkins)

The orientable cover of the moduli space of real genus zero algebraic curves with marked points is a compact aspherical manifold tiled by associahedra, which resolves the singularities of the space of phylogenetic trees. The resolution maps planar metric trees to their underlying abstract representatives, collapsing and folding an explicit geometric decomposition of the moduli space into cubes. This decomposition endows the resolving space with an interesting canonical pseudometric.

Convex Polytopes from Nested Posets

European Journal of Combinatorics 43 (2015) 229 - 248

S. Forcey, S. Reisdorf, P. Showers (Akron)

Motivated by the graph associahedron KG, a polytope whose face poset is based on connected subgraphs of G, we consider the notion of associativity and tubes on posets. This leads to a new family of simple convex polytopes obtained by iterated truncations. These generalize graph associahedra and nestohedra, even encompassing notions of nestings on CW-complexes, but fall in a different category altogether than generalized permutohedra.

Polyhedral Covers of Tree Space

SIAM Journal of Discrete Mathematics 28 (2014) 1508 - 1514

D. Huang (Cornell), D. Spadacene (Michigan)

We construct the space of phylogenetic trees from local gluings of classical polytopes, the associahedron and the permutohedron. Its homotopy is also reinterpreted and calculated based on polytope data.

Skeletal Configurations of Ribbon Trees

Discrete Applied Mathematics 170 (2014) 46 - 54

H. Cheng (Arizona), B. Li (NIH), A. Risteski (Princeton)

The straight skeleton construction creates a straight-line tree from a polygon. Motivated by moduli spaces from algebraic geometry, we consider the inverse problem of constructing a polygon whose straight skeleton is a given tree. We prove there exists only a finite set of planar embeddings of a tree appearing as straight skeletons of convex polygons. The heavy lifting of this result is performed by using an analogous version of Cauchy's arm lemma. Computational issues are also considered, uncovering ties to a much older angle bisector problem

Diagonalizing the Genome II: Toward Possible Applications

arxiv preprint 2012

J. Morava (Johns Hopkins)

We construct a related (stacky) resolution of a space of real quadratic forms, and suggest, perhaps without much justification, that systems of oscillators parametrized by such objects may may provide useful models in genomics. 

The Shape of Associativity

Canadian Mathematical Society Notes 44 (2012) 12 - 14

Associativity is ubiquitous in mathematics. Unlike commutativity, its more popular cousin, associativity has for the most part taken a backseat in importance. But over the past few decades, this concept has blossomed and matured. We start with a brief look at three fields of mathematics where this has transpired, and then explore the visualization of associativity.

Deformations of Associahedra and Visibility Graphs

Contributions to Discrete Mathematics 7 (2012) 68 - 81

R. Shah (Williams), X. Shao (MIT), E. Winston (Bard)

Given a arbitrary polygon P with holes, we construct a polytopal complex analogous to the associahedron based on convex diagonalizations of P. This polytopal complex is shown to be contractible, and a geometric realization is provided based on the theory of secondary polytopes.  We then reformulate a combinatorial deformation theory and present an open problem based on visibility which is a close cousin to the carpenter's rule statement of computational geometry.

What makes a Tree a Straight Skeleton?

Proceedings of the Canadian Conference on Computational Geometry (2012)

O. Aichholzer (Graz), H. Cheng (Arizona), T. Hackl (Graz), S. Huber (Salzburg), B. Li (Williams), A. Risteski (Princeton)

Let G be a cycle-free connected straight-line graph with predefined edge lengths and fixed order of incident edges around each vertex. We address the problem of deciding whether there exists a simple polygon P such that G is the straight skeleton of P. We show that for given G, such a polygon P might not exist, and if it exists it might not be unique.

Moduli Spaces of Punctured Poincaré Disks

Tamari Memorial Festschrift: Progress in Mathematics Volume 299 (2012) 

B. Fehrman (Chicago), T. Heath (Columbia), A. Vashist (Michigan)

The Tamari lattice and the associahedron provide methods of measuring associativity on a line. The real moduli space of marked curves captures the space of such associativity.  We consider a natural generalization by considering the moduli space of marked particles on the Poincaré disk, extending Tamari's notion of associativity based on nesting. A geometric and combinatorial construction of this space is provided, which appears in Kontsevich's deformation quantization, Voronov's swiss-cheese operad, and Kajiura and Stasheff's open-closed string theory.

Triple Infinity

Esopus Magazine (Fall 2011)

A.Shotz (artist), P. Natarajan (Yale)

An artist, a mathematician, and a cosmologist walk into a bar, and discuss the nature of infinity.

Pseudograph Associahedra 

Journal of Combinatorial Theory, Series A 118 (2011) 2035 - 2055

M. Carr (Brandeis), S. Forcey (Tennessee State)

Given a simple graph G, the graph associahedron KG is a simple polytope whose face poset is based on the connected subgraphs of G. This paper defines and constructs graph associahedra in a general context, for pseudographs with loops and multiple edges, which are also allowed to be disconnected.  We then consider deformations of pseudograph associahedra as their underlying graphs are altered by edge contractions and edge deletions.

Deformations of Bordered Surfaces and Convex Polytopes

Notices of the American Mathematical Society 58 (2011) 530 - 541

T. Heath (Columbia), C. Vipismakul (UT Austin)

We consider the moduli space of Riemann surfaces with boundary and marked points. Such spaces appear in open-closed string theory, particularly with respect to holomorphic curves with Lagrangian submanifolds. We consider a combinatorial framework to view the compactification of this space based on the pair-of-pants decomposition of the surface, relating it to the well-known phenomenon of bubbling. Our main result classifies all such spaces that can be realized as convex polytopes.

Particle Configurations and Coxeter Operads

Homotopy and Related Structures 4 (2009) 83 - 109

S. Armstrong (Williams), M. Carr (Michigan), E. Engler (Williams), A. Leininger (MIT), M. Manapat (Berkeley)

There exist natural generalizations of  the real moduli space of Riemann spheres based on manipulations of Coxeter complexes. These novel spaces inherit a tiling by the graph-associahedra convex polytopes. We obtain explicit configuration space models for the classical infinite families of finite and affine Weyl groups using particles on lines and circles. A Fulton-MacPherson compactification of these spaces is described, which in then used to define the Coxeter operad. A complete classification of the building sets of these complexes is also given, along with a computation of their Euler characteristics.

Shape Deformation in Continuous Map Generalization

GeoInformatica 13 (2009) 203 - 221

J. Danciger (Stanford), J. Mugno (Maryland), D. Sheehy (Carnegie Mellon), R. Ward (Princeton)

Given a collection of regions on a map, we seek a method of continuously altering the regions as the scale is varied. This is formalized and brought to rigor as well-defined problems in homotopic deformation. We ask the regions to preserve topology, area-ratios, and relative position as they change over time. A solution is presented using differential methods and computational geometric techniques. Most notably, an application of this method is used to provide an algorithm to obtain cartograms.

A Realization of Graph Associahedra

Discrete Mathematics 309 (2009) 271 - 276

Given any finite graph, we offer a simple realization of its corresponding graph associahedron polytope using integer coordinates.

Marked Tubes and the Graph Multiplihedron

Algebraic and Geometric Topology 8 (2008) 2081 - 2108

S. Forcey (Tennessee State)

Given a graph G, we construct a convex polytope whose face poset is based on marked subgraphs of G. Not only does this yield a natural generalization of the multiphihedron, but features of this polytope appear in works related to quilted disks, bordered Riemann surfaces, and operadic structures. Certain examples of graph multiplihedra are related to Minkowski sums of simplices and cubes and others to the permutohedron.

Juggling Braids and Links

The Mathematical Intelligencer (2007) 15 - 22

J. Mugno (Maryland)

Using a simplistic model of juggling based on physics, a natural map is constructed from the set of periodic juggling patterns to links. We then show that all topological links can be juggled.

Compatible Triangulations and Point Partitions by Series-Triangular Graphs

Computational Geometry: Theory and Applications 34 (2006) 195 - 202

J. Danciger (UC Santa Barbara), D. Sheehy (Princeton)

We introduce series-triangular graph embeddings and show how to partition point sets with them.  This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets.  The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set.

Coxeter Complexes and Graph Associahedra

Topology and its Applications 153 (2006) 2155 - 2168

M. Carr (Michigan)

Given a graph G, we construct a simple, convex polytope whose face poset is based on the connected subgraphs of G. This provides a natural generalization of the Stasheff associahedron and the Bott-Taubes cyclohedron. Moreover, we show that for any simplicial Coxeter system, the minimal blow-ups of its associated Coxeter complex has a tiling by graph associahedra. These spaces are natural generalizations of the Deligne-Knudsen-Mumford compactification of the real moduli space of curves.

Continuous Foldability of Polygonal Paper

Proceedings of the Canadian Conference on Computational Geometry (2004)

E. Demaine (MIT), J. Mitchell (Stony Brook), J. O'Rourke (Smith)

We prove that any given well-behaved folded state of a piece of paper can be reached via a continuous folding process starting from the unfolded paper and ending with the folded state.

Combinatorial Equivalence of Real Moduli Spaces

Notices of the American Mathematical Society 51 (2004) 620 - 628

The Riemann moduli space of spheres with marked points has become a central object in mathematical physics. There is a Deligne-Knudsen-Mumford compactification of this space coming from Geometric Invariant Theory which allows collisions of points of the configuration space. The real spaces, unlike their complex counterparts, have an inherent tiling, which allows an intuitive, combinatorial construction. Along the way, we provide a new construction of the associahedron from products of simplices.

A Space of Cyclohedra

Discrete and Computational Geometry 29 (2003) 61 - 75

The real points of the Deligne-Knudsen-Mumford moduli space of marked points on the sphere have a natural tiling by associahedra. We extend this idea to construct an aspherical space tiled by cyclohedra. We explore the structure of this space, coming from blow-ups of hyperplane arrangements, as well as discuss possibilities of its role in knot theory and mathematical physics.

Cellular Structures determined by Polygons and Trees

Annals of Combinatorics 5 (2001) 71 - 98

R. C. Read (Waterloo)

The polytope structure of the associahedron is decomposed into two categories, types and classes. The classification of types is related to integer partitions, whereas the classes present a new combinatorial problem.  We solve this, and incorporate the results into properties of moduli spaces. Connections are discussed with relation to classic combinatorial problems as well as to other sciences.

Tessellations of Moduli Spaces and the Mosaic Operad

Contemporary Mathematics 239 (1999) 91 - 114

We construct a new (cyclic) operad of mosaics defined by polygons with marked diagonals. Its underlying (aspherical) spaces are the compactification of the real moduli space of curves, naturally tiled by Stasheff associahedra. We describe them as iterated blow-ups and show that their fundamental groups form an operad with similarities to the operad of braid groups.