July - December 2011 Thematic Program on Discrete Geometry and Applications October Workshops Proposed talk titles and abstract submissions. Accepted talks will be 20 to 30 minutes in length.

OCTOBER WORKSHOPS

October 11-14, 2011
Workshop on Rigidity

Alfakih, Abdo Y.
On the Universal rigidity of bar frameworks in general position

A bar framework G(p) in r-dimensional Euclidean space is a graph G whose vertices are points p1, p2,.., pn in R^r, and whose edges are line segments connecting pairs of these points. A given framework G(p) in R^r is said to be universally rigid if there does not exist a non-congruent framework G(q) in any Euclidean space with the same edge lengths as those of G(p). A framework G(p) in R^r is generic if the coordinates of p1,...,pn are algebraicaly independent over the integers. On the other hand, G(p) is in general position in R^r if there is no subset, of cardinality r+1, of the points p1, ...,pn that is affinely dependent. It is known that a generic framework G(p) on n vertices in R^r is universally rigid if and only if G(p) admits a positive semi-definite stress matrix of rank n-r-1. In this talk, I’ll show that the "if" part of this result still holds under the weaker assumption of a framework in general position. Universal rigidity has many important applications in molecular conformation and wireless sensor networks.
(This is a joint work with Yinyu Ye).

Bezdek, Karoly
Rigid ball-polyhedra in Euclidean 3-space

A ball-polyhedron is the intersection with non-empty interior of finitely many (closed) unit balls in Euclidean 3-space. One can represent the boundary of a ball-polyhedron as the union of vertices, edges, and faces defined in a rather natural way. A ball-polyhedron is called a simple ball-polyhedron if at every vertex exactly three edges meet. Moreover, a ball-polyhedron is called a standard ball-polyhedron if its vertex-edge-face structure is a lattice (with respect to containment). To each edge of a ball-polyhedron one can assign an inner dihedral angle and say that the given ball-polyhedron is rigid with respect to its inner dihedral angles if the vertex-edge-face structure of the ball-polyhedron and its inner dihedral angles determine the ball-polyhedron up to congruence locally. The main result of this talk is a Cauchy-type rigidity theorem for ball-polyhedra stating that a simple ball-polyhedron is rigid with respect to its inner dihedral angles if and only if it is a standard ball-polyhedron. This is a joint work with M. Naszodi (Eotvos Univ., Budapest).

Cheng, Jialong and Sitharam, Meera
Better Estimates of 3D rigidity

Maxwell's condition states that the edges of a graph are independent in its d-dimensional generic rigidity matroid only if (a) the number of edges does not exceed d|V| - {d+1 choose 2}, and (b)this holds for every induced subgraph. Such graphs are called Sparse orMaxwell-independent in d-dimensions.Laman's theorem shows that the converse holds in 2D. While the converse is false in 3D, we answer the following questions in the affirmative. The first question was posed by Tib'or Jord'an at the 2008 rigidity workshop at BIRS.
We consider the following questions.
Question 1:Does every maximal, Maxwell-independent set of a graph have size at least the rank?
Question 2: Is there a better and tractable combinatorial upper bound (than the number
of edges) for Sparse or Maxwell-independent graphs?We give affirmative answers to both questions. As one consequence, the answers also give simpler proofs of correctness for existing algorithms
that give rank bounds.

Connelly, Bob Cornell University
Rigidity, tensegrities, and some applications

The theory of rigid structures has been developed greatly over the last fifty years or so. This will be a discussion of some of the main results and the main concepts. One important thing is what is the definition of rigidity? Local rigidity, global rigidity, infinitesimal rigidity, static rigidity, and uniform rigidity all are good examples of definitions that are possible. I will discuss what these mean and show some of the connections and applications. Another important thing is what are the objects that are rigid. There are bar-and-joint frameworks, tensegrities, packings, bar-and-body frameworks, and body-hindge, for example. This is a background and preview of many of the talks to come.

Crapo, Henry
Isostatic Graphs and Semi-simplicial Maps

Following work initiated by Tiong Seng Tay, we know that a graph $G$ is generically isostatic in dimension $D$ if it has a shellable semi-simplicial map $f$ to the $D$-simplex $K_{d+1}$. The converse is known only for $D=1,2$. We of course concentrate on the case $D=3$. In a semi-simplicial map to $K_4$, incidence must be preserved: edges whose end vertices go to the same vertex, say $j$, we call a {\it loop at $j$}, which must be sent to an edge of $K_4$ incident to $j$. We also insist that the inverse image $f^{-1}(ij)$ of any edge $ij$ of $K_4$ be a {\it tree} connecting the vertex set $f^{-1}(i)\cup f^{-1}(j)$. A map is {\it shellable} if and only if, starting from the degenerate placement of the graph as its image under $f$, {\it in} the tetrahedron, the vertices can be gradually separated without making discontinuous change in edge directions. A simple proof shows that the existence of a shellable semi-simplicial map $F:G\to K_4$ implies $G$ is $3$-isostatic. It is not known whether every $3$-isostatic graph has such a shellable map. But "normally" there are so many you would not want to bother to count them.
Computer programs, which I write in Python, can establish that a given graph is isostatic, and quickly so, simply because so many shellable maps exist. But such programs are virtually useless in showing that a 3v-6 graph is dependent, since we must wait until the dreary end of the computation, only to find that there are no shellable maps, \dots and even then not to be sure of dependency, since there is no such theorem proven.
The situation is very similar to that encountered when using Henneberg reduction (and for good reason).
In this talk we describe recent work to cut down the search for maps, and to eliminate the need to produce shellings, by concentrating on maps in which non-shellable vertex packets (inverse images of a single vertex) can not occur: those in which vertex packets induce subgraphs having no cycles. Such maps are {\it "freely shellable"}. Roger Poh has proven that for any planar graph there is a partition of its vertices into no more than three parts, each part inducing a path as subgraph. Such partitions are not necessarily vertex partitions under inverse image of a semi-simplicial map. But since maximal planar graphs are generically $3$-isostatic, we are still led to conjecture that isostatic graphs share similar properties. We conjecture:{\it A graph G is generically $3$-isostatic graph if and only if it has a semi-simplicial map to the tetrahedron in which all vertex packets induce subgraphs that are broken paths (forests with all vertices of valence $1$ or $2$).}
This conjecture is false if you insist that the induced subgraphs be paths. As an example, consider a hinged ring of six tetrahedra.

Time permitting (or on another occasion during the week) we should discuss computational methods for constructing the generically 3-rigid {\it components} of an arbitrary graph, or for finding dependencies.

Dickinson, William Grand Valley State University
Packings of Equal Circles on Flat Tori

We outline an algorithm to find all the locally maximally dense packings of a fixed number of equal circles on any flat torus. The algorithm uses the tools of rigidity theory and topological graph theory. We have applied this to the case of 3 equal circles and have determined all the locally maximally dense packings on any flat torus in this case. We have also applied this on upto six equal circles on certain flat and have determined some other optimal arrangements. This is joint work with AnnaVictoria Ellsworth and Jennifer Kenkel.

Erik Demaine, Massachusetts Institute of Technology
Linkage Folding: From Erd\H{o}s to Proteins

Linkages have a long history ranging back to the 18th century in the quest for mechanical conversion between circular motion and linear motion, as needed in a steam engine. In 1877, Kempe wrote an entire book of such mechanisms for "drawing a straight line". (In mathematical circles, Kempe is famous for an attempted proof of the Four-Color Theorem, whose main ideas persist in the current, correct proofs.) Kempe designed many linkages which, after solidification by modern mathematicians Kapovich, Millson, and Thurston, establish an impressively strong result: there is a linkage that signs your name by simply turning a crank.

Over the years mathematicians, and more recently computer scientists, have revealed a deep mathematical and computational structure in linkages, and how they can fold from one configuration to another. In 1936, Erd\H{o}s posed one of the first such problems (now solved): does repeatedly flipping a pocket of the convex hull convexify a polygon after a finite number of flips? This problem by itself has an intriguingly long and active history; most recently, in 2006, we discovered that the main solution to this problem, from 1939, is in fact wrong.

This talk will describe the surge of results about linkage folding over the past several years, in particular relating to the two problems described above. These results also have intriguing applications to robotics, graphics, nanomanufacture, and protein folding.

Erik Demaine, Massachusetts Institute of Technology
Geometric Puzzles: Algorithms and Complexity

