Organizers: David
Gunderson and Karen Gunderson

Time: Fridays 3:30pm

Room: 415 Machray Hall

Topics including graphs and hypergraphs, algebraic graph theory, finite geometries, random processes, extremal or Ramsey theory, applications of combinatorics, combinatorial geometry, partial orders, design theory, combinatorial matrix theory, additive combinatorics.

Talks can be surveys, works in progress, introductions to an area, or recent results. All are welcome to attend and to volunteer talks. Talks should be aimed at a wide audience of combinatorialists and should be understandable to graduate students.

Subscription to the calendar is available via: https://www.google.com/calendar/ical/4aq25ijhgs0tb19k9cni79ucps%40group.calendar.google.com/public/basic.ics

Schedules for past seminars are available here.

Date | Speaker | Title |
---|---|---|

12 Jan 2018 | Michal Przykucki | Parking on a random tree |

19 Jan 2018 | No Seminar | |

26 Jan 2018 | Michael Doob | Seeing the rank of a matrix |

2 Feb 2018 | William Kocay | The Configurations (13_3) |

9 Feb 2018 | Bob Quackenbush | Rectangular powers and Ramsey theory |

16 Feb 2018 | Amy Shaw | Fast percolation |

23 Feb 2018 | No Seminar | Reading week |

2 Mar 2018 | No Seminar | |

9 Mar 2018 | Shonda Gosselin (UW) | Metric Dimension of Circulant Graphs and Cayley Hypergraphs |

16 Mar 2018 | Amy Shaw | Orienting wide partitions |

23 Mar 2018 | No Seminar | Faculty of Science lecture series |

30 Mar 2018 | No Seminar | University closed -- Good Friday |

6 Apr 2018 | No Seminar | Faculty of Science lecture series |

**Speaker**: Michal Przykucki

**Title**: Parking on a random tree

**Abstract: **
Consider the following problem, introduced in 1966 as a model of a
simple protocol to resolve collisions in hashing functions. Let T be a
rooted tree on n vertices (e.g., a directed path) with edges directed
towards the root. We imagine that each node of T has space for a
single car to park. A number m of cars arrive one by one, each at a
node chosen independently and uniformly at random. If a car arrives at
a space which is already occupied, it follows the unique path oriented
towards the root until it encounters an empty space, in which case it
parks there; if there is no empty space, it leaves T and the protocol fails.

We discuss some new results in the case when T is random. Joint work with Christina Goldschmidt.

**Speaker**: Michael Doob

**Title**: Seeing the rank of a matrix

**Abstract: **
Matroids have several equivalent definitions. One involves the definition of independent sets and while another uses the structure of cycles. It is this duality that allows some algebraic properties of graphs to be viewed geometrically. We'll see how this works. As an example, we'll look at the "geometry" of the rank of the incidence matrix of a graph.

**Speaker**: William Kocay

**Title**:The Configurations (13_3)

**Abstract: **
Grunbaum has conjectured that every configuration (n_3)
that can be drawn in the plane with straight lines can be
drawn with rational coordinates. There are 2036
configurations (13_3). We show how to coordinatize
all of them with rationals. Elliptic curves make
an appearance.

**Speaker**: Bob Quackenbush

**Title**: Rectangular powers and Ramsey theory

**Abstract: **
For a finite structure $A$ (e.g., a graph, poset, group, or lattice),
let its set of finite powers be $Pow(A) = \{A^n | n \geq 0\}$ with
$P_{m,n}(A)$ the set of all substructures of $A^n$ isomorphic to
$A^m$.

Choose positive integers $n, m, k, c$ with $n > m > k$. Then we call
an onto map $\Delta: P_{k,n}(A) \to [c] = \{1,...,c\}$ a
*$c$-colouring*. We seek $B \in P_{m,n}(A)$ such that the
restriction of $\Delta$ to $\{C \in P_{k,m}(A) | C \subseteq B \}$ is
constant; such a $B$ is said to be *monochromatic* with respect
to $\Delta$.

I will discuss the positive and negative results of this quest, couched in the language of rectangular powers and polymorphism clones.

See abstract: here

**Speaker**: Amy Shaw

**Title**: Fast percolation

**Abstract: **
Given a graph $G$ and a positive integer $r$, the $r$-neighbor bootstrap percolation process on $G$ is defined in the following way:
A subset $A \subset V(G)$ of vertices is initially infected, and any
vertex outside $A$ is healthy. We then successively infect each
healthy vertex that has at least $r$ infected neighbours. If every
vertex is eventually infected, say that $A$ percolates.

Bootstrap percolation has been the subject of much study in both the probabilistic and deterministic models, in particular on the grid $[n]^2$. The maximum time to percolation in $[n]^2$ has been determined precisely and in this talk, I will present some new results on how quickly a 'small' initial configuration can percolate.

This talk is based on joint work with Stefan David.

**Speaker**: Shonda Gosselin (UW)

**Title**: Metric Dimension of Circulant Graphs and Cayley Hypergraphs

**Abstract: **
A pair of vertices $x$ and $y$ in a graph (or hypergraph) $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset of its vertices $W$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the \emph{metric dimension} of $G$. The problem of determining the metric dimension of a graph is known to be NP-hard (Khuller et al 1994). The metric dimension of a graph has applications in network discovery and verification, combinatorial optimization, chemistry, and many other areas, and consequently this graph parameter has received a great deal of attention from researchers, the main goal being to determine the metric dimension of certain classes of graphs or to achieve asymptotic bounds. In particular, there is great interest in finding classes of graphs whose metric dimension does not grow with the number of vertices. Such graphs are said to have bounded metric dimension. In this talk, we bound the metric dimension of Cayley hypergraphs on finite Abelian groups with the canonical set of generators, and we show that the metric dimension of these hypergraphs is equal to the metric dimension of a Cartesian product of a circulant graphs of the form $C_n(1,2,\ldots,t)=Cay(\mathbb Z_n:\{\pm 1,\pm 2,\ldots,\pm t\})$. These circulant graphs have bounded metric dimension (Grigorious et al 2014). In fact, their metric dimension is determined by the congruence class of $n$ modulo $2t$. We present some background on the problem and some new results. We also bound the metric dimension of Cartesian products of these circulants, which yields bounds on the metric dimension of the corresponding Cayley hypergraphs. This is joint work with my students Adam Borchert and Kevin Chau.

**Speaker**: Amy Shaw

**Title**: Orienting wide partitions

**Abstract: **
Latin squares are square arrays filled with symbols so that every symbol appears exactly once in each row and column. For example, Cayley tables and sudoku solutions are Latin squares. While it is simple to construct a Latin square with $n$ symbols on a square array of size $n$, construction of Latin squares can become difficult when further constraints are imposed. Dinitz's conjecture, which was confirmed by Galvin, relates to the existence of Latin squares when different cells have different sets of available symbols, Rota's basis conjecture pertains to the problem when the symbols are vectors and rows/columns must be linearly independent, and the wide partition conjecture addresses the problem for shapes other than square arrays. I will discuss these problems and conjectures and my recent results on the wide partition conjecture. Based on joint work with Ping Kittipassorn.