April 24, 2014

November 25- 29, 2013
Retrospective Workshop on
Discrete Geometry, Optimization, and Symmetry

Károly Bezdek (Calgary), Asia Ivic Weiss (York)
Antoine Deza (McMaster), Yinyu Ye (Stanford)


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