Gortler, Steven -- Harvard
Characterizing Generic Global Rigidity

Consider a graph embedded in D-dimensional Euclidian space, with edges drawn as straight lines. We say that this embedding of the graph is globally rigid if it there is no other embedding of the graph in R^d with the same edge lengths (up to Euclidian transforms). Testing for global rigidity is in general NP-hard.
In this talk, I will describe a simple way to characterize global rigidity under the (mild) assumption that the embedding is "generic". In particular, we prove that Connelly's sufficient condition for generic global rigidity is also necessary. This condition can be tested efficiently using a randomized algorithm. This characterization also establishes that global rigidity is a generic property of a graph and dimension.I will also briefly touch on a related characterization of the universal rigidity of generic frameworks.This is joint work with Alex Healy and Dylan Thurston.

Jackson, Bill and Owen, John
Radical/Quadratic Realisations of a Rigid Graph

Let $f_e$ denote the set of squared edge distances in a framework $(G,p)$. We say that $(G,p)$ is radically (respectively quadratically) solvable if $(G,p)$ is congruent to a framework (G,q)$ where $q$ is in an extension field $K$ which is radical (respectively of degree $2^s$ for some s) over $\rat(d_e)$. We show that radically (quadratically) solvable is a generic property and that $G$ is quadratically solvable in dimension 2 if $G$ is globally rigid. We discuss the conjecture: if $G$ is 3-connected then $G$ is radically solvable in dimension 2 only if $G$ is globally rigid.

Jordan. Tibor Eotvos Lorand University
Geometric Sensitivity of Rigid Graphs

Kaszanitzky, Viktória
Rigid two-dimensional frameworks with two coincident points

Let G = (V;E) be a graph and u; v 2 V be two designated vertices.We give a necessaryand sufficient condition for the existence of a rigid two-dimensional framework (G; p), inwhich u; v are coincident. This result extends a classical result of Laman on the existence of a rigid framework on G. Our proof leads to an efficient algorithm for testing whether G satisfies the condition.
Joint work with Zsolt Fekete and Tibor Jordán.

Lee-St. John, Audrey Mount Holyoke College
Body-and-cad rigidity theory

Classical rigidity theory focuses on distance constraints between points. For bar-and-joint rigidity, planar properties are well-understood and have a combinatorial characterization via Laman's Theorem; higher dimensions remain a conspicuously open area. For body-and-bar structures, Tay's Theorem characterizes combinatorial rigidity in all dimensions. Both Laman's and Tay's Theorems lead to simple and efficient combinatorial algorithms.
We consider additional geometric relations by focusing on 3D body-and-cad structures, which allow coincidence, angular and distance constraints between points, lines and planes affixed to rigid bodies. These comprise most of what is found in 3D environments of constraint-based CAD software (e.g., "mates" in a SolidWorks "assembly"). Initial foundations for body-and-cad rigidity theory indicate its combinatorial properties lie somewhere between the well-understood world of body-and-bar rigidity and the open area of 3D bar-and-joint rigidity. In this talk, we present recent work on combinatorial body-and-cad rigidity and discuss several applications. Joint work with Jessica Sidman.

Lubiw, Anna University of Waterloo
Reconfiguration of Graph Drawings

We expore some problems of reconfiguring straight line planar graph drawings. Edges are represented as straight line segments, and vertices are represented as points that may move continuously in the plane. Edge lengths are not necessarily preserved, but planarity must be preserved.
For a given planar graph and a given embedding, an older result of Cairns and Thomassen shows that the configuration space is connected. We discuss algorithmic versions of this, i.e. ways to "morph" one straight line planar drawing to another. Then we consider preserving other structure in the drawing, specifically, edge directions or vertex visibilities. In the latter case, we prove that any planar cycle (i.e. any polygon) can be convexified without losing any vertex-to-vertex visibilities.

Maehara, Hiroshi
To hold a convex body by a circle

Mednykh, Alexander Sobolev Institute of Mathematics, Novosibirsk,Russia
The Brahmahupta's theorem after Coxeter.

The Heron's formula is well known from the elementary school. It gives the area of an Euclidean triangle in terms of lenghts of the sides. The non-Euclidean versions of this theorem can be found, for example, in the book by E.~B. Vinberg, Geometry II: Spaces of Constant Curvature, Springer-Verlag, 1993. The Brahmahupta's theorem is a direct generalization of the Heron's ones for the case of inscribed quadrilateral.
Following the ideas of Coxeter J.~E. Valentine, 1970 gave necessary and sufficient conditions for four points of the hyperbolic plane lie on a circle, line, horocycle, or one branch of an equidistant curve.
In this report we use these results to find a few non-Euclidean generalizations of the Brahmahupta's theorem.

Musin, Oleg R. (University of Texas at Brownsville)
Sets with few distances

A finite set X in a metric space M is called an s-distance set if the set of distances between any two distinct points of X has size s. The main problem for s-distance sets is to determine the maximum cardinality of s-distance sets for fixed s and M. Let us denote by A(M, s) the maximum cardinality of s-distance sets in M. In this talk, we are going to discuss upper bounds for A(M, s), where M is a compact two-point homogeneous space. We consider the most important cases for the coding theory, when M is a sphere, the Hamming space and the Johnson space. This talk is based on the following publications: O.R. Musin, Spherical two-distance sets // Journal of Combinatorial Theory, Series A 116 (2009) 988—995; A. Barg and O.R. Musin, Bounds on sets with few distances // Journal of Combinatorial Theory Ser. A, 118 , no. 4, 2011, pp. 1465-1474; O.R. Musin and H. Nozaki, Bounds on three- and higher-distance sets // European Journal of Combinatorics 32 (2011) 1182-1190.

Nixon, Tony
Rigidity, Circuits and Global Rigidity on the Cylinder

We discuss bar-joint frameworks in 3-dimensions where the vertices are constrained to the surface of a circular cylinder. We present a natural analogue of Laman's theorem characterising minimal infinitesimal rigidity in this context. The appropriate class of graphs are simple graphs with $2|V|-2$ edges (and the associated subgraph inequality) and we give an inductive construction of such graphs. We begin to consider global rigidity of such frameworks by analysing the circuits of this matroid; that is simple graphs with $2|V|-1$ edges such that all proper subgraphs have at most $2|V'|-2$ edges.

Penne, Rudi
Pin merging in planar body frameworks

Recski,Andras Budapest University of Technology and Economics
Characterizing minimal generic rigid graphs in the d-dimensional space

The problem in the title is trivial for d=1, well known for d=2 and is one of the most outstanding open problems of structural rigidity for d>2. We consider this problem as determining the rank of a matrix in
the ring of the multivariable polynomials, and study the various scenarios where some expansion members cancel each other. An expansion member corresponds to the decomposition of a graph into d trees such that each tree can be oriented with a priori given indegrees for every edge. Deciding the existence of such a decomposition/orientation is polynomial for d=1 but its complexity is open even for d=2. We hope that a better understanding of these scenarios will contribute towards a future generalization of Laman's theorem for d>2.

Ros, Lluís
Numerical Analysis and Navigation of Robot Linkage Configuration Spaces

The aim of this talk is to provide an overview of several algorithms for numerical analysis and navigation of robot linkage configuration spaces, under development at the Kinematics and Robot Design Group at IRI, Barcelona. In particular, algorithms will be described for (1) computing all possible configurations that a robot linkage can adopt, (2) obtaining the various singularity loci of the linkage, and (3) finding a proper path connecting two given configurations of the linkage. Along the talk, we will highlight why such problems are of interest in Robotics, and mention the global information that can be obtained, about the kinetostatic performance of the linkage. Examples will be showed of the application of the algorithms to particular linkages.

Ross, Elissa
The rigidity of graphs on the torus

We study the rigidity properties of an n-dimensional infinite periodic framework by considering such a framework as a graph embedded on an n-dimensional torus. In this talk we describe a complete characterization of generic rigidity for 2-dimensional frameworks on a torus of fixed dimensions, and on a partially variable torus. We describe necessary conditions for the rigidity of periodic frameworks on higher dimensional fixed tori.

Shai, Offer Tel Aviv University, Israel
Topics in rigidity theory from the aspect of Assur Graph (revised abstract)

