Combinatorics Seminar

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.

Extremal C15-free graph

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.


Winter 2018 Schedule

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

Graph with every pair of vertices having
exactly 2 common neighbours

Abstracts

12 January 2018, 3:30 pm, 415 Machray Hall

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.

26 January 2018, 3:30 pm, 415 Machray Hall

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.

2 February 2018, 3:30 pm, 415 Machray Hall

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.

9 February 2018, 3:30 pm, 415 Machray Hall

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

16 February 2018, 3:30 pm, 415 Machray Hall

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.

9 March 2018, 3:30 pm, 415 Machray Hall

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.

16 March 2018, 3:30 pm, 415 Machray Hall

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.