CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Graphs and geometry
Président: John Gimbel (University of Alaska)

RYAN HAYWARD, University of Alberta
Play Hex like an expert: a 76-year-old lecture  [PDF]

The connection game Hex --- played on a graph --- is popular with discrete mathematicians and computer scientists alike. On December 26 1942 Piet Hein introduced the game --- then called Polygon --- in the Danish newspaper Politiken, where he continued to write a regular Polygon column. Frustrated by letters from readers who had clearly not understood the game, on February 1 1943 Hein hosted a public lecture together with chess-expert Jens Lindhard. While researching our book ``Hex, the full story", Bjarne Toft and I located and deciphered Hein's notes for this public lecture, which sadly were unknown to Martin Gardner when he wrote a column on Hex in Scientific American in 1957. I will reprise the highlights of the Hein-Lindhard lecture, which includes a 6x6 first-player winning strategy.

YIFAN JING, University of Illinois at Urbana-Champaign
The genus of complete 3-uniform hypergraphs  [PDF]

In 1968, Ringel and Youngs confirmed the last open case of the Heawood Conjecture by determining the genus of every complete graph $K_n$. In this talk, we investigate the minimum genus embeddings of complete 3-uniform hypergraphs $K_n^{(3)}$. We determine both the orientable and the non-orientable genus of $K_n^{(3)}$. This is joint work with Bojan Mohar.

VALENTINA PEPE, Sapienza University of Rome
Finite Geometries and Pseudorandom Graphs  [PDF]

In [N. Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), R12, 8pp.] Alon constructs triangle-free pseudorandom graphs with high edge density. The very nice construction by S.Kopparty, as good as Alon's one, turns out to be the incidence graph of a Generalized Quadrangle over the finite fields $\mathbb{F}_q$ intersected with an $\mathbb{F}_p$-linear set, with $p=char (\mathbb{F}_q)$. Inspired by that, we explore the constructions of dense clique free pseudorandom graphs using finite geometries.

SIMA HAJIAGHAEI SHANJANI, University of Victoria
Hardness of Approximation for Geometric Set Cover and Related Problems  [PDF]

In Geometric Set Cover, the goal is to find a minimum sized cover for a given set of points in the plane by a family of given objects. We show that the following problems are NP-hard to approximate within $c$ factor of the optimum, where $c=(1537/1536)$: $(i)$ Geometric Set Cover even when the objects are axis-aligned rectangles. $(ii)$ Geometric Red-Blue Set Cover: given red points and blue points in the plane, the goal is to find a family of given axis-aligned rectangles that cover all the blue points with the minimum number of reds. $(iii)$ Boxes Class Cover: given red points and blue points in the plane, the goal is to find a minimum number of axis-aligned rectangles that cover all the blue points but no red. Prior to this work, $(i)$ was shown to be APX-hard and no hardness of approximation result has been shown for $(ii)$ and $(iii)$.

MATTHEW SULLIVAN, University of Waterloo
Fundamentals of Rotation Schemes  [PDF]

Suppose $D$ is a good drawing of the complete graph $K_n$. A rotation at a vertex $v$ of $D$ is the cyclic order at which $v$ sees its neighbours. A rotation scheme of $D$ is the collection of rotations at each vertex. Information like pairs of crossing edges are encoded by rotation schemes, and thus the crossing/planar $K_4$ information is as well. Using Ramsey theory and rotation schemes, we generate a proof of a generalized version of a theorem by Pach, Solymosi, T\'{o}th.