Assur graphs are the building blocks of any mechanism or structure in engineering. In this talk, the advantages of using Assur Graphs in the rigidity theory community will be demonstrated. It will be shown that the footprints of Assur Graphs appear in many topics of rigidity theory. The initial point is with the Pebble Game where for any dimension d, the directions of the edges in a graph, define the decomposition of the graph into Assur Graphs (Sljoka et al., 2011). As a matter of fact, the d-edges directed out of every vertex are the 'd-dyad' and a cyclic of d-dyads constitute an Assur Graph. Pinned Isostatic graph can be defined through the correct decomposition into Assur Graphs (Shai et al., 2010). Rigidity circuits (generic circuits) in 2d are derived from Assur Graphs through the contraction of all the pinned vertices into one vertex and vice versa; that is, grounding any vertex of a rigidity circuit results in an Assur Graph (Servatius et al., 2010a). There is a conjecture related to 3d Assur Graphs and 3d rigidity circuits (Shai, 2008). In geometric constraint systems, it is possible to use the decomposition of the constraint graphs into Assur Graphs for optimization in the case where changes in dimensions of the drawing are needed (Reich and Shai, 2011). In Tensegrity, it is possible to construct novel types of Tensegrity Assur structures (Bronfeld, 2010) that can be both rigid and flexible relying on proven properties that exist solely in Assur Graphs (Servatius et al., 2010b). The unique properties of Tensegrity Assur Graphs were employed also to build a simulation for the locomotion of a caterpillar (Omer, 2011).
References
Bronfeld, 2010, Shape change control for an Adjustable Deployable Tensegrity device. M.Sc thesis, Tel-Aviv University, Israel.
Omer O., 2011, Employing Assur Tensegrity Structures Methods for Simulating a Caterpillar Locomotion, M.Sc thesis, Tel-Aviv University, Israel.
Reich and Shai, 2011, private communication with vice president of research, Dassault Systèmes, Paris, January.
Servatius B., Shai O. and Whiteley W., 2010a, Combinatorial Characterization of the Assur Graphs from Engineering, European Journal of Combinatorics, Vol. 31, No. 4, May, pp. 1091-1104

Servatius B., Shai O. and Whiteley W., 2010b, Geometric Properties of Assur Graphs, European Journal of Combinatorics, Vol. 31, No. 4, May, pp. 1105-1120.

Shai O., 2008, Canonical Forms for Multidimensional Isostatic Frameworks, Determinate trusses, Linkages and R-tensegrity Systems, Recent Progress in Rigidity Theory, July 12, Banff International research Station - Canada.
Shai O., Sljoka A. and Whiteley W., Directed Graphs, Decompositions, and Spatial Rigidity, submitted to Discrete Applied Mathematics, 2010.
Sljoka A., Shai O and Whiteley W., Checking mobility and decomposition of linkages via Pebble Game Algorithm, ASME Design Engineering Technical Conferences, August 28-31, 2011, Washington, USA.

Robert E Skelton UCSD
Optimal Complexity in Structures

I will show the minimal mass solution for tensegrity structural systems for the fundamental load conditions: bending (cantilevered) loads, compressive loads, tensile loads, and torsional loads. I will show that each of these problems has an optimal complexity (the total number of components). I will also show a single connectivity of tensile and compressive members that all yield the same dynamic model.

Sitharam, Meera and Wang, Menghan and Gao, Heping
Cayley configuration spaces of 1-degree-of-freedom linkages

We study the 2D configuration spaces of 1-degree-of-freedom (dof)
linkages obtained by dropping a bar from a triangle-decomposable linkage. The latter linkages are minimally rigid and well-studied, for example, in geometric constraint solving for CAD, because they are
quadratic-radical solvable (QRS also called ruler-and-compass constructible): in other words, the point coordinates that realize rational bar lengths belong to an extension field over the rationals obtained by nested square-roots (solutions to a triangularized quadratic system with rational coefficients). Additionally, if a relative local orientation is specified for each point, then there is a linear time algorithm to compute the point coordinates of the unique cartesian configuration satisfying the specified orientations (if one exists). To represent the 2D configuration space of a 1-dof linkage, we use the set of realizable distance-values for an independent non-edge f- we call this the Cayley configuration space over f. This space consists of a set of intervals on the real line.We are interested in various aspects of the complexity of Cayley configuration spaces:
(a) the Cayley algebraic complexity of describing the interval end points,
(b) the Cayley size, i.e., the number of intervals,
(c) the Cayley computational complexity of computing the interval endpoints, as a function of the number of intervals.
The first question we answer is the following: consider the Cayley configuration space of a 1-dof linkage G on any non-edge f such that G U f is triangle-decomposable; does its Cayley complexity ((a) above) depend on the choice of f? We answer this question in the negative. Specifically, we show that if the interval endpoints are QRS for the Cayley configuration space over some choice of f, then they are QRS for any choice of f. This shows robustness of the Cayley complexity measure, for 1-dof triangle decomposable linkages. In addition, we give an algorithmic characterization of 1-dof, triangle decomposable linkages with QRS Cayley complexity.
Next, we show a surprising result that (graph)planarity is equivalent to QRS Cayley complexity for a natural subclass of 1-dof triangle-decomposable linkages. While this is a finite forbidden minor graph characterization of QRS Cayley complexity, we provide counterexamples showing impossibility of such finite forbidden minor characterizations when the above subclass is enlarged. Finally, we consider (b) and (c) above for 1-dof, triangle decomposable linkages with QRS Cayley complexity. We give a natural, minimal set of local orientations whose specification guarantees Cayley size of 1 and linear Cayley computational complexity. Specifying fewer orientations results in a superpolynomial blow-up of both the Cayley size and computational complexity, provided P is different from NP.

Stachel, Helmuth
On the flexibility of Kokotsakis meshes

A Kokotsakis mesh is a polyhedral structure consisting of an $n$-sided central polygon $p_0$ surrounded by a belt of quadrangles or triangles such that each side $a_i$ of $p_0$ is shared by an adjacent polygon $p_i$ and the relative motion between cyclically consecutive neighbor polygons is a spherical coupler motion. Hence, each vertex of $p_0$ is the meeting point of four faces. \\
These structures with rigid planar faces and variable dihedral angles were first studied in the thirties of the last century. However, in the last years there was a renaissance. The question under which conditions such meshes are flexible (infinitesimally or continuously) became important for the field of discrete differential geometry as well as for the theory of paper folding. \\ While for arbitrary $n$ the classification of continuously flexible Kokotsakis meshes is an open problem, we know since R. Bricard the solution for $n=3$. For $n=4$, each nontrivial flexible example includes a multiply decomposable composition of two spherical four-bar mechanisms. Based on the known examples, there is a conjecture that the reducibility of this composition, i.e., a 4-4-correspondance, is a necessary condition for continuous flexibility. G. Nawratil recently listed all reducible compositions. If the conjecture holds true, a classification of all flexible quadrangular Kokotsakis meshes seems to be possible.

Tanigawa, Shin-ichi
Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries
Joint work with Naoki Katoh

Theran, Louis
The rigidity transition in random graphs

If we build a framework on a generic set of n points in the plane in the plane by adding bar one at a time uniformly at random, after how many edges will we see a rigid component larger than a triangle? How big is this rigid component when it emerges, and is it unique or are there many?
Shiva Kasiviswanathan and Cris Moore answered these questions as follows: There is a constant c_2\approx 3.588 such that, in a sparse Erdos-Renyi random graph G(n,c/n):
* If c < c_2, all rigid components are triangles, edges, or single vertices with high probability
* If c > c_2, then there is a unique linear-sized rigid component with high probability
The interesting thing from a rigidity standpoint is that c_2 is quite a bit below 4 and that the transition is sudden. The value of c_2 had been found in simulation by Rivoire and Barre, and we confirm their observations theoretically.

Whiteley, Walter York University
How do we generate finite motions for generically rigid graphs?

We will survey situations structures will unexpectedly have a finite motion, for configurations generic within a class of constraints.
(a) There are a number of examples where a symmetry can turn a generically rigid graph into a graph that has finite motions, while other symmetries do not have this impact.
(b) Circumstances where flatness of a set of points can generate an infinitesimal motion that preserves the flatness also generate a finite motion (e.g. K5,5 with one side coplanar).
(c) For braced plane discs of parallelograms and triangles, and some forms of their 3D analogs, every infinitesimal is a finite motion;
(d) Special configurations with second order flexibility are guaranteed to be flexible;
(e) Second step flexibility, in which a first order flex at a regular point of a variety is tangent to the variety;
(f) Sufficient points (or implied points) at infinity (including slide joints).

