Réunion d'hiver SMC 2018

Vancouver, 7 - 10 décembre 2018

Géométrie discrète et combinatoire
Org: Barry Monson (University of New Brunswick) et Asia Ivic Weiss (York University)
[PDF]

GABRIELA ARAUJO-PARDO, Mathematics Institute, National University of México
The achromatic number of Kneser Graphs and their relationship with Steiner Triple Systems  [PDF]

In this talk we give the notion of complete colorings in graphs, achromatic number, Knesser Graphs and Steiner Triple Systems. Also, we explain how the Steiner triple systems solve the problem about the existence of complete colorations on Knesser graphs that attain the upper bound of the achromatic number, where the achromatic number of a graph G is the maximum integer value for the number of chromatic classes in a complete and proper coloring of G.

KAROLY BEZDEK, University of Calgary
On Gromov's conjecture for uniform contractions  [PDF]

Let ${\mathbb E}^d$ denote the $d$-dimensional Euclidean space. The $r$-ball body generated by a given set in ${\mathbb E}^d$ is the intersection of balls of radius $r$ centered at the points of the given set. In this talk we prove the following Blaschke-Santalo-type inequalities for $r$-ball bodies: for all $1\leq k\leq d$ and for any set of given volume in ${\mathbb E}^d$ the $k$-th intrinsic volume of the $r$-ball body generated by the set becomes maximal if the set is a ball. As an application we prove the following. Gromov's conjecture (1987) states that if the centers of a family of $N$ congruent balls in ${\mathbb E}^d$ is contracted, then the volume of the intersection does not decrease. A uniform contraction is a contraction where all the pairwise distances in the first set of centers are larger than all the pairwise distances in the second set of centers, that is, when the pairwise distances of the two sets are separated by some positive real number. The author and M. Naszodi [Discrete Comput. Geom. (2018), 1-14] proved Gromov's conjecture as well as its extension to intrinsic volumes for all uniform contractions in ${\mathbb E}^d$, $d>1$ under the condition that $N\geq \left(1+\sqrt{2}\right)^d$. We give a short proof of this result using the Blaschke-Santalo-type inequalities of $r$-ball bodies and improve it for $d\geq 42$.

PETER BROOKSBANK, Bucknell University
Existence of high rank regular polytopes for PSp(4,q)  [PDF]

This talk pertains to the following general question: given an infinite family $\mathcal{F}$ of finite simple groups, and an integer $r>2$, determine the members of $\mathcal{F}$ that arise as symmetries of an abstract regular polytope of rank $r$. It is unlikely that a complete answer will be found for all $\mathcal{F}$ and all $r$, but the question helps to structure the search for new families of polytopes having symmetry groups that by some measure are well understood.

The question has been settled for all families $\mathcal{F}$ when $r=3$, and for the alternating groups ${\rm Alt}(n)$ and the projective groups ${\rm PSL}(3,q)$ and ${\rm PSU}(3,q)$ for arbitrary rank $r$. In joint work with Leemans I showed that ${\rm PSL}(4,q)$ has polytopes of rank 4, and with Ferrara and Leemans that ${\rm PSp}(2m,q)$ has rank $2m+1$ polytopes so long as $q=2^e$ is even. In this talk I will focus on the groups ${\rm PSp}(4,q)$ for $q$ odd, giving constructions of polytopes of ranks 4 and 5.

GABE CUNNINGHAM, University of Massachusetts Boston
Vertex-faithful regular polyhedra  [PDF]

A regular abstract polyhedron is vertex-faithful if each symmetry is uniquely determined by its action on the vertices. When the number of vertices has only a few factors, it is possible to classify all regular vertex-faithful polyhedra with that many vertices. In this talk, I will present a classification of all regular polyhedra with a prime number of vertices (vertex-faithful or not), and I will describe some results so far on vertex-faithful regular polyhedra where the number of vertices is twice a prime or a prime squared. Joint work with Mark Mixer.

ROBERT DAWSON, Saint Mary's University
A Circle Tiling Problem  [PDF]

We investigate the problem of whether a 5x5 grid of points can be covered without duplication (tiled) by five circles. The answer is shown to be unique, and some generalizations are presented.

WENDY FINBOW-SINGH, Saint Mary's University
Constructing Generically Rigid Frameworks  [PDF]

The combinatorial characterization of general graphs that can be realized in 3-space as isostatic (rigid and independent) bar and joint frameworks is a major unsolved problem in rigidity theory. In the absence of a general characterization, it is interesting to investigate certain classes of graphs and confirm the rigidity and independence of almost all realizations of this graph in 3-space (generic rigidity), something that follows from the existence of even one isostatic realization.

