# Combinatorics

## Richard Guy and the Encyclopedia of Integer Sequences: A Fifty-Year Friendship

Richard Guy was a supporter of the database of integer sequences right from its beginning in the 1960s. This talk will be illustrated by sequences that he contributed, sequences he wrote about, and especially sequences with open problems that he would have liked but that I never got to tell him about.

## The Unity of Combinatorics: Connections and Wonders

An account of how a great Guy and his Brown coauthor created a 300-page book entitled "The Unity of Combinatorics" out of a 30-page paper from 1995 of the same name. The latter was an outline of a proposed lecture series, whose purpose was to feature the many connections within the vast area of combinatorics, thereby dispelling the then prevalent notion that combinatorics is just a bag of tricks. In writing the book, we took this notion and ran with it --- and how!

I'll talk about a number of these connections and some topics that seem almost magical, including Beatty sequences, Conway worms, games played with turtles instead of coins, and a way of viewing the non-negative integers as a field. The book begins with a child playing with colored blocks on his living-room rug and ends with a description of the Miracle Octad Generator. Finally, I'll talk about working with this gentlemanly giant of the world of numbers and sequences and patterns and games.

## Unsolved Combinatorial Games Richard K. Guy liked and others he would have liked

Richard started the Unsolved Problems in Combinatorial Games Column. I'll consider some of his favourites, talk about some developments, and add a few reminiscences.

## Random discrete surfaces

A triangulation of a surface is a way to divide it into a finite number of triangles. Let us pick a random triangulation uniformly among all those with a fixed size and genus. What can be said about the behaviour of these random geometric objects when the size gets large? We will investigate three different regimes: the planar case, the regime where the genus is not constrained, and the one where the genus is proportional to the size. Based on joint works with Baptiste Louf, Nicolas Curien and Bram Petri.

- Read more about Random discrete surfaces
- 321 reads

## Explicit results about primes in Chebotarev's density theorem

Let $L/K$ be a Galois extension of number fields with Galois group $G$, and let $C⊂G$ be a conjugacy class. Attached to each unramified prime ideal p in OK is the Artin symbol $\sigma p$, a conjugacy class in $G$. In 1922 Chebotarev established what is referred to his density theorem (CDT). It asserts that the number $\pi C(x)$ of such primes with $\sigma p=C$ and norm $Np≤x$ is asymptotically $\left|C\right|\left|G\right|\mathrm{Li} (x)$ as $x\rightarrow\infty$ where $\mathrm{Li} (x)$ is the usual logarithmic integral. As such, CDT is a generalisation of both the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions. In light of Linnik's result on the least prime in an arithmetic progression, one may ask for a bound for the least prime ideal whose Artin symbol equals C. In 1977 Lagarias and Odlyzko proved explicit versions of CDT and in 1979 Lagarias, Montgomery and Odlyzko gave bounds for the least prime ideal in the CDT. Since 2012 several unconditional explicit results of these theorems have appeared with contributions by Zaman, Zaman and Thorner, Ahn and Kwon, and Winckler. I will present several recent results we have proven with Das, Ng, and Wong.

## Regular Representations of Groups

A natural way to understand groups visually is by examining objects on which the group has a natural permutation action. In fact, this is often the way we first show groups to undergraduate students: introducing the cyclic and dihedral groups as the groups of symmetries of polygons, logos, or designs. For example, the dihedral group $D_8$ of order 8 is the group of symmetries of a square. However, there are some challenges with this particular example of visualisation, as many people struggle to understand how reflections and rotations interact as symmetries of a square.

Every group G admits a natural permutation action on the set of elements of $G$ (in fact, two): acting by right- (or left-) multiplication. (The action by right-multiplication is given by $\left{t_g : g \in G\right}, where $t_g(h) = hg$ for every $h \in G$.) This action is called the "right- (or left-) regular representation" of $G$. It is straightforward to observe that this action is regular (that is, for any two elements of the underlying set, there is precisely one group element that maps one to the other). If it is possible to find an object that can be labelled with the elements of $G$ in such a way that the symmetries of the object are precisely the right-regular representation of $G$, then we call this object a "regular representation" of $G$.

A Cayley (di)graph $Cay(G,S)$ on the group $G$ (with connection set $S$, a subset of $G$) is defined to have the set $G$ as its vertices, with an arc from $g$ to $sg$ for every $s$ in $S$. It is straightforward to see that the right-regular representation of $G$ is a subset of the automorphism group of this (di)graph. However, it is often not at all obvious whether or not $Cay(G,S)$ admits additional automorphisms. For example, $Cay(Z_4, {1,3})$ is a square, and therefore has $D_8$ rather than $Z_4$ as its full automorphism group, so is not a regular representation of $Z_4$. Nonetheless, since a regular representation that is a (di)graph must always be a Cayley (di)graph, we study these to determine when regular representations of groups are possible.

I will present results about which groups admit graphs, digraphs, and oriented graphs as regular representations, and how common it is for an arbitrary Cayley digraph to be a regular representation.

## Combinatorial Matrices

Matrices contain combinatorial information. They may provide alternative representations of combinatorial ideas. Examples include permutation matrices as representations of permutations of a finite set, and adjacency matrices as representations of a finite graph. The linear algebraic properties of these matrices may provide useful combinatorial information, and combinatorial information about a matrix may impact its linear algebraic properties. At the same time, some combinatorial constructs are defined by matrices. A notable example is the alternating sign matrices which arise in a number of ways including from the partial order on permutations called the Bruhat order. In this talk we will explore various connections between combinatorics and matrices, combinatorial matrices.

- Read more about Combinatorial Matrices
- 2794 reads

## Sparse - Dense Phenomena

The dichotomy between sparse and dense structures is one of the profound, yet fuzzy, features of contemporary mathematics and computer science. We present a framework for this phenomenon, which equivalently defines sparsity and density of structures in many different yet equivalent forms, including effective decomposition properties. This has several applications to model theory, algorithm design and, more recently, to structural limits.

- Read more about Sparse - Dense Phenomena
- 2857 reads

## Small Number and the Basketball Tournament

The mathematical context of the third story, Small Number and the Basketball Tournament, contains some basic principles of combinatorics. The plot of the story and the closing question are structured in a manner that allows the moderator to introduce the notion of permutations and combinations. Since the numbers used in the story are relatively small, this can be used to encourage the young audience to explore on their own. Mathematics is also present in the background. Small Number and his friends do mathematics after school in the Aboriginal Friendship Centre. He loves playing the game of Set and when he comes home his sister is just finishing her math homework. Small Number and his friend would like to participate in a big half-court tournament, and so on.

For more details see http://mathcatcher.irmacs.sfu.ca/content/small-number

## Hyperplane Arrangements and Applications

Some photos from the Hyperplane Arrangements and Applications conference which took place at UBC Vancouver, August 8-12. This conference was held in honour of Hiroaki Terao.