We also consider when these finite motions are conserved by changes of the metric or the dimension of the space via coning or other geometric transformations. Our goal is to also highlight some new research problems and promising approaches.

Back to top

October 17-21, 2011
Workshop on Rigidity and Symmetry

• Alexandrov, Victor (Sobolev Institute of Mathematics and Novosibirsk State University)
  The Dehn invariants of the Bricard octahedra
  We prove that the Dehn invariants of any Bricard octahedron remain constant during the ?ex and that the Strong Bellows Conjecture holds true for the Steffen ?exible polyhedron.

• Apel, Susanne
  An Invariant theoretic view on 10 points on a cubic
  The work presented here is from Jürgen Richter-Gebert who is not able to be present himself. Starting from a discussion with Jim Blinn which was related to invariant theoretic aspects of the Cayley-Bacharach theorem, Jürgen tried to find a bracket polynomial expressing the fact that 10 points in the projective plane lie on a common cubic curve. It is natural to ask for a homogenous polynomial of degree three (ten brackets per monomial). This is, the starting point for the investigations. Jürgen was able to find a nice and symmetric solution for this problem. However it has 30240 summands. It has analogies with the case of quadrics and the underlying concept can be generalized to curves of every degree. On the other hand using an idea of Jim Blinn, that produces a related polynomial with 12 brackets per summand and a determinatal trick, he was able to find a formula with summands to 26. However, the result is far from being symmetric. So far we were not able, to find a better solution. May it be that (in this case) symmetry and conciseness are two incompatible  concepts?

• Baake, Michael and Grimm, Uwe
  Aperiodic Tilings: Notions and Properties I & II
  These two talks give an introductory account of the theory of aperiodic order, focussing on aperiodic tilings of space. In particular, notions of symmetry and equivalence concepts are introduced, and key
  properties are demonstrated by means of examples. The recent discovery by Joan Taylor of an hexagonal monotile of the plane is discussed in detail.
  
  

• Borcea,Ciprian
  Deformations of crystal frameworks
  This is joint work with Ileana Streinu.
  We apply our deformation theory of periodic bar-and-joint frameworks to tetrahedral crystal structures. The deformation space is investigated in detail for frameworks modelled on quartz, cristobalite and tridymite.

• Conder, Marston
  Large groups acting on surfaces/structures of given genus, and the symmetric genus of a given group
  This lecture will concentrate on recent developments with regard to these questions:
  What is the {\em largest number of automorphisms\/} of \\ $\bullet\,$ a compact orientable surface of given genus $g > 1$ ? \\ $\bullet\,$ a compact non-orientable surface of given genus $g > 2$ ?
  Given a finite group $G$, what is the {\em smallest genus of faithful actions\/} of $G$ on \\ $\bullet\,$ compact orientable surfaces? \\ $\bullet\,$ compact orientable surfaces, preserving orientation? \\ $\bullet\,$ compact non-orientable surfaces?
  Answers to questions like these may be found by investigating properties of finite quotients of Fuchsian and non-Euclidean crystallographic groups.
  Some of what I will report is joint work with Tom Tucker (New York).
  
  

• De Saedeleer, Julie, Université Libre de Bruxelles
  The geometry of the groups PSL(2,q).
  In this talk, we will describe geometric structures consisting of points and lines, that have a group PSL(2,q) acting transitively on the pairs of incident points and lines. We will focus on the case where the group PSL(2,q) acts primitively on the points.
  We give a complete classification of the rank two geometries of the groups PSL(2,q).In the context of the search for locally s-arc-transitive graphs related to families of simple groups, we give the classification with one more axiom namely that the group be primitive on one bipart of the vertex set. And finally we will give the most recent developments on geometries of the groups PSL(,q).
  
  
• Dolbilin, Nikolai, Steklov Mathematical Institute, currently at the Fields Institute and Queen's University
  Parallelohedra and a Walk Alround the Voronoi Conjecture
  
  

• Fowler, Patrick W. Department of Chemistry, University of Sheffield, UK
  Counting with symmetry: extended versions of mobility criteria
  Characterisations of mobility and rigidity are often expressed in terms of necessary, though usually not sufficient, criteria embodied in ‘counting rules’. These include Maxwell’s rule for rigidity of frames and its extension due to Calladine, and the mobility criterion due to Gruebler and Kutzbach. The sets of objects being counted (bars, joints, mechanisms, states of self stress, rigid-body motions, freedoms of particular types of connector) have collective symmetry. If this is taken into account, the counting rules can be extended to statements about reducible representations, giving a version of the rule for each class of symmetry operations. This often sharpens the conclusions, and yields detailed information about the physical character of mechanisms, states of self stress, and so on. In this respect, each counting rule is the trace under the identity operation of an extended symmetry rule, the tip of a group-theoretical iceberg of potentially useful information.
  This contribution discusses some symmetry-extended counting rules in rigidity and mobility, and puts them in the context of similar considerations in chemistry, where mechanical and pictorial models are often informative, and symmetry is very often a key consideration.
  This is joint work with Simon D. Guest (Cambridge)
  

• Guest, Simon
  Generating symmetric tensegrities
  Connelly showed how it was possible to generate a catalogue of symmetric tensegrities that have a single regular orbit of nodes, one orbit of struts, and two orbits of cables. I will explore how it might be possible to extend this catalogue to consider systems that have one or more orbits of nodes, which may not be regular.
  

• Hubard, Isabel, UNAM
  Equivelar 4-twistoids, part I
  In this talk we shall consider 4-polytopes that arise as quotients of the Euclidean tessellation {4,3,4} by fixed point free crystallographic groups of the Euclidean space.
  

• Jackson, Bill
  The number of 2-dimensional complex realisations of a rigid graph
  Given a generic realisation $(G,p)$ of a rigid graph $G$, the number of realisations of $G$ which are equivalent to $(G,p)$ and are pairwise non-congruent depends only on the graph $G$. We denote this number by $c(G)$. We determine $c(G)$ when the rigidity matroid of $G$ is connected and, in particular, show that $c(G)=1$ if and only if $G$ is 3-connected and redundantly rigid. In adition we show that the problem of determining $c(G)$ for an arbitrary rigid graph $G$ can be reduced to the case when $G$ is 3-connected and essentially 4-edge-connected.

• Jajcay, Robert, Indiana State University
  Restricting the Degree/Diameter and Cage Problems to Vertex-Transitive Graphs
  The Degree/Diameter Problem is the problem of finding a graph of the largest possible order from the family of graphs of given degree and diameter. Similarly, the Cage Problem calls for finding the smallest graph of given degree and girth. Great many of the extremal graphs for either of these two interconnected problems are highly symmetric: either vertex-transitive or possessing large automorphism groups with only few orbits. Despite this observation, not much is known about the role of symmetry in extremal graph theory.
  `Based on intuition' alone, one couldeasily find arguments to both support and reject the idea that high symmetry is somehow essential to these problems. On one hand, it is tempting to assume that the high symmetry of the best known graphs is simply due to our preference toward constructions that involve symmetry. Such constructions tend to be easier to organize and limit the corresponding search spaces. As we get closer to the optimal bounds (called the Moore bounds), we will possibly run out of such constructions and will start seeing more complicated graphs with fewer automorphisms. The opposing view can be supported by the idea that as the resulting graphs become more and more `compact', the structural conditions forced on the local neighborhoods will become more global and will make the neighborhoods more alike; leading to vertex-transitivity of the resulting graphs.
  Regardless of the ultimate resolution of the role of symmetry in finding graphs extremal to either of the two problems, it appears obvious that further study of vertex-transitive graphs and their relation to the Degree/Diameter and Cage Problems bears the potential of providing us with more insights in these notoriously hard questions. In our talk, we review some of the latest results obtained in collaboration with Geoff Exoo, Jozef Siran and Martin Macaj.
  
  

• Klambauer, Maximilian University of Toronto
  Equivelar maps on the Klein bottle, and a higher dimensional generalization.
  Given a tessellation of the Euclidean plane and a group of its symmetries generated by two glide reflections, in parallel axes with equal translational components, one can obtain a tessellation on the Klein bottle by identifying points that are in the same orbit under the group action. This idea may be generalized by taking quotients of E^n by subgroups of symmetries which are generated by pairs of glide reflections through parallel hyperplanes. In this talk, we will examine some polytopes obtained this manner.

