University of Victoria

In this talk we consider the oriented colouring problem for graphs with bounded Euler genus. That is we consider the smallest $k$ such that all oriented graphs embeddable on surfaces of Euler genus at most $g$ necessarily have an oriented...

Lifting theorems have played a key role in many recent breakthrough results in diverse areas of theoretical cs and mathematics via simple yet profound connections between these areas and communication complexity. A typical lifting theorem translates...

The word complexity function p(n) of a subshift X measures the number of n-letter words appearing in sequences in X, and X is said to have linear complexity if p(n)/n is bounded. It's been known since work of Ferenczi that linear word complexity...

Let q=1 mod 4 be a prime power and let F_q be the finite field of q elements. The Paley graph of order q is the graph with vertex set F_q, such that two vertices are adjacent if and only if their difference is a square in F_q. Paley graphs play an...

Since suggested by Tur\'an in 1941, determining the Tur\'an density of hypergraphs has been a notoriously difficult problem at the center of extremal combinatorics. Subsequently, several natural variants of this problem have been suggested, most...

Suppose a graph G has list chromatic number k. It is easy to see that if L is a (k+1)-list assignment for G, then G admits two L-colourings f and g where f(v) =/= g(v) for every vertex v in the graph. But what if we want still more disjoint L...

We consider an arbitrary sequence of d*d matrices (A_n) of norm at most 1 and subject them to noiselike perturbations of size epsilon. We show that the perturbed system has simple Lyapunov spectrum (no repeated exponents) and discuss universal bounds...

I will talk about the `minimal spanning arborescence', a directed version of the Minimal spanning tree. I will explain how this naturally leads to a new type of stochastic process which we call `loop contracting random walk'. I will show how this can...

In 1974 Erdős and Rothschild asked the following question: given integers k, s and a large n, what is the maximum number of s-edge-colourings of an n-vertex graph free of a monochromatic k-vertex clique? A follow up question is to determine which...

Measuring the serial dependence across time is critical in model identification and diagnosis in time series (TS) analysis. In classic TS analysis, the autocorrelation function is perhaps the most widely used method to examine the temporal...