Réunion d'hiver SMC 2019
Toronto, 6 - 9 décembre 2019
Org: Károly Bezdek (Calgary), Ted Bisztriczky (Calgary), Ferenc Fodor (Calgary and Szeged) et Asia Ivić Weiss (York)
[PDF]
- GABRIELA ARAUJO, Mathematics Institute, National University of México
Circulant graphs and digraphs: Achromatic and diachromatic numbers and achromatic index [PDF]
-
A {\bf{complete}} $k$-vertex-coloring of a graph $G$ is a vertex-coloring of $G$ using $k$ colors such that for every pair of colors there is at least two incident vertices in $G$ colored with this pair of colors. The {\bf{chromatic}} $\chi(G)$ and {\bf{achromatic}} $\alpha(G)$ numbers of $G$ are the smallest and the largest number of colors in a complete proper $k$-vertex-coloring of $G$, therefore
$\chi(G)\leq\alpha(G)$.
\
The dichromatic number and the diachromatic number, generalice the concepts of chromatic number and achromatic number. An {\bf{acyclic}} $k$-vertex-coloring of a digraph $D$ is vertex coloring using $k$ colors such that $D$ has no monochromatic cycles and a \emph{complete} $k$-vertex-coloring of a digraph $D$ is a vertex coloring using $k$ colors such that for every ordered pair $(i,j)$ of different colors, there is at least one arc $(u,v)$ such that $u$ has color $i$ and $v$ has color $j$. The dichromatic number $dc(D)$ and diachromatic number $dac(D)$ of $D$ are the smallest and the largest number of colors in a complete proper $k$-vertex-coloring of $D$, therefore $dc(D)\leq dac(D)$. \
We determine the achromatic and diachromatic numbers of some specific circulant graphs and digraphs and give general bounds for these two parameters on these graphs and digraphs. Also, we determine the achromatic index for circulant graphs of order $q^2+q+1$ using projective planes.
- KAROLY BEZDEK, University of Calgary
From spherical to Euclidean illumination [PDF]
-
In this talk I introduce the problem of illumination of convex bodies in spherical spaces and solve it for a large subfamily of convex bodies. Then I derive from it a combinatorial version of the classical illumination problem for convex bodies in Euclidean spaces as well as a solution to that for a large subfamily of convex bodies, which in dimension three leads to special Koebe polyhedra. This is a joint work with Z. Langi (Budapest Univ. of Tech., Hungary).
- KAROLY J. BOROCZKY, Renyi Institute of Mathematics
Reverse Minkowski and Alexandrov-Fenchel inequalities [PDF]
-
Around 1992, Uli Betke and Wolfgang Weil proved a reverse Minkowski inequality for the mixed area in terms of the perimeter where equality occurs for orthogonal segments. This inequality is generalized to higher dimensions where the most general version ("Reverse Alexandrov-Fenchel inequality") is only verified for zonoids. Stability versions are also discussed. Joint work with Daniel Hug.
- ROBERT DAWSON, Saint Mary's University
Collision-Free Linkages [PDF]
-
Linkages have been studied by both mathematicians and engineers for many years. In the late 19th century Kempe showed that any algebraic curve could be traced (at least in part) by an appropriately-designed linkage. However, (perhaps because there are other reasons why the tracing will in general be only partial) he was not concerned about the fact that the links may intersect each other. Abel \emph{et al} have shown that the linkage may be made planar, but at the cost of a very indirect modeling with enormous numbers of links. This talk -- joint work with Pietro Milici (Brest) -- gives a simple construction that closely emulates a Kempe-style ``ideal'' linkage using rigid nonintersecting links. In particular, I shall try to make clear what this means!
- 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.
- ALEXEY GARBER, University of Texas Rio Grande Valley
Five-dimensional parallelohedra [PDF]
-
In this talk I will report on the recent progress in the Voronoi conjecture on parallelohedra. The conjecture claims that every convex polytope that tiles $\mathbb{R}^d$ with translations only is an affine image of the Dirichlet-Voronoi domain for some $d$-dimensional lattice. The Voronoi conjecture was stated more than a century ago but is still open in general case.
In the talk I plan to briefly survey some known results on the Voronoi conjecture and outline the proof of the conjecture in $\mathbb{R}^5$.
Based on a joint work with Alexander Magazinov.
- JING HAO, Georgia Institute of Technology
Minimum distance of random linear codes [PDF]
-
In coding theory, the trade-off between information rate $R$ and error-correcting ability $\delta$ of a code is a central topic of study. Classical work by Gilbert and Varshamov has showed that with high probability, the minimum distance of a random linear code can achieve the G-V bound given by $R = 1-H_2(\delta)$, where $H_2$ is the binary entropy function. In this work, we give a full characterization for the minimum distance of a random linear code by comparing it to the random code ensemble where every coordinate of a codeword are taking values uniformly in $\mathbb{F}_q$.
- ILYA IVANOV, University of Calgary
Illumination number of the unconditionally symmetric 4-dimensional cap body of a ball [PDF]
-
Cap body of a ball in $\mathbb{E}^d$ (as introduced by Minkowski in 1903) is a convex hull of an origin centered euclidean closed unit ball $B^d(o)$ and a countable set of points outside of the ball $\{p_1, p_2, \dots \} \in \mathbb{E}^d \setminus B^d(o)$ such that for any two points $p_i, p_j$ the segment $[p_i, p_j]$ has a nonempty intersection with $B^d(o)$.
Unconditionally symmetric convex body in $\mathbb{E}^d$ is a body that together with every its point with coordinates $(x_1, \dots, x_d)$ also contains all the points with coordinates $(\pm x_1, \dots, \pm x_d)$. In my talk I will show that 8 illumination directions are enough to completely illuminate the boundary of an unconditionally symmetric cap body of a ball in $\mathbb{E}^4$.
- BARRY MONSON, University of New Brunswick-Fredericton
More on Roli's Cube [PDF]
-
Actually Roli's cube $\mathcal{R}$ isn't a cube, although it does share the $1$-skeleton of a $4$-cube. First
described by Javier (Roli) Bracho, Isabel Hubard and Daniel Pellicer in 2014,
$\mathcal{R}$ is a chiral $4$-polytope of type $\{8,3,3\}$, faithfully realized in $\mathbb{R}^4$ (a situation earlier
thought to be impossible). Of course, Roli didn't himself name $\mathcal{R}$; but the
eponym is pleasing and has taken hold.
Today I will give some new insights into $\mathcal{R}$, touching on its regular covers, connections to
the M\"{o}bius-Kantor configuration, and other more abstract things.
This work was generously supported at Universidad Nacional Aut\'{o}noma de M\'{e}xico (Morelia) by PAPIIT-UNAM grant \#IN100518 .
- AMANDA MONTEJANO, UNAM
Zero-sum subsequences in bounded-sum $\{-1, 1\}$-sequences [PDF]
-
In this talk, we consider problems and results that go in the opposite direction of the classical theorems in the discrepancy theory. The following statement gives a flavor of our approach. Let $t$, $k$ and $q$ be integers such that $q \ge 0$, $0 \le t < k$, and $t \equiv k \,({\rm mod}\, 2)$, and take $s \in [0,t+1]$ as the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Then, for any integer
$$n \ge \frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s$$ and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)|\leq q$, there is a block of $k$ consecutive terms ($k$-block) $B\subset [n]$ with $|\sum_{x\in B}^nf(x)|\leq t$. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This is a joint work with Yair Caro and Adriana Hansberg.
- ANTONIO MONTERO, York University
A family of regular hypertopes built from regular polytopes [PDF]
-
A regular hypertope is a combinatorial object that generalises both regular hypermaps and regular polytopes. In this talk we will present a construction of a family of regular hypertopes with some preassigned conditions on their local combinatorics. This family is built from a family of regular polytopes.
- DEBORAH OLIVEROS, Instituto de Matemáticas UNAM
The geometry and combinatorics of discrete line segment hypergraphs [PDF]
-
An $r$-segment hypergraph $H$ is a hypergraph whose edges consist of $r$-consecutive integer points on line segments in $\mathbb{R}^2$. In this talk, we will present some results in the chromatic number $\chi(H)$ and covering number $\tau(H)$ of hypergraphs in this family, uncovering several interesting geometric properties in the process. We provide improved (in fact, optimal) bounds on $\tau(H)$ for $r \le 5$ and provide sharp bounds on the chromatic number $\chi(H)$ in terms of $r$, and use them to prove two fractional versions.
Joint work with Christopher O'Neill and Shira Zerbib
- NATHAN ROBOCK, University of Calgary
r-convexity revisited [PDF]
-
For the last few decades researchers of convex bodies have been interested in the theory of strong convexity, first presented by Anton Mayer. In this talk I will discuss r-convexity, a norm-free and dimension free (where applicable) theory that is based on Mayer's strong convexity, and present some results from classical convexity that have been extended to r-convexity, such as the theorems of Caratheodory, Tietze, and Nakajima.
- EGON SCHULTE, Northeastern University
The Regularity Radius of Delone Sets [PDF]
-
Delone sets are uniformly discrete point sets in Euclidean d-space used in the modeling of crystals.
The mathematical theory describing the relationship between the local and global structure of a crystal was initiated by Delone, Dolbilin, Shtogrin, and Galiulin in the 1970's, and resulted in the Local Theorem for Delone Sets. Its main goal is to understand in mathematical terms how congruence of local atomic arrangements forces global structural regularity or periodicity. There are two types of Delone sets that account for regularity or periodicity, respectively, namely the regular systems (orbits of a single point under a crystallographic group) or multiregular systems (unions of finitely many point orbits under a crystallographic group). The local theory searches for local conditions on a Delone set X that guarantees the emergence of a crystallographic group of symmetries producing X as an orbit set consisting of a single point orbit or finitely many point orbits, respectively. There are interesting new results for the regularity radius of Delone sets. The regularity radius is the smallest number such that each Delone set X in d-space with mutually congruent point clusters (point neighborhoods) of this radius is a regular system. We discuss old and new results from the local theory of Delone sets, including a lower bound for the d-dimensional regularity radius which is linear in R, the radius of the largest empty ball of X, as well as an upper bound in dimension 3. This is joint work with a group of mathematicians and crystallographers.
- BRADEN STRACHAN, University of Calgary
Illumination number of the unconditionally symmetric 3-dimensional cap body of a ball [PDF]
-
Cap body of a ball in $\mathbb{E}^d$ (as introduced by Minkowski in 1903) is a convex hull of an origin centered euclidean closed unit ball $B^d(o)$ and a countable set of points outside of the ball $\{p_1, p_2, \dots \} \in \mathbb{E}^d \setminus B^d(o)$ such that for any two points $p_i, p_j$ the segment $[p_i, p_j]$ has a nonempty intersection with $B^d(o)$.
Unconditionally symmetric convex body in $\mathbb{E}^d$ is a body that together with every one of its point with coordinates $(x_1, \dots, x_d)$ also contains all the points with coordinates $(\pm x_1, \dots, \pm x_d)$. In my talk, I will show that 6 illumination directions are enough to completely illuminate the boundary of an unconditionally symmetric cap body of a ball in $\mathbb{E}^3$.
- BEATRICE-HELEN VRITSIOU, University of Alberta
On Hadwiger's covering conjecture [PDF]
-
A central problem in Discrete Geometry, Hadwiger's covering conjecture, asks to find the smallest integer $N(n)$ with the property that every convex body in ${\mathbb R}^n$ can be covered by at most $N(n)$ translates of its interior.
We will discuss connections with Asymptotic Convex Geometry and measure concentration, as well as with entropic methods, that allow for at least a subexponential improvement to the long-standing general upper bounds of Rogers for $N(n)$.
This is joint work with Han Huang, Boaz Slomka and Tomasz Tkocz.