• Kumar, Abhinav (MIT)
  Rigidity of spherical codes, and kissing numbers in high dimensions.
  One way to improve spherical codes or kissing configurations is to try to create space by continuously deforming them. We say that a code is rigid when there are no nontrivial deformations which do not decrease the minimum distance. We describe a linear programming algorithm to check infinitesimal rigidity for spherical codes, and apply it to the best kissing configurations known in low dimensions. We also describe a related construction which improves the current records for kissing numbers in dimensions 25 through 31. This is joint work with Henry Cohn, Yang Jiao and Salvatore Torquato.
  
  

• Malestein, Justin
  Generic combinatorial rigidity of periodic frameworks
  In this talk, I will discuss a Maxwell-Laman-type theorem for periodic frameworks in the plane due to L. Theran and myself. I will also sketch the main steps in the proof, namely a result on periodic direction networks and the development of some matroidal families of graphs. Several examples of frameworks will be presented.
  

• Mednykh, Alexander Sobolev Institute of Mathematics, Novosibirsk State University, Russia
  Volumes of Polyhedra in Hyperbolic and Spherical Spaces.
  The calculation of volume of polyhedron is very old and difficult problem. Probably, the first result in this direction belongs to Tartaglia (1499–1557) who found the volume of an Euclidean tetrahedron. Nowadays this formula is more known as Caley-Menger determinant. Recently it was shown by I. Kh. Sabitov (1996) that the volume of any Euclidean polyhedron is a root of algebraic equation whose coefficients are functions depending of combinatorial type and lengths of polyhedra. In hyperbolic and spherical spaces the situation is much more complicated. Gauss used the word ”die Dschungel” in relation with volume calculation in non-Euclidean geometry. In spite of this, Janos Boyai, Nicolay Lobachevsky and Ludwig Schlafli obtained very beautiful formulae for non-Euclidean volume of a biorthogonal tetrahedron (orthoscheme). The volume of the Lambert cube and some other polyhedra were calculated by R. Kellerhals (1989), D. A. Derevnin, A. D. Mednykh (2002), A. D. Mednykh, J. Parker, A. Yu. Vesnin (2004), E. Molnar, J. Szirmai (2005) and others. The volume of hyperbolic polyhedra with at least one vertex at infinity was found by E. B. Vinberg (1992). The general formula for volume of tetrahedron remained to be unknown for a long time. A few years ago Y. Choi, H. Kim (1999), J. Murakami, U. Yano (2005) and A. Ushijima (2006) were succeeded in finding of a such formula. D. A. Derevnin, A. D. Mednykh (2005) suggested an elementary integral formula for the volume of hyperbolic tetrahedron. We note that the volume formula for symmetric tetrahedra whose opposite dihedral angles are mutually equal is rather simple. For the first time this phenomena was discovered by Lobachevsky for ideal hyperbolic tetrahedra, which is automatically symmetric. The respective result in quite elegant form was presented by J. Milnor (1982). For general case of symmetric tetrahedron the volume was given by D. A. Derevnin, A. D. Mednykh and M. G. Pashkevich (2004). Surprisedly, but a hundred years ago, in 1906 an essential advance in volume calculation for non-Euclidean tetrahedra was achieved by Italian mathematician Gaetano Sforza. It came to light during discussion of the author with Jose Maria Montesinos-Amilibia at the conference in El Burgo de Osma (Spain), August 2006.The aim of this lecture is to give a survey of the above mentioned results.

• Mitschke, Holger--Institute for Theoretical Physics, University Erlangen-Nuremberg, Germany
  Floppy frameworks as models for auxetic materials
  Microstructures of auxetic materials, i.e. with negative Poisson's ratio, share common structural elements which allow certain types of deformation mechanisms -- reentrant elements or rotations. This motivates the hypothesis that auxetic materials can be identified by considering the microstructure as a pin-joint-and-bar framework and their permitted mechanisms. In order to support this, a broad deformation analysis of archives of mathematical frameworks, namely tilings, and their mechanisms, based on numerical calculations of the infinitesimal floppy modes, has been accomplished. Our study of periodic planar tilings has already been fruitful to design novel auxetic elastic material. We show that elastic cellular structures, built by Ti-6-Al-4V selective electron-beam melting rapid prototyping precisely on the basis of the newly found auxetic framework, possess the same qualitative auxetic deformation behaviour [H.~Mitschke et al., Adv.~Mater.~2011, 23, 2669--2674]. Poisson's ratio is only well-defined for a framework if it has a unique deformation path when a strain is applied. Frameworks where the edge equations allow more degrees of freedom are deformed in our analysis by additionally constraining spatial symmetries which can also be linked to physical constraints such as minimum of angular spring energy. The presented results are for planar frameworks only, but the numerical approach is equally suitable and has the potential to yield conceptually new truly 3D auxetic mechanisms. An open question is whether this model provides a sufficient or even necessary property of auxetic geometries, e.g. whether rigidity is an exclusion criteria for auxetic microstructures.
  

• Mixer, Mark Fields Institute
  Equivelar 4-twistoids II
  In this talk we shall consider 4-polytopes that arise as quotients of the Euclidean tessellation {4,3,4} by fixed point free crystallographic groups of the Euclidean space.

• Offer, Shai Tel-Aviv University
  Symmetric Frameworks with Finite Motions through Assur Graphs at Singular Positions.
  In the talk it will be demonstrated how it is possible to derive frameworks, although are over braced, with a finite motion. This is accomplished by employing the special singularity configuration property that only Assur Graphs possess, causing all the inner joints to have an infinitesimal motion. Using sliders and replications results in symmetric frameworks with finite motions. Demonstrations in 2d will be given in the talk and a conjecture will be presented with the assertion that this method is applied for a special class of 3d Assur Graphs.

• Owen, Megan -Fields Institute
  Geodesics in CAT(0) Cubical Complexes
  A cubical complex is a polyhedral complex in which all the cells are unit cubes. By giving each cube the Euclidean L2 metric, we get a natural metric on the whole complex. These complexes arise in such areas as geometric group theory, reconfigurable systems, and phylogenetics. If a cubical complex is globally non-positively curved or CAT(0), then there is a unique shortest path or geodesic between any two points in the complex.
  We give a bijection between CAT(0) cubical complexes and posets with inconsistent pairs, and show how this can be used to compute shortest paths. When the cube complex represents the space of metric trees, the geodesics can be computed in polynomial time and induce a finer polyhedral subdivision on the space.
  

• Pellicer, Daniel UNAM
  Regular polygonal complexes in space
  A polytonal complex is an arrangement of vertices, edges and faces where the faces do not need to be planar, and more than two of them can meet at the same edge. We say that it is regular whenever its symmetry group acts transitively on its flags. I will show the full classification of the regular polygonal complexes in the Euclidean space.
  

• Petitjean, Michel
  Chirality and Symmetry Measures: some Open Problems
  A general framework to define symmetry and chirality measures is introduced. Then, we present a chirality measure (the chiral index) based on an extension of the Wasserstein metric to spaces of colored mixtures distributions. Connections with Procrustes methods and optimal RMS superpositions are outlined. The properties of the chiral index are presented, including its use as an asymetry coefficient of d-variate distributions. Relations with graph automorphisms groups and applications to chemistry are mentioned. Some maximally dissymetric or maximally chiral figures are presented. Several open problems are listed.
  
  
• Power, Stephen
  Space group and point group symmetry equations for the Borcea-Streinu rigidity matrix of a crystal framework
  To each translationally periodic, discrete, bar-joint framework (crystal framework) $C$ in $\bR^d$ and choice of period vectors there is a finite matrix $R$, obtained by Borcea and Streinu, whose null-space determines the infinitesimal flexes of $C$ that are of affine-periodic type. (These flexes are periodic modulo an affine velocity distribution.) We derive this matrix afresh as a restriction of the infinite rigidity matrix $R(C)$ of $C$ and obtain symmetry equations, such as $\pi_e(g)R = R\pi_v(g)$, for various representations $\pi_e, \pi_v$, of the space group of $C$, associated with edges and vertices. This in turn leads to various symmetry adapted Maxwell-Calladine type formulae.
  
  
