Réunion d'hiver SMC 2011
Delta Chelsea Hotel, Toronto, 10 - 12 décembre 2011

Géométrie discrete
Org: Elissa Ross et Walter Whiteley (York)

ANTHONY NIXON, Fields Institute, Toronto
Frameworks with Mixed Dimensional Constraints  [PDF]

In this talk I will introduce the idea of bar-joint frameworks in 3-dimensions where the joints are partitioned into two sets, one supported on a fixed 2-dimensional surface and the other on a fixed 1-dimensional surface. I will describe how the basics of rigidity theory adapt to these settings; in particular, relevant classes of graphs are shown to be 2-coloured graphs with various sparsity counts for the whole graph and for each monochromatic subgraph. I will focus on two particular examples of this idea: a line at a 45 degree angle to a plane and a line through the (translational) axis of a cylinder. I will discuss progress towards, and barriers to, finding combinatorial characterisations, or Laman-type theorems, for when such frameworks are rigid.

MEGAN OWEN, Fields Institute
Applications of the space of metric trees  [PDF]

The space of metric $n$-trees is a polyhedral complex, in which each polyhedron corresponds to a different tree topology. Under the construction of Billera, Holmes, and Vogtmann, this space is non-positively curved, so there is a unique geodesic (shortest path) between any two trees. Furthermore, the (Frechet) mean of a set of trees in this space is well-defined and computable by an iterative algorithm. We present properties of this mean tree, including some non-Euclidean "sticky" behaviour, as well as applications to biological problems in phylogenetics and medical imaging.

VINCENT PILAUD, Fields Institute Toronto
Coxeter brick polytopes  [PDF]

We define the brick polytope of a subword complex on a finite Coxeter group. This construction provides polytopal realizations for a certain class of subword complexes containing in particular the cluster complexes of S. Fomin and A. Zelevinsky. For the later, the brick polytopes coincide with the generalized associahedra of C. Hohlweg, C. Lange, and H. Thomas. We obtain a vertex description of these polytopes and explain some of their combinatorial properties. Joint work with Christian Stump.

ELISSA ROSS, Fields Institute
The rigidity of periodic bar body frameworks  [PDF]

From the perspective of rigidity theory, d-dimensional bar body frameworks are a well understood class of structures. That is, good combinatorial characterizations exist to predict the generic rigidity of such graphs in any dimension. In this talk, we consider the question of infinite periodic bar body frameworks, which we study as multigraphs on a torus. We describe necessary conditions for the rigidity of these frameworks, and outline what is known about the sufficiency of these conditions.

BERND SCHULZE, Fields Institute
Predicting flexibility in periodic frameworks with added symmetry  [PDF]

Recent work from authors across disciplines has made substantial contributions to counting rules (Maxwell type theorems) which predict when an infinite periodic framework would be rigid or flexible while preserving the periodic pattern. Other work has shown that for finite frameworks, introducing symmetry modifies the previous general counts, and under some circumstances this symmetrized Maxwell type count can predict added finite flexibility in the structure. In this talk we combine these approaches to present new Maxwell type counts for the columns and rows of a modified orbit rigidity matrix for frameworks that have both a periodic structure and additional symmetry within the periodic cells. In a number of cases, this count for the combined group of symmetry operations demonstrates that there is added finite flexibility in what would have been rigid when realized without the symmetry. Given that many crystal structures have these added symmetries, and that their flexibility may be key to their physical and chemical properties, these results are of both practical and theoretic interest. This talk is based on joint work with Elissa Ross and Walter Whiteley.

CSABA TOTH, University of Calgary
New bounds for untangling geometric graphs  [PDF]

Suppose that we are given a straight-line drawing $D$ of a planar graph $G$ such that some pairs of edges cross. Since $G$ is planar, it can be redrawn (by relocating some of its vertices) such that no two edges cross anymore. The process of redrawing $G$ to obtain a crossing-free straight-line drawing is called the {\em untangling} of $G$. For every $n\in \mathbb{N}$, there is a planar graph $G_0$ with $n$ vertices and a straight-line drawing $D_0$ of $G_0$ such that in any {\em crossing-free} straight-line drawing of $G_0$, at most $O(n^{.4981})$ vertices lie at the same position as in $D_0$. For every planar graph $G$ with $n$ vertices and every straight-line drawing $D$ of $G$ (with possible edge crossings), there is a {\em crossing-free} straight-line drawing of $G$ such that at least $\Omega(n^{0.3766})$ vertices are at the same position as in $D$. (Joint work with Arikushi, Cano, and Urrutia.)

RYAN TRELFORD, University of Calgary
The Equivalence of The Illumination and Separation Conjectures  [PDF]

Let $K$ be $d$-dimensional convex body in $\mathbb{E}^d$, and let $Q\in\mathbb{E}^d\setminus K$. A point $P$ on the boundary of $K$ is said to be illuminated by $Q$ if the ray emanating from $Q$ through $P$ intersects the interior of $K$. One can ask what is the smallest positive integer $n$ such that there exists a set of distinct points $\{Q_1,\ldots,Q_n\}$ whereby every boundry point of $K$ is illuminated by at least one of the $Q_i$'s. The illumination conjecture (formulated by I. Gohberg, H. Hadwiger, and A. Markus) states that $n\leq 2^d$. Surprisingly, $2^d$ is also the conjectured maximum number of hyperplanes that are necessary to separate any interior point $O$ of $K$ from any face of $K$. In this talk, I will outline K. Bezdek's proof that the Illumination Conjecture and the Separation Conjecture are indeed equivalent.

VIKTOR VIGH, Fields Institute
On the diminishing process of B. Tóth  [PDF]

B. Tóth suggested some 20 years ago the following random process to investigate: let $B=B_0$ be the unit circular disc in $R^2$ centered at the origin, and define $B_n$ recursively as follows: we choose a random point $p_n$ from $B_{n-1}$ according to the uniform distribution and let $B_n= B_{n-1} \cap (p_n + B)$. $B_n$ is a disc-polygon, the first interesting questions are: what can we say about the expectations of different geometric quantities of $B_n$ (e.g. number of vertices, diameter). These problems turned out to be very tough, no relevant results are known about the process. In this talk we consider some closely related problems.

In the first part of the talk we replace the unit disc in the process by regular simplices (in any dimension) and by regular polygons (in the plane). Asymptotic results are given for the speed of the process, and we examine the limit distribution of the center in the case of simplices.

In the second part of the talk we consider another model to obtain random disc-polygons: we fix a spindle convex disc $S$ in the plane, we choose $n$ independent random point from $S$ according to the uniform distribution, and we define $S_n$ as the spindle convex hull of the chosen points. We show asymptotic results for the expectation of the number of the vertices of $S_n$, if $S$ has smooth enough boundary, or if $S$ is a disc-polygon.

The talk is based on joint work with G. Ambrus, F. Fodor and P. Kevei.


Ryerson University York University AARMS: Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences

Nous remercions chaleureusement ces commanditaires de leur soutien.

© Société mathématique du Canada :