Cauchy, Dehn, and Alexandrov proved that arbitrary convex triangulated spheres are isostatic, and therefore any realization of these 3-connected planar graphs $G=(V, E)$, with $|E|=3|V|-6$, at generic positions of the vertices are also isostatic. Finbow and Whiteley provided another class, the class of 3-dimensional isostatic frameworks, the block and hole polyhedra, along with methods to verify generic rigidity that can be extended to other classes. These methods are based on tracking when a larger framework can be derived from a known small example using vertex splitting, an operation known to take a minimally generically rigid framework to a new minimally generically rigid framework with one more vertex.

There is another technique for adding a vertex to a rigid structure that preserves isostatic rigidity; spider splitting. In this talk we will present some preliminary results regarding the relationship between vertex-splitting and spider-splitting.

AMANDA MONTEJANO, UNAM
A rainbow version of Mantel's Theorem  [PDF]

One of the first results in extremal graph theory, Mantel's Theorem, asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices), and this bound is best possible. Here we consider a colourful variant of the above. Let $G_1, G_2, G_3$ be three graphs on a common vertex set $V$ and think of each graph as having edges of a distinct colour. Define a rainbow triangle to be three vertices $v_1, v_2, v_3 \in V$ so that $v_i v_{i+1} \in E(G_i)$ (where the indices are treated modulo $3$). We will be interested in determining how many edges force the existence of a rainbow triangle. We prove that whenever $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist a rainbow triangle. We provide an example to show this bound is best possible. This is a joint work with Ron Aharoni, Matt DeVos, Sebastian Gonzales and Robert Samal.

DEBORAH OLIVEROS, Instituto de Matemáticas UNAM
Tverberg Theorems with Altered Nerves.  [PDF]

Tverberg's theorem says that a set with sufficiently many points in $\mathbb{R}^d$ can always be partitioned into $m$ parts so that the $(m-1)$-simplex is the (nerve) intersection pattern of the convex hulls of the parts. The main results of our paper demonstrate that, Tverberg's theorem is but a special case of a more general situation where other simplicial complexes arise as nerves. We prove that, given sufficiently many points, all trees and cycles, can also be induced by at least one partition of a point set. We also discuss how some complexes cannot be achieved this way, even for arbitrarily large sets of point sets.

DANIEL PELLICER, UNAM (National University of Mexico)
Higher rank chiral polytopes with toroidal facets  [PDF]

Chiral abstract polytopes are combinatorial structures with maximal symmetry by combinatorial rotations, but none by reflections. Many such objects in ranks 3, 4 and 5 are known, but up to date there are very few constructions of chiral polytopes of ranks 6 and higher. In particular, it is still not known whether a given regular polytope of rank n is the facet of a chiral polytope of rank n+1. In this talk I will present a construction that shows that all but finitely many regular toroidal polytopes of rank n and type $\{4,3^{n-3},4\}$ are facets of chiral polytopes of rank n+1.

EGON SCHULTE, Northeastern University
Local Theory in Tilings and Delone Sets  [PDF]

Local detection of global properties in a geometric structure is usually a challenging problem. The Local Theorem for Tilings says that a tiling of Euclidean d-space is tile-transitive (isohedral) if and only if the large enough neighborhoods of tiles (coronas) satisfy certain conditions. This is closely related to the Local Theorem for Delone Sets, which locally characterizes those point sets among the uniformly discrete point sets in d-space which are orbits under a crystallographic group. Both results are of great interest in crystallography. We discuss old and new results from the local theory of tilings and Delone sets.

TAMON STEPHEN, Simon Fraser University
Colourful Simplicial Depth, Grids and Algorithms  [PDF]

We describe some combinatorial and geometric problems relating to colourful simplicial depth. The first is on covering (perhaps modulo 2) a box of grid points with axis-aligned affine subspaces. The objective is to do this so that each co-ordinate hyperplane containing grid points contains a subspace from the cover, and to minimize the number of elements in the cover. Others include computing the colourful simplicial depth of a configuration quickly, and solving a colourful version of linear programming feasibility.

GORDON WILLIAMS, University of Alaska Fairbanks
On maniplexes with co-skeleton $K_4$  [PDF]

This talk will discuss recent progress on a classification problem in the theory of maniplexes, specifically, the classification of rotary and reflexible maniplexes in rank 4 whose duals have one-skeletons are the graph $K_4$.

A maniplex is a generalization of the graph theoretic map to higher dimensions, much in the way abstract polytopes are a combinatorial abstraction of polyhedra and convex polytopes. They are studied via similar mechanisms, in particular through their automorphism and connection groups. Rotary and reflexible maniplexes form the two most symmetric kinds of maniplexes, and their study and classification plays a role similar to the classification of chiral and regular abstract polytopes do in the study of abstract polytopes.

This is joint work with Steve Wilson.