• Richter, David
  How to Draw an Edge-Colored Graph
  Define a ``parallel drawing'' of a $d$-edge-colored graph as a representation in the plane where every vertex is represented by a point, every edge is represented by a segment, and the lines supporting the edges sharing a common color are parallel. Call a parallel drawing ``faithful'' if there is a bijection between the edges of the graph and the supporting lines. The purpose of this talk is to discuss the cases of this problem when $d=3$ and $d=4$.
  
  
• Schulte, Egon, Northeastern University
  Two-Orbit Polyhedra in Ordinary Space
  In the past few years, there has been a lot of progress in the classification of highly-symmetric discrete polyhedral structures in Euclidean space by distinguished transitivity properties of the geometric symmetry groups. We discuss recent results about two particularly interesting classes of polyhedra in ordinary 3-space, each described by a "two-flag orbits" condition. First we review the chiral polyhedra, which have two flag orbits under the symmetry group such that adjacent flags are in distinct orbits. They occur in six very large 2-parameter families of infinite polyhedra, three consisting of finite-faced polyhedra and three of helix-faced polyhedra. Second, we describe a complete classification of finite "regular polyhedra of index 2", a joint effort with Anthony Cutler. These polyhedra are combinatorially regular but "fail geometric regularity by a factor of 2"; in other words, the combinatorial automorphism group is flag-transitive but their geometric symmetry group has two flag orbits. There are 32 such polyhedra.
  
  

• Schulze, Bernd
  Counts for predicting symmetric motions in frameworks with applications to protein flexibility
  It is well-understood in biochemistry that the functioning of a protein depends both on having basic stable forms (tertiary structure) and having some residual flexibility supported within that structure. The flexibility and rigidity of proteins can be analyzed via the well developed theory of generic rigidity of body-bar frameworks. In particular, there exist fast combinatorial algorithms (such as the pebble game) for determining the rigidity of a body-bar framework.
  Recent theoretical work on rigidity of frameworks has modified this analysis to include the basic symmetry of some structures and predict motions which preserve this symmetry. In particular, a framework in 3-space which counts to be combinatorially minimally rigid in generic realizations (i.e., the underlying graph satisfies the count $e=6v-6$) becomes flexible when realized with 2-fold rotational symmetry. Protein dimers, formed by two copies of a protein are a good case study for the possible impact of this added flexibility, due to 2-fold rotational symmetry, as they generally self-assemble with a 2-fold rotational axis, for reasons of minimal energy. What is the significance of this for the behavior of dimers, such as tryptophan repressor?We will explore this case study and describe some symmetry-adapted pebble game algorithms.
  Our symmetric counting methods also yield interesting results for other point group symmetries which are frequently found in proteins. For example, a 3-dimensional framework which counts to be over-braced by two ($e=6v-4$) has a finite symmetry-preserving flex when realized generically with $D_2$ symmetry, where $D_2$ is the point group generated by two half-turns about perpendicular axes.
  This is joint work with Adnan Sljoka and Walter Whiteley.
  

• Servatius, Brigitte
  Point/Line Configurations and their Realizability
  A generically rigid body-pin structure, by the Molecular Theorem (2010) remains rigid even if the bodies are replaced by straight lines.Steinitz' Theorem (1910) says that a point line configuration with three points on every line and three lines through every point may be realized in the plane with at most one curved line.
  We want to point out some problems with Steinitz' Theorem with respect to realizations requiring points
  as well as lines to be distinct and to examine the relationships between these two theorems.
  

• Streinu, Ileana
  Periodic body-and-bar frameworks
  Abstractions of crystalline materials known as periodic body-and-bar frameworks are made of rigid bodies connected by fixed-length bars and subject to the action of a group of translations. In this paper, we give a Maxwell-Laman characterization for generic minimally rigid periodic body-and-bar frameworks. As a consequence we obtain efficient polynomial time algorithms for their recognition based on matroid partition and pebble games.
  This is joint work with Ciprian Borcea and Shin-ichi Tanigawa.
  
  

• Theran, Louis
  Generic rigidity of crystallographic frameworks
  Last year, Justin Malestein and I proved a Maxwell-Laman-type theorem for periodic frameworks in the plane. I'll talk about our newer Laman-type results that apply to a larger class of crystallographic groups. Along the way, some new matroidal families of graphs will come up, as well as related results on symmetric direction networks.
  

• Thorpe,M. F. , Arizona State University
  Rigidity Percolation
  Rigidity can percolate across large structures to render the whole structure rigid. This is obviously important in the design of buildings and in also important in molecular structures and frameworks.
  There is a phase transition associated with rigidity percolation which occurs as the number of cross braces is increased as a system tends to the thermodynamic limit with an infinite number of sites and edges. The earliest example studied was via the pebble game algorithm on a triangular network, where each edge is present independently with probability p.
  Exact solutions are known in two cases: on a Cayley tree, where rigidity percolates out from a long rigid busbar and on hierarchical lattices. In the first case, the solution is obtained by using atransfer matrix, and the transition is first order (collapse like a house of cards), while in the second case the solution is obtained via renormalization group, and the transition is second order or continuous.

Back to top

October 24-27, 2011
Workshop on Symmetry in Graphs, Maps and Polytopes

• Apel, Susanne
  G-Cycles - Powerful and Surprisingly Simple Objects
  The aim in this talk is to introduce the concept of G-cycles. They arise as a natural concept when analyzing a special kind of automatic theorem provers for real projective incidence theorems: the binomial proving method which uses determinants as first class citizen objects. The basic idea of Jürgen Richter-Gebert was analyzing this proving method by creating a diagrammatic representatin of it. In the first place this leads to a manifold composed of triangles carrying a  Ceva or Menelaus structure and constituting as a whole a proof of the theorem. The glued triangles  constitute a surface whose topological structure is investigated. However,  in the second place, some of the constructions made in the process seem not optimal. This leads to the concept of G-Cycles as building blocks in the proving method (instead of Ceva and Menelaus triangles). They can also be interpreted as theorems about ratios of length in affine geometry and thereby generalizing results from Grünbaum and Shepard. So G-Cycles form generalizations of the Theorems of Ceva and Menelaus. Some other special cases of G-Cycles are also already known in the literature. The presentation will touch the topics incidence theorems and automatic proofs of those as well as bracket algebra, topology and combinatorics.
  
  
• Berman, Leah
  A geometric construction for new highly incident configurations
  A geometric $k$-configuration is a collection of points and straight lines in the Euclidean plane so that every point lies on $k$ lines and every line passes through $k$ points. In this talk, we will describe a new construction for constructing $k$-configurations for any $k \geq 3$. This construction method uses only straightedge-and-compass techniques, given an initial regular $m$-gon of points, to construct a $k$-configuration with $m(2^{k-2})$ points and lines. It includes the smallest 7-configuration (which is still rather small), as well as producing new infinite families of 5- and 6-configurations.
  
  
• Brooksbank, Peter
  Classical groups acting on polytopes
  
  
  
• Burgiel, Heidi
  A Family of Unsatisfying Graphs
  
  
• Cara, Philippe --Vrije Universietit Brussel
  Large Group actions applied to virus architecture
  (Joint work with A. Devillers and R. Twarock)
  It has been known for a long time that most viruses exhibit icosahedral symmetry. In 1962 Caspar and Klug\cite{CaKl62} developed a theory describing the structure of the protein containers that encapsulate and hence protect the viral genome. The theory's main ingredients are triangulations of the faces of an icosahedron. The location of (centres of mass of) structural proteins is deduced from such triangulations.
  More recently Keef and Twarock\cite{KeTw09} extended the Caspar--Klug theory using more general tilings of the icosahedron and superpositions of several tilings. Now more structural details can be explained as well as the organisation of the viral genome inside the icosahedral capsid. In this theory many mathematical objects like quasicrystals, groups, lattices, etc. interact to provide more insight.
  We clarify these interactions and provide a more uniform mathematical framwork based on group actions.
  \begin{thebibliography}{99}
  \bibitem{CaKl62} Caspar D.L.D. and Klug A.,
  \emph{Physical principles in the construction of regular viruses}, Cold Spring Harbor Symp. 27:1--24, 1962.
  \bibitem{KeTw09} Keef, T. and Twarock, R.,
  \emph{Affine extensions of the icosahedral group with applications to the three-dimensional organisation of simple viruses},
  J. Math. Biol. 59: 287-313, 2009.
  \end{thebibliography}
  
  

