
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 1114, 2011
Workshop on Rigidity
Alfakih, Abdo Y.
On the Universal rigidity of bar frameworks in general position
A bar framework G(p) in rdimensional 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 noncongruent 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 semidefinite stress
matrix of rank nr1. 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 ballpolyhedra in Euclidean 3space
A ballpolyhedron is the intersection with
nonempty interior of finitely many (closed) unit balls in Euclidean
3space. One can represent the boundary of a ballpolyhedron as
the union of vertices, edges, and faces defined in a rather natural
way. A ballpolyhedron is called a simple ballpolyhedron if at
every vertex exactly three edges meet. Moreover, a ballpolyhedron
is called a standard ballpolyhedron if its vertexedgeface structure
is a lattice (with respect to containment). To each edge of a
ballpolyhedron one can assign an inner dihedral angle and say
that the given ballpolyhedron is rigid with respect to its inner
dihedral angles if the vertexedgeface structure of the ballpolyhedron
and its inner dihedral angles determine the ballpolyhedron up
to congruence locally. The main result of this talk is a Cauchytype
rigidity theorem for ballpolyhedra stating that a simple ballpolyhedron
is rigid with respect to its inner dihedral angles if and only
if it is a standard ballpolyhedron. 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 ddimensional generic rigidity
matroid only if (a) the number of edges does not exceed dV 
{d+1 choose 2}, and (b)this holds for every induced subgraph.
Such graphs are called Sparse orMaxwellindependent in ddimensions.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, Maxwellindependent 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 Maxwellindependent 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 barandjoint frameworks,
tensegrities, packings, barandbody frameworks, and bodyhindge,
for example. This is a background and preview of many of the talks
to come.
Crapo, Henry
Isostatic Graphs and Semisimplicial
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 semisimplicial 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 semisimplicial 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 semisimplicial 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 3v6 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 nonshellable 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 semisimplicial
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 semisimplicial 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
3rigid {\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 FourColor 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 Ddimensional
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 NPhard.
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 3connected
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 twodimensional 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 twodimensional 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.
LeeSt. John, Audrey Mount Holyoke
College
Bodyandcad rigidity theory
Classical rigidity theory focuses on distance
constraints between points. For barandjoint rigidity, planar
properties are wellunderstood and have a combinatorial characterization
via Laman's Theorem; higher dimensions remain a conspicuously
open area. For bodyandbar 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 bodyandcad
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 constraintbased
CAD software (e.g., "mates" in a SolidWorks "assembly").
Initial foundations for bodyandcad rigidity theory indicate
its combinatorial properties lie somewhere between the wellunderstood
world of bodyandbar rigidity and the open area of 3D barandjoint
rigidity. In this talk, we present recent work on combinatorial
bodyandcad 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 vertextovertex 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 nonEuclidean versions of
this theorem can be found, for example, in the book by E.~B. Vinberg,
Geometry II: Spaces of Constant Curvature, SpringerVerlag, 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 nonEuclidean
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 sdistance set if the set of distances between any two distinct
points of X has size s. The main problem for sdistance sets is
to determine the maximum cardinality of sdistance sets for fixed
s and M. Let us denote by A(M, s) the maximum cardinality of sdistance
sets in M. In this talk, we are going to discuss upper bounds
for A(M, s), where M is a compact twopoint 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
twodistance 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. 14651474; O.R. Musin and H. Nozaki, Bounds
on three and higherdistance sets // European Journal of Combinatorics
32 (2011) 11821190.
Nixon, Tony
Rigidity, Circuits and Global Rigidity on the Cylinder
We discuss barjoint frameworks in 3dimensions
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 $2V2$ 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 $2V1$ edges such that all proper subgraphs have at most
$2V'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 ddimensional
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
ndimensional infinite periodic framework by considering such
a framework as a graph embedded on an ndimensional torus. In
this talk we describe a complete characterization of generic rigidity
for 2dimensional 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 dedges directed out of every vertex are the 'ddyad' and
a cyclic of ddyads 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, TelAviv University, Israel.
Omer O., 2011, Employing Assur Tensegrity Structures Methods for
Simulating a Caterpillar Locomotion, M.Sc thesis, TelAviv 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. 10911104
Servatius B., Shai O. and Whiteley W.,
2010b, Geometric Properties of Assur Graphs, European Journal
of Combinatorics, Vol. 31, No. 4, May, pp. 11051120.
Shai O., 2008, Canonical Forms for Multidimensional
Isostatic Frameworks, Determinate trusses, Linkages and Rtensegrity
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 2831, 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 1degreeoffreedom linkages
We study the 2D configuration spaces of
1degreeoffreedom (dof)
linkages obtained by dropping a bar from a triangledecomposable
linkage. The latter linkages are minimally rigid and wellstudied,
for example, in geometric constraint solving for CAD, because
they are
quadraticradical solvable (QRS also called rulerandcompass
constructible): in other words, the point coordinates that realize
rational bar lengths belong to an extension field over the rationals
obtained by nested squareroots (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 1dof linkage, we use the set of realizable distancevalues
for an independent nonedge 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 1dof linkage G on any nonedge f such
that G U f is triangledecomposable; 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 1dof triangle decomposable
linkages. In addition, we give an algorithmic characterization
of 1dof, 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 1dof triangledecomposable
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
1dof, 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 blowup
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
fourbar mechanisms. Based on the known examples, there is a conjecture
that the reducibility of this composition, i.e., a 44correspondance,
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, Shinichi
Rootedtree 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 ErdosRenyi 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 linearsized 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
1721, 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 RichterGebert who is not able to be present
himself. Starting from a discussion with Jim Blinn which was
related to invariant theoretic aspects of the CayleyBacharach
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 barandjoint 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 nonorientable 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 nonorientable surfaces?
Answers to questions like these may be found by investigating
properties of finite quotients of Fuchsian and nonEuclidean
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 sarctransitive
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, rigidbody 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 grouptheoretical
iceberg of potentially useful information.
This contribution discusses some symmetryextended 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 4twistoids, part I
In this talk we shall consider 4polytopes
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 2dimensional 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 noncongruent 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 3connected 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 3connected and essentially 4edgeconnected.
 Jajcay, Robert, Indiana State University
Restricting the Degree/Diameter
and Cage Problems to VertexTransitive 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 vertextransitive 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 vertextransitivity
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 vertextransitive 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 MaxwellLamantype 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 CaleyMenger
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 nonEuclidean geometry. In spite of this, Janos Boyai, Nicolay
Lobachevsky and Ludwig Schlafli obtained very beautiful formulae
for nonEuclidean 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 nonEuclidean tetrahedra was achieved
by Italian mathematician Gaetano Sforza. It came to light during
discussion of the author with Jose Maria MontesinosAmilibia
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, HolgerInstitute for
Theoretical Physics, University ErlangenNuremberg, 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 pinjointandbar
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 Ti6Al4V selective electronbeam
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, 26692674]. Poisson's ratio is only welldefined 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 4twistoids II
In this talk we shall consider 4polytopes that arise as quotients
of the Euclidean tessellation {4,3,4} by fixed point free crystallographic
groups of the Euclidean space.
 Offer, Shai
TelAviv 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
nonpositively 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 dvariate 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 BorceaStreinu rigidity matrix of a
crystal framework
To each translationally periodic, discrete, barjoint framework
(crystal framework) $C$ in $\bR^d$ and choice of period vectors
there is a finite matrix $R$, obtained by Borcea and Streinu,
whose nullspace determines the infinitesimal flexes of $C$ that
are of affineperiodic 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 MaxwellCalladine type formulae.
 Richter, David
How to Draw an EdgeColored Graph
Define a ``parallel drawing'' of a $d$edgecolored 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
TwoOrbit Polyhedra in Ordinary Space
In the past few years, there
has been a lot of progress in the classification of highlysymmetric
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 3space, each described by a "twoflag 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 2parameter
families of infinite polyhedra, three consisting of finitefaced
polyhedra and three of helixfaced 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 flagtransitive 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 wellunderstood 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 bodybar frameworks. In particular, there exist fast combinatorial
algorithms (such as the pebble game) for determining the rigidity
of a bodybar 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 3space which counts
to be combinatorially minimally rigid in generic realizations
(i.e., the underlying graph satisfies the count $e=6v6$) becomes
flexible when realized with 2fold 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 2fold
rotational symmetry, as they generally selfassemble with a
2fold 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 symmetryadapted 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 3dimensional
framework which counts to be overbraced by two ($e=6v4$) has
a finite symmetrypreserving flex when realized generically
with $D_2$ symmetry, where $D_2$ is the point group generated
by two halfturns about perpendicular axes.
This is joint work with Adnan Sljoka
and Walter Whiteley.

Servatius, Brigitte
Point/Line Configurations and their Realizability
A generically rigid bodypin 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 bodyandbar frameworks
Abstractions of crystalline materials known as periodic bodyandbar
frameworks are made of rigid bodies connected by fixedlength
bars and subject to the action of a group of translations. In
this paper, we give a MaxwellLaman characterization for generic
minimally rigid periodic bodyandbar 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 Shinichi Tanigawa.

Theran, Louis
Generic rigidity of crystallographic frameworks
Last year, Justin Malestein and I proved a MaxwellLamantype
theorem for periodic frameworks in the plane. I'll talk about
our newer Lamantype 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 2427, 2011
Workshop on Symmetry in Graphs, Maps and Polytopes
 Apel, Susanne
GCycles  Powerful and Surprisingly Simple Objects
The aim in this talk is to introduce the concept of Gcycles.
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 RichterGebert
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 GCycles
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 GCycles
form generalizations of the Theorems of Ceva and Menelaus. Some
other special cases of GCycles 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 straightedgeandcompass
techniques, given an initial regular $m$gon of points, to construct
a $k$configuration with $m(2^{k2})$ points and lines. It includes
the smallest 7configuration (which is still rather small), as
well as producing new infinite families of 5 and 6configurations.
 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 CasparKlug
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:124, 1962.
\bibitem{KeTw09} Keef, T. and Twarock, R.,
\emph{Affine extensions of the icosahedral group with applications
to the threedimensional organisation of simple viruses},
J. Math. Biol. 59: 287313, 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 orientationpreserving 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(g1)$
conformal automorphisms), or equivalently, {\em regular maps\/}
of type $\{3,7\}$, and also {\em $5$arctransitive cubic graphs},
{\em $7$arctransitive $4$valent graphs}, and {\em hyperbolic
$3$manifolds of largest possible symmetrytovolume ratio}.
% I will explain some of these, as well as a very recent one
({\em locally 9arctransitive 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 selfdual 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
selfdual chiral polytopes, we mix a chiral polytope with its
dual or with the mirror image of its dual. This always yields
something which is selfdual, 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 cdindex,
a noncommutative 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
cdindex exists for manifolds whose boundary has a Whitney stratification.
The setting of Whitney stratifications allows us to give shorter
proofs of identities involving the cdindex 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 FrobeniusSchur 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 Cgroup it is possible to construct
an abstract regular polytope, P, whose group of automorphisms
is isomorphic to that string Cgroup. 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
Cgroup, 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 nregular
graphs with chromatic index n. In particular we'll see some
Cayley graphs, as well as the flaggraph of any polytope, as
1skeletons 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 eightdimensional lattice spanned by the units. The
ring of rational integers can be regarded as a onedimensional
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 4dimensional
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 grouptheoretic 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 GonzalezDiez and David TorresTeigell.

Karab\'a\v s, J\'an
Classification of orientable
edgetransitive maps
An orientable map is edgetransitive if and only if its
medial is a vertextransitive map. Hence, using the techniques
for the classification and construction of vertex transitive
maps we obtain the classification of edgetransitive maps on
orientable surfaces.
The orientationpreserving 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.
Orientationpreserving automorphisms of an edgetransitive map
are \emph{face colourpreserving}, 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 twovertex 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
facecolouring of $\bar{M}$. These conditions gives to rise
to \emph{seven} infinite families of edgetransitive maps. Using
techniques of voltage assignments we can reconstruct all edgetransitive
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 wellknown 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 & NonRealizability for VertexMinimal
Triangulations of Closed Surfaces
A polyhedral realization of a triangulated 2manifold is a simplexwise
linear embedding into R^3 in the orientable case, or a simplexwise
linear immersion in the nonorientable case. It is an open question
how many vertices are minimally needed for a realizable triangulation
of any particular 2manifold. Progress has been made in recent
years with the aid of computer programs, but few results are
known in the nonorientable case. As such, a large part of the
talk will focus on geometric and topological constraints preventing
realizability in the nonorientable case. It is possible to
prove, for example, that neither of the two minimal 9vertextriangulations
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 vertexminimal.
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 CFSGfree 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): 706729
(2006).
2. A. Mednykh: Counting conjugacy classes of subgroups in a
finitely generated group.\textit{ Journal of Algebra} 320: 22092217
(2008).
3. A. Breda d'Azevedo, A. Mednykh, R. Nedela: Enumeration of
maps regardless of genus:
Geometric approach. \textit{Discrete Mathematics } 310(67):
11841203 (2010).
4. A. Mednykh, R. Nedela: Enumeration of unrooted hypermaps
of a given genus. \textit{Discrete Mathematics} 310(3): 518526
(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))$ringlike
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 treewidth have small separations and this leads to
a ringlike 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 2dimensional
orbifolds

Piggott, Adam
The symetries of McCulloughMiller 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. McCulloughMiller'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
FewOrbit Polytopes
Among abstract or geometric
polytopes, the regular polytopes stand out as those with maximal
symmetrytheir 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 twoorbit 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, selfdualities
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 2group 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 welldefined classes of
maps on at most two vertices and their duals, every nilpotent
regular map has both its valency and facesize 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 nonnegative 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 GraverWatkins types of edgetransitive
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 nonorientable
surfaces will also be discussed.

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

Williams, Gordon
On the Minimal Regular Covers of the Polyhedral Prisms
and AntiPrisms
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 Cgroups. 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 antiprisms.
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

