Abstracts
Abdo Alfakih, University of Windsor
On the Universal rigidity of Tensegrity frameworks
A tensegrity framework $(G, p)$ in $R^r$ is a graph $G$, where each edge
is labeled as either a bar, a cable, or a strut; and where each node i is
mapped to a pint $p^i$ in $R^r$. Connelly proved that if an r-dimensional
tensegrity framework $(G, p)$ on n vertices in $R^r$ admits a proper semide
nite stress matrix of rank n -r -1, and if configuration $p = (p^1,...p^n)$
is generic, then $(G, p)$ is universally rigid. For the special case of
bar frameworks, Alfakih and Ye proved that this result holds under the assumption
that confguration $p$ is in general position. In this talk, we show that
the above tensegrity result continues to hold under the much weaker assumption
that in configuration $p$, each point and its neighbors in $G$ affnely span
$R^r$ (Joint work with Viet-Hang Nguyen).
Karoly Bezdek, University of Calgary
Plank theorems via successive inradii
In the 1930's, A. Tarski introduced his plank problem at a time when the
field discrete geometry was about to born. It is quite remarkable that Tarski's
question and its variants continue to generate interest in the geometric
as well as analytic aspects of coverings by planks in the present time as
well. Besides giving a short survey on the status of the affine plank conjecture
of T. Bang (1950) we prove some new partial results for the successive inradii
of the convex bodies involved. The underlying geometric structures are successive
hyperplane cuts introduced several years ago by Conway and inductive tilings
introduced recently by Akopyan and Karasev.
Ted Bisztriczky, University of Calgary
Erdos-Szekeres type theorems for planar convex sets
A family F of sets is in convex position if none of its members is contained
in the convex hull of the union of the others. The members of F are ovals
(compact convex sets) in the plane that have a certain property. An Erdos-Szekeres
type theorem concerns the existence , for any integer n=3, of a smallest
positive integer N(n) such that if |F|=N(n) then there are n ovals of F
in convex position.
This talk is based upon work with Gabor Fejes Toth and surveys some well
known theorems and introduces some new ones.
Yuen-Lam Cheung, University of Waterloo
Efficient use of semidefinite programming for the selection of rotamers
in protein conformations
Determination of a protein's structure can facilitate an understanding
of how the structure changes when that protein combines with other proteins
or smaller molecules. One important issue is the determination of the side
chain positions given a fixed protein backbone. In this talk, we consider
an integer programming formulation that models the side chain positioning
problem, which generalizes a few combinatorial optimization problems such
as the 3SAT problem and the max $k$-cut problem. We study a semidefinite
programming (SDP) relaxation of the NP-hard side chain positioning problem,
introduced by Chazelle, Kingsford and Singh (2004). We show that the Slater
constraint qualification (strict feasibility) fails for the SDP relaxation,
which can then be regularized by using facial reduction; the resultant regularized
SDP relaxation can be solved much faster and more accurately than the original
SDP relaxation. We discuss some rounding techniques for obtaining feasible
integral solution from the SDP relaxation. We also present a cutting plane
technique for enforcing the nonnegativity constraints in the SDP relaxation,
improving the efficiency in solving the SDP relaxation and the quality of
the final integral solution.
This is joint work with Forbes Burkowski and Henry Wolkowicz.
Marston Conder, University of Auckland
An update on polytopes with many symmetries
In this talk I'll give a brief update on some recent discoveries about
regular and chiral polytopes, including:
$\bullet$ the smallest regular polytopes of given rank
$\bullet$ simplifications/applications of the intersection condition
$\bullet$ computer-assisted determination of all regular and chiral polytopes
with up to 4000 flags
$\bullet$ conditions on the Schläfli type $\{p_1,p_2,...,p_n\}$ for
the existence of a tight regular $n$-polytope (with $2p_{1}p_{2}\,...\,p_{n}$
flags)
$\bullet$ chiral polytopes of type $\{3,3,\dots,3,k\}$ (with some $A_n$
or $S_n$ as automorphism group).
Pieces of these involve joint work with Gabe Cunningham, Isabel Hubard,
Dimitri Leemans, Deborah Oliveros, Eugenia O'Reilly Regueiro and Daniel
Pellicer.
Robert Connelly, Cornell University
A complete certificate universal rigidity
A bar framework, determined by a finite graph $G$ and configuration p=(p_1,
p_2, … p_n) in R^d, is universally rigid if it is rigid in any R^D
containing R^d. We provide a characterization of universally rigidity for
any graph G and any configuration p in terms of a sequence of affine subsets
of the space of configurations. This corresponds to a facial reduction process
for closed finite dimensional convex cones, and it is a stronger property
than global rigidity, but promises to provide a more concrete setting for
global rigidity. The theory also applies naturally to tensegrity frameworks.
This is joint work with Steven Gortler.
Balazs Csikos, Eotvos Lorand University
Optimal covering of a disk with congruent smaller disks
In 2008 R. Connelly asked how we should place n small disks of radius r
to cover the largest possible area of a disk of radius R > r. The problem
is interesting only when r is between the maximal radius for which the small
disks can be packed into the big disk and the minimal radius for which they
can cover it. We discuss some results concerning small values of n. It is
known that for n=5, the optimal configuration has a 5-fold rotational symmetry
when r is slightly above the covering radius, but the rotational symmetry
is lost as r increases. We show that for n=3, there is no such a symmetry
breaking with the increase of r.
The analogous statement is easy to prove for n=2, and conjectured to be
true for n=4.
Antoine Deza, McMaster University
Colourful linear programming
We present results and open questions dealing with a generalization of
linear programming introduced by Bárány and Onn in 1997, and
the associated generalization of the Carathéodory's Theorem proven
by Bárány in 1982. In particular, we present generalizations
of the Colourful Carathéodory Theorem due to Arocha et al. and Holmsen
et al. and strengthening of these. Combinatorial generalizations and computational
approaches are discussed. Based on joint-works with Sui Huang, Frédéric
Meunier, Pauline Sarrabezolles, Tamon Stephen, Tamás Terlaky, and
Feng Xie.
Ricardo Fukasawa, University of Waterloo
Cutting-planes for integer programming based on lattice-free sets
In this talk I will review some results in the theory of cutting planes
for integer programming. These results show that some very strong class
of cutting planes (Gomory cuts) can be derived as cuts based on lattice-free
polyhedra in a low dimension. Therefore, there has been recent effort in
generalizing those results and also in understanding that type of polyhedra.
I will give an overview of some developments of the theory and point out
to some interesting open problems.
Thomas C. Hales, University of Pittsburgh
The formal verification of nonlinear inequalities
This talk will discuss recent results on the formal verification of nonlinear
inequalities with applications to discrete geometry. This talk is largely
based on research by A. Solovyev.
Isabel Hubard, Universidad Nacional Autónoma de México
Projective chiral polytopes
The projective n-space can be seen as $\mathbb{S}^n$, identifying antipodal
points. In a similar way as one can realise polytopes in Euclidean spaces,
one can realise polytopes in projective spaces. A polytope is said to be
chiral if has no "reflection" symmetry, but maximum degree of
"rotational" symmetry. More formally, a polytope is chiral if
its automorphism group has two orbits on flags, with adjacent flags belonging
to different orbits. In this talk we shall discuss some examples of chiral
polytopes in the projective 3-space.
Muhammad Khan, University of Calgary
Equal sum sequences and imbalance sets of tournaments
In 1978, Reid conjectured that any finite set of non-negative integers
is the score set of some tournament and in 1989, Yao gave a non-constructive
proof of Reid's conjecture using arithmetic arguments. No constructive proof
has been found since. In this talk, we investigate a related problem, namely,
which sets of integers are imbalance sets of tournaments. We completely
characterize these sets and also estimate the minimal order of a tournament
realizing an imbalance set. Our proofs are constructive and provide a pseudo-polynomial
time algorithm for realizing any imbalance set. Furthermore, we show that
the problem to decide whether a set of integer is the imbalance set of a
tournament is closely related with the
problem of finding equal sum sequences (ESSeq) from two sets of integers,
a generalization of the well-known equal sum sets problem.
Abhinav Kumar, MIT
Tight simplices and codes in compact spaces
A tight simplex (or more generally, code) in a compact 2-point homogeneous
space is one whose size matches the linear programming bound, subject to
its minimal distance. I will recall known examples
of tight codes in real and complex projective spaces, and describe newexistence
proofs of many families of tight simplices in projective spaces over the
quaternions and octonions. The most interesting of these are simplices of
15 points in HP^2 and 27 points in OP^2, whose non-existence (!) had been
conjectured for thirty years. In particular, these simplices are all universally
optimal. Time permitting, I will also describe examples of tight simplices
in real Grassmannians. This is joint work with Henry Cohn and Gregory Minton.
Dimitri Leemans, University of Auckland
C-groups and almost simple groups
Several results have been obtained recently on classifications of abstract
regular polytopes associated to almost simple groups. These abstract polytopes
are also string C-groups and, as their name says it, they have a string
Coxeter diagram. It is natural to ask if we could say something is we drop
the string condition.
I will give some recent results in that direction that would lead to classify
the building blocks of Jacques Tits' theory of buildings, namely apartments.
Nicholas Matteo, Northeastern University
Two-orbit convex polytopes
We classify all the convex polytopes, and face-to-face tilings of $E^n$
by convex polytopes, whose symmetry groups have two orbits on the flags.
It turns out there aren't very many, and none are more than four-dimensional.
We also consider convex polytopes and tilings with two flag orbits under
the combinatorial automorphism group.
Peter McMullen,University College London
Realizations of symmetric sets
In the two years since the original Workshop, there have been significant
developments in realization theory; it is the aim of this talk to give an
outline of them. A symmetric set is a finite set together with a transitive
subgroup of its permutations; thus the situation is rather more general
than previously, where (vertex-sets of) regular polytopes alone were considered.
Cosine vectors completely describe realizations of symmetric sets, and a
product on them assisted in tackling harder problems than could be dealt
with by scaling and blending alone; this material was presented in Toronto
two years ago. The core of the latest work is an inner product on cosine
vectors, which leads to nice orthogonality relations. So far, this is contained
in my paper `Realizations of regular polytopes, IV' (in press). Something
even more recent will be kept as a surprise for the meeting.
Shinji Mizuno,Tokyo Institute of Technology
On the number of solutions generated by the simplex method for LP
Co author: Tomonari Kitahara
We obtain upper bounds for the number of distinct solutions generated by
the simplex method for linear programming (LP). One of the upper bounds
is polynomial in the number of variables, the number of constraints, and
the ratio of the maximum to the minimum positive components in all the basic
feasible solutions. We show that they are good upper bounds for some special
LP problems including those on 0-1 polytopes, those with totally unimodular
matrices, and the Markov decision problems. We also show that the upper
bounds are almost tight by using an LP instance on a 0-1 polytope and a
simple variant of the Klee-Minty example.
Barry Monson, University of New Brunswick, Fredericton
Regular Covers and Monodromy Groups of Abstract Polytopes
Please click here for abstract
Daniel Pellicer, Universidad Nacional Autónoma de México
Chiral extensions of chiral polytopes
Abstract chiral polytopes are combinatorial structures that generalize
the notion of convex polytope, with the extra property of having all combinatorial
symmetry by (abstract) rotations, but none by reflections. Abstract chiral
d-polytopes with regular facets are known to have a chiral universal extension
(a chiral (d+1)-polytope whose facets are isomorphic to the starting polytope),
where the last entry of the Schlafli type is infinite. We show that every
finite chiral polytope with regular faces admits a finite chiral extension.
Ian Post, University of Waterloo
The performance of the simplex method on deterministic Markov decision
processes
Markov decision processes (MDPs) are a particularly interesting class of
linear programs, lying just beyond where our ability to solve LPs in strongly
polynomial time stops. We prove that the simplex method using Dantzig's
pivoting rule converges in strongly polynomial time for deterministic MDPs
regardless of the discount factor. For a deterministic MDP with $n$ states
and $m$ actions, we prove the simplex method runs in $O(n^3 m^2 \log^2 n)$
iterations if the discount factor is uniform and $O(n^5 m^3 \log^2 n)$ iterations
if each action has a distinct discount factor. Previously the simplex method
was known to run in polynomial time only for discounted MDPs where the discount
was bounded away from 1.
Egon Schulte, Northeastern University
Classification of Regular and Chiral Polytopes by Topology
The past three decades have seen a revival of interest in the study of
polytopes and their symmetry. The most exciting new developments all center
around the concept and theory of abstract polytopes. The lecture gives a
survey of currently known topological classification results for regular
and chiral polytopes, focusing in particular on the universal polytopes
which are globally or locally toroidal. While there is a great deal known
about toroidal regular polytopes, there is almost nothing known about the
classification locally toroidal chiral polytopes.
Tamon Stephen, Simon Fraser University
Colourful Simplices and Octahedral Systems
Given a point p in R^d contained in each of (d+1) simplices (colours),
Barany's colourful version of the Caratheodory Theorem guarantees that p
is also in the convex hull of a colourful simplex with one vertex of each
colour. Let mu(d) be the minimum possible number of such colourful simplices
containing p. A construction shows that mu(d) <= d^2+1, and this is conjectured
to be tight.
In this talk, we discuss octahedral systems, which model this problem combinatorially,
and use them to get lower bounds for mu(d).
Csaba D. Toth, University of Calgary
Universal point sets and edge sets
This talk surveys recent results and open problems on universal point sets
and universal edge sets for geometric graphs. A point set S in the plane
is universal for a class of planar graphs if every graph in
that class admits a geometric embedding such that all vertices are in S.
Finding the minimum size of a universal point set for n-vertex planar graphs
is a longstanding open problem. The current best lower and upper bounds
are 1.235-o(1)n and n^2/2, respectively. Point sets of size O(n log n) and
O(n^{3/2} log n) have recently been found for important special cases. A
planar graph G is free if every triangulation of G admits a family of geometric
realizations that attain all possible distributions of lengths on the edges
of G. In a recent work with Fulek et al., we have identified all free graphs,
using tools from graph drawing and rigidity theory.
Asia Ivic Weiss, York University
Polytopes derived from cubic tessellations
A toroid of rank rank n+1 is the quotient of a Euclidean tessellation of
n-space over a rank n subgroup of the group its translations. We derive
some general results on the group of automorphisms of equivelar toroids,
that is the toroids obtained from the regular tessellations. We give a complete
classification of equivelar toroids in ranks 3 and 4.
Henry Wolkowicz, University of Waterloo
Relaxations of Graph Partitioning and Vertex Separator Problems using Continuous
Optimization
Both the Graph Partitioning and Vertex Separator problemsare hard discrete
optimization problems. We look at severalapproximation techniques. This
includes eigenvalue and projectedeigenvalue techniques, quadratic programming
techniques, andsemidefinite programming (SDP). In particular, we show thatthe
SDP relaxation is equivalent to and arises from the Lagrangian relaxation
for a particular quadratically constrained quadraticmodel. Moreover, the
bounds obtained by the SDP techniques are the best among the ones we compare.
(work with Ting Kei Pong, Hao Sun, Ningchuan Wang)
Yuriy Zinchenko, University of Calgary
Towards efficient approximation of p-cones
2-norm cone, also known as the second-order cone (SOC), recieved wide applications
in modern convex optimization. SOC wide aceptance due to numerous applications
was equally well supported by efficient numerical techniques to handle linear
optimization problems posed over such cones. In particular, SOC may be effectively
handled directly by the so-called interior-point methods as well as can
be efficiently approximated with polyhedra. The situtation with SOC extensions
to p-norm cones so far remaines dramatically different: despite applications
being present, our capacity to handle these cones remains limited. Niether
there are self-concordant barriers comparable to that of SOC known for such
generalized cones, nor have we efficient means to approximate these cones.
We describe a few approaches aimed at constructing good approximations to
these cones as well as present the analysys of a greedy polyhedral approximation
scheme. Our belief is that these cones ultimately may not be that much different
from SOC.
Back to top
