CanaDAM 2021
En ligne, 25 - 28 mai 2021

Contributed Talks I

MACKENZIE CARR, Simon Fraser University
Digital Convexity in Cycles and Cartesian Products  [PDF]

Given a finite set $V$, a convexity, $\mathcal{C}$, is a collection of subsets of $V$ that contains both the empty set and the set $V$ and is closed under intersections. The elements of $\mathcal{C}$ are called convex sets. The digital convexity on the vertex set of a graph, originally introduced as a tool for processing digital images, is defined as follows: a subset $S \subseteq V(G)$ is digitally convex if, for every $v\in V(G)$, we have $N[v] \subseteq N[S]$ implies $v \in S$. Or, equivalently, $S$ contains every vertex for which it is a local dominating set. In this talk, we discuss the use of cyclic binary strings and certain types of $n\times m$ binary arrays to enumerate the digitally convex sets of the $k^{th}$ power of a cycle and of the Cartesian product of paths, $P_n\square P_m$.

ALEXANDER KOLPAKOV, Université de Neuchâtel
Space vectors forming rational angles  [PDF]

We classify all sets of nonzero vectors in $\mathbb{R}^3$ such that the angle formed by each pair is a rational multiple of $\pi$. The special case of four-element subsets lets us classify all tetrahedra whose dihedral angles are multiples of $\pi$, solving a 1976 problem of Conway and Jones: there are $2$ one-parameter families and $59$ sporadic tetrahedra, all but three of which are related to either the icosidodecahedron or the $B_3$ root lattice. The proof requires the solution in roots of unity of a $W(D_6)$-symmetric polynomial equation with $105$ monomials (the previous record was only $12$ monomials). This is a joint work with Kiran Kedlaya, Bjorn Poonen, and Michael Rubinstein.

MATTHEW SULLIVAN, University of Waterloo
Simple Drawings of $K_n$ from Rotation Systems  [PDF]

A complete rotation system on $n$ vertices is a collection consisting of the cyclic permutations of the elements $[n]\backslash\{i\}$. If $D$ is a drawing of a labelled graph, then a rotation at vertex $v$ is the cyclic ordering of the edges at $v$. In particular, the collection of all vertex rotations of a simple drawing of $K_n$ is a rotation system. Conversely, can we characterize when a complete rotation system can be represented as a simple drawing of $K_n$ (a.k.a. realizable)? In 2011, Jan Kyn\u{c}l published a proof using homotopy implying that if all 6 vertex rotation systems of an $n$ vertex rotation system $R_n$ are realizable, then $R_n$ is realizable. In this talk, we will briefly review the full characterization of realizable rotation systems and see a combinatorial proof that if rotation systems of size 10 are realizable, then the associated $n$ vertex rotation system is realizable.

JAMES TUITE, Open University, UK
The degree/geodecity problem for mixed graphs  [PDF]

The degree/girth problem asks for the smallest possible order of an undirected graph with given girth and minimum degree. In this talk we explore a new analogue of this problem for mixed graphs, i.e. graphs that contain both undirected edges and directed arcs. A mixed graph $G$ is $k$-geodetic for some $k \geq 2$ if for any pair of vertices $u,v$ of $G$ there is at most one non-backtracking mixed path from $u$ to $v$ with length not exceeding $k$; we ask for the order of the smallest $k$-geodetic mixed graph with given undirected and directed degrees. An extremal mixed graph for this problem is called a geodetic cage. We present new lower bounds on the order of $k$-geodetic mixed graphs, results on their regularity and constructions of geodetic cages.

AARON WILLIAMS, Williams College
Constructing Universal Cycles for Fixed-Content Strings  [PDF]

Consider the circular string $123313321323$ of length twelve. Its substrings of length three — $123, 233, 331, ..., 231, 312$ — encode the twelve permutations of the multiset $\{1,2,3,3\}$ with the redundant final symbol omitted. We provide the first explicit construction of these fixed-content universal cycles, along with efficient algorithms that generate each successive symbol in amortized O(1)-time, regardless of the specific multiset of symbols. \newline

When universal cycles of this type are decoded, the resulting order of strings (e.g. $1233, 2331, 3312, ..., 2313, 3123$) have a nice property: Successive strings differ by a prefix rotation of length $n$ or $n-1$. We illustrate how this property can be used to speed-up exhaustive computations for the stacker crane problem, and other combinatorial problems whose candidate solutions can be represented by fixed-content strings. \newline

Joint work with Joe Sawada (University of Guelph).