• Conder, Marston
  The ubiquity of alternating groups (as automorphism groups of symmetric structures)
  There are several contexts in which finite alternating groups occur as the automorphism group (or orientation-preserving automorphism group) of a discrete structure with maximum possible symmetry under certain constraints. In fact, it frequently happens that all but finitely many $A_n$ appear in the given context, and sometimes all but finitely many symmetric groups $S_n$ occur as well (or instead). % Examples include {\em Hurwitz surfaces\/} (compact Riemann surfaces of genus $g > 1$ with $84(g-1)$ conformal automorphisms), or equivalently, {\em regular maps\/} of type $\{3,7\}$, and also {\em $5$-arc-transitive cubic graphs}, {\em $7$-arc-transitive $4$-valent graphs}, and {\em hyperbolic $3$-manifolds of largest possible symmetry-to-volume ratio}. % I will explain some of these, as well as a very recent one ({\em locally 9-arc-transitive bipartite graphs}), and the possibility that for every $r \ge 3$, all but finitely many $A_n$ and $S_n$ occur as the automorphism group of a {\em chiral polytope\/} of rank $r$.

• Cunningham, Gabe
  Constructing self-dual chiral polytopes
  Abstract: A polytope is chiral if its automorphism group has two orbits on the flags, such that adjacent flags belong to distinct orbits. The mixing operation for chiral polytopes constructs the minimal common cover of two given polytopes. To construct self-dual chiral polytopes, we mix a chiral polytope with its dual or with the mirror image of its dual. This always yields something which is self-dual, but it may not be chiral or polytopal. However, there are several simple criteria that can, in many cases, settle the question of chirality and polytopality.
  
  

• Ehrenborg, Richard
  Euler flag enumeration of Whitney stratified spaces
  The flag vector contains all the face incidence data of a polytope, and in the poset setting, the chain enumerative data. It is a classical result due to Bayer and Klapper that for face lattices of polytopes, and more generally, Eulerian graded posets, the flag vector can be written as a cd-index, a non-commutative polynomial which removes all the linear redundancies among the flag vector entries. This result holds for regular CW complexes. We relax the regularity conditions to show the cd-index exists for manifolds whose boundary has a Whitney stratification. The setting of Whitney stratifications allows us to give shorter proofs of identities involving the cd-index and opens inequality questions.
  This is joint work with Mark Goresky and Margaret Readdy.

• Herman, Allen
  The Schur Indices of irreducible characters of the groups of abstract regular polytopes
  In 2001, McMullen and Monson noted an example of an irreducible character $\chi$ of the automorphism group $\Gamma$ of the abstract regular polytope $\{5,5\}_5$ with Frobenius-Schur indicator $FS(\chi) = 0$, and asked whether or not there could exist examples with $FS(\chi) = -1$. In algebraic terms, this is asking if there is a simple component of the real group algebra $\mathbb{R}\Gamma$ that is a matrix ring over the real quaternion algebra. 10 years later, the question remains open. In my talk I will survey what is known about this problem, and give an overview of what is known about the analogous problems for Weyl groups, finite Coxeter groups, and finite unitary reflection groups.

• Helfand, Ilanit
  Constructions of Polytopes with Preassigned Automorphism Group and Number of Flag Orbits
  It is known that given a string C-group it is possible to construct an abstract regular polytope, P, whose group of automorphisms is isomorphic to that string C-group. This talk will explore the conditions under which it is possible to construct an abstract polytope whose automorphism group is isomorphic to a given string C-group, and which has a preassigned number of flag orbits, greater than one. We will also discuss some of the properties of a collection of polytopes which fulfill these parameters.

• Hubard, Isabel UNAM
  Colourful polytopes and graphs
  In this talk we shall construct abstract polytopes from n-regular graphs with chromatic index n. In particular we'll see some Cayley graphs, as well as the flag-graph of any polytope, as 1-skeletons of abstract polytopes.

• Johnson, Norman W.
  Basic System of Integers
  A subset of one of the algebraic systems C, H, or O is a basic system of integers if:
  (1) the trace and the norm of each element are rational integers;
  (2) the elements form a discrete subring of C, H, or O with the units forming a finite multiplicative group or loop; and
  (3) when C, H, or O is taken as a two-, four-, or eight- dimensional vector space over R, the elements are the points of a two-, four-, or eight-dimensional lattice spanned by the units. The ring of rational integers can be regarded as a one-dimensional basic system. The rings of Gaussian and Eisenstein complex integers are well known. A. I. Weiss and I proved that there are exactly three basic systems of integral quaternions. Here I show that there are just four such systems of octonions. As lattice points, the integers of each basic system are the vertices of some regular or uniform Euclidean honeycomb of dimension 1, 2, 4, or 8.
  

• Jones, Gareth
  Beauville surfaces and groups
  A Beauville surface is a complex surface (hence a 4-dimensional real manifold) constructed as the quotient of a cartesian product of two regular dessins (i.e. orientably regular hypermaps) of genus at least 2 by a finite group acting freely on this product. Although they are of considerable interest to algebraic geometers (e.g. for their rigidity properties), the construction and investigation of these surfaces are essentially group-theoretic and combinatorial activities. I shall survey recent results on which groups can act in the above way, and which groups can arise as the automorphism groups of Beauville surfaces. Much of this is joint work with Yolanda Fuertes, Gabino Gonzalez-Diez and David Torres-Teigell.
  

• Karab\'a\v s, J\'an
  Classification of orientable edge-transitive maps
  An orientable map is edge-transitive if and only if its medial is a vertex-transitive map. Hence, using the techniques for the classification and construction of vertex transitive maps we obtain the classification of edge-transitive maps on orientable surfaces.
  The orientation-preserving automorphism group of a medial map is of index at most two in the automorphism group of a medial map.
  Hence we know, that the quotient of a medial map has at most two vertices. The lifting technique can be used for the construction.
  Orientation-preserving automorphisms of an edge-transitive map are \emph{face colour-preserving}, i. e. they cannot act as a duality in the medial map. The number of possible quotient maps significantly decreases, in particular there are just six quotient maps to consider. In the case of two-vertex quotient, $\bar{M}$, of a medial map, $M$, the automorphism group of the respective (medial) map must contain an automorphism $\phi$ such that $\phi$ projects onto an automorphism of the quotient, transposing the two vertices of $\bar{M}$ and preserving the face-colouring of $\bar{M}$. These conditions gives to rise to \emph{seven} infinite families of edge-transitive maps. Using techniques of voltage assignments we can reconstruct all edge-transitive maps of given genus or up to given number of edges.

• Kutnar, Klavdija
  Cubic Cayley graphs and snarks
  In this talk I will discuss the well-known conjecture that there are no snarks amongst Cayley graphs.
  I will present an innovative approach in solving this conjecture combining the theory of Cayley maps and the existence of independent set of vertices whose complement induces a forest regularly on the set of arcs with cyclic vertex stabilizer, together with some partial results obtained thus far.
  This is a joint work with Ademir Hujdurovic and Dragan Marusic.

• Leemans, Dimitri
  Polytopes of high rank arising from almost simple groups
  In this talk, we will present results obtained the last few years on abstract regular polytopes constructed for some families of almost simple groups.

• Leopold, Undine , Northeastern University
  Polyhedral Realizations & Non-Realizability for Vertex-Minimal Triangulations of Closed Surfaces
  A polyhedral realization of a triangulated 2-manifold is a simplex-wise linear embedding into R^3 in the orientable case, or a simplex-wise linear immersion in the non-orientable case. It is an open question how many vertices are minimally needed for a realizable triangulation of any particular 2-manifold. Progress has been made in recent years with the aid of computer programs, but few results are known in the non-orientable case. As such, a large part of the talk will focus on geometric and topological constraints preventing realizability in the non-orientable case. It is possible to prove, for example, that neither of the two minimal 9-vertex-triangulations for the projective plane with two handles is polyhedrally realizable. In an attempt to narrow the bounds from both sides, the speaker will also present results concerning realizations with certain symmetries and few vertices which have been obtained by an adapted computer heuristic. Combining these approaches lead to new minimality results. For the projective plane with two handles 10 vertices suffice, which makes the corresponding realizations vertex-minimal. This work was done as part of the speaker's undergraduate thesis advised by Ulrich Brehm at TU Dresden, Germany.
  

• Malnic, Aleksander
  On the split structure of lifted groups
  

• Marusic, Dragan
  On some open problems in group actions on graphs
  I will discuss some of my favorite problems dealing with graphs admitting transitive group actions.
  In particular, I will present partial results about
  - the interplay between semiregular automorphisms and imprimitivity block systems in graphs; and
  - strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree 2p.
  

• Macaj, Martin
  Nonorientable Regular Maps and Residual Finiteness of Triangle Groups (slides)
  It is well known that for any given hyperbolic pair (k ,m) there exist infinitely many regular maps of valence k and face lengthm on an orientable surface, with automorphism group isomorphic to a linear fractional group. A nonorientable analogue of this result was known to be true for all pairs (k ,m) as above with at least one even entry. In this paper we establish the existence of such regular maps on nonorientable surfaces for all hyperbolic pairs. The material presented is a result of a joint work with Gareth A.
  Jones and Jozef irn.

• Mednykh, Alexander Sobolev Institute of Mathematics, Novosibirsk, Russia
  Enumeration of Coverings, Maps and Hypermaps
  In this lecture we present a new method to count finite sheeted coverings of manifolds with a finitely generated fundamental group. The details can be found in [1] and [2]. We apply it to count branched and unbranched coverings over compact surfaces ([2],\,[3]).
  As a consequence, we suggest a new approach to count maps on surfaces up to orientation preserving homeomorphism. The further development of the method gives us a possibility to count sensed maps and hypermaps by number of edges on a closed orientable surface ([3],\,[4]).
  REFERENCES
  1. A. Mednykh, R. Nedela: Enumeration of unrooted maps of a given genus. \textit{J. Comb. Theory, Ser. B } 96(5): 706-729 (2006).
  2. A. Mednykh: Counting conjugacy classes of subgroups in a finitely generated group.\textit{ Journal of Algebra} 320: 2209-2217 (2008).
  3. A. Breda d'Azevedo, A. Mednykh, R. Nedela: Enumeration of maps regardless of genus:
  Geometric approach. \textit{Discrete Mathematics } 310(6-7): 1184-1203 (2010).
  4. A. Mednykh, R. Nedela: Enumeration of unrooted hypermaps of a given genus. \textit{Discrete Mathematics} 310(3): 518-526 (2010).

• Mohar, Bojan Simon Fraser University
  Large clique minors in vertex transitive graphs

An important (yet unpublished) theorem of Babai states that there exists a function $f: N \to N$ so that every finite vertex
transitive graph without $K_n$ as a minor is either $(f(n),f(n))$-ring-like or is a vertex transitive map on the torus. Applying a recent theorem of the authors about separations in vertex transitive graphs, we obtain a relatively short proof of Babai's theorem with explicit values for $f(n)$. The starting point is that graphs of bounded tree-width have small separations and this leads to a ring-like structure. Otherwise, there is a large grid minor. This yields a $K_n$ minor unless the graph is locally planar, and we show that this gives rise to a vertex transitive map. Finally, a ball packing argument is used to prove that the combinatorial curvature of this map is zero; otherwise there is a dense graph contained as a minor, and this yields $K_n$ minor. The last step is to eliminate the Klein bottle, ending up with a toroidal map.
This talk is a joint work with Matt DeVos.

• Nedela, Roman
  Vertex transitive and edge transitive polytopes and 2-dimensional orbifolds
  

• Piggott, Adam
  The symetries of McCullough-Miller Space
  Given a group W and a fixed decomposition of W as a free product, the symmetric outer automorphism group of W consists of those outer automorphisms of W which first permute the free factors, and then conjugate each free factor. McCullough-Miller's
  space X=X(W) is a simplicial complex on which the symmetric outer automorphism group of W acts.
  We will discuss the question of just how well X models the full outer automorphism group of W. In particular, we consider circumstances under which Aut(X) is precisely Out(W).

• Schulte, Egon , Northeastern University
  Few-Orbit Polytopes
  Among abstract or geometric polytopes, the regular polytopes stand out as those with maximal symmetry---their combinatorial automorphism group or geometric symmetry group has just one orbit on the flags. We discuss various classes of polytopes with few flag orbits under the respective group. Important classes include chiral polytopes, and more generally two-orbit polytopes, as well as "alternating" semiregular polytopes. We report about joint work with Antonio Breda and Gareth Jones, as well as with, separately, Isabel Hubard and Barry Monson.

• Siran, Jozef (Open University and Slovak University of Technology)
  External symmetries of regular and orientably regular maps
  A map on a surface (orientable or not) is said to be regular if its automorphism group is regular on flags, and a map on an orientable surface is orientably regular if its orientation preserving automorphism group is regular on darts. An (orientably) regular map may admit `external symmetries', that is, self-dualities and exponents (also known as hole operators) that do not preserve the map like automorphisms do, but still produce an isomorphic copy of the map. Such symmetries generate a group which we call the external symmetry group of a map. In the talk we will survey various ways of constructing regular and orientably regular maps with `small' and `large' external symmetry groups and address the question about structure of these groups.
  
  

• Skoviera, Martin Comenius University, Bratislava
  Regular maps with nilpotent automorphism groups

According to a folklore result, every regular map on an orientable surface with abelian automorphism group belongs to one of three infinite families of maps with one or two vertices. Here we deal with regular maps whose automorphism group is nilpotent. We show that each such map decomposes into a direct product of two maps H x K, where Aut(H) is a 2-group and K is a map with a single vertex and an odd number of semiedges. Many important properties of nilpotent maps follow from this decomposition. We show, for example, that apart from two well-defined classes of maps on at most two vertices and their duals, every nilpotent regular map has both its valency and face-size divisible by 4. We give a complete classification of nilpotent regular maps of nilpotency class 2 and 3, and prove that for every positive integer c there are only finitely many simple regular maps whose automorphism group is nilpotent of class c. This is a joint work with Y. F. Ban, S. F. Du, Y. Liu, A. Malni\v c, and R. Nedela.

• Tucker, Thomas
  Map Gaps
  Call the non-negative integer $g $ a {\em gap} for a certain type of symmetric map if there is no surface of genus $g$ containing a map of that type. This talk will discuss gap phenomena in a wide variety of contexts. For example, chiral regular maps and nondegenerate regular maps (no primal or dual multiple edges) both have gaps at $g=p+1$, for $p>12$ prime and $p \not\equiv 1$ mod $6,8$ or $10$, by recent work of Conder, \v Sir\`a\v n, and Tucker. Computer lists for some of the Graver-Watkins types of edge-transitive maps have gaps for low genus, although it is not known whether any type other than chiral regular maps have infinitely many gaps. There are also gap questions for groups acting on surfaces. For the strong symmetric genus $\sigma^o(G)$, there are no gaps, but the question is open for the symmetric genus $\sigma(G)$. One can fix a group $G$ and ask for all $g$ such that $G$ acts (faithfully) on the surface of genus $g$. By Kulkarni's Theorem one can determine all but finitely many such $g$, but even for cyclic groups those finitely many can be impossible to determine (for number theoretic reasons). Similar questions for non-orientable surfaces will also be discussed.
  

• Weiss, Richard
  Buildings and s-transitive graphs
  Abstract: The notion of an s-transitive graph was introduced by William Tutte, who showed 65 years ago that finite s-transitive trivalent graphs exist only for s at most 5. In this talk we will give a survey of results on s-transitive graphs and the connection between s-transitive graphs and the theory of buildings.
  

• Williams, Gordon
  On the Minimal Regular Covers of the Polyhedral Prisms and Anti-Prisms
  Abstract polytopes are partially ordered sets that mimic many of the combinatorial properties of the face lattice of a polytope. The most symmetric class of these objects are called regular abstract polytopes; these are well understood because of their correspondence to a special class of groups generated by involutions known as string C-groups. Less well understood are the abstract polytopes that lack this high degree of symmetry.
  In 1999, Michael Hartley developed a theoretical framework for representing any abstract poly- tope as a quotient of some regular abstract polytope. Since then, the investigation of the structure of these quotient representations has been an active area of inquiry. In many instances it is possi- ble to identify a unique minimal regular cover for a given polytope (though not all polytopes have minimal covers!). In the current work we provide the first explicit descriptions of minimal regular covers for an infinite family of polytopes, namely, the convex prisms and anti-prisms. This talk will describe some of the tools developed to tackle this problem and discuss the representations, as well as present some related open problems in the field.
  This talk incorporates joint work with Michael Hartley, Barry Monson and Daniel Pellicer.

• Back to top