# Past Combinatorics Seminars

List of past schedules for the University of Manitoba Combinatorics Seminar.

## 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

## 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.

## Fall 2017 Schedule

Date Speaker Title
15 Sep 2017 David Gunderson Some of my favourite problems in combinatorial geometry
22 Sep 2017 Sergei Tsaturian Survey of Euclidean Ramsey Theory
29 Sep 2017 Karen Gunderson Sets with no 3-term arithmetic progressions
6 Oct 2017 No Combinatorics Seminar Thanksgiving break
20 Oct 2017 No Combinatorics Seminar Facutly of Science lecture series
27 Oct 2017 Ranganathan Padmanabhan Elliptic Curves in Combinatorics
3 Nov 2017 Avery Miller (CS) Treasure Hunting in Graphs Without a Map
10 Nov 2017 Amy Shaw Catching a fast robber
17 Nov 2017 No Combinatorics Seminar Faculty of Science lecture by Charles Colbourn
24 Nov 2017 Anthony Bonato (Ryerson) Burning spiders and path forests
1 Dec 2017 Shahin Kamali (CS) $k$-server problems: a review of the old results and recent developments
8 Dec 2017 Andrii Arman The crossing number of a graph

## Abstracts

### 15 September 2017, 3:30 pm, 418 Machray Hall

Speaker: David Gunderson
Title: Some of my favourite problems in combinatorial geometry

Abstract: The purpose of this talk is to popularize some problems or theorems from combinatorial geometry. For example, I will look at the Heilbronn problem, Monsky's theorem, Minkowski's theorem, and some recent results in Euclidean Ramsey theory. Here are a few motivating questions:

1. Place 5 points in a unit square, no three of which are collinear, and look at the 10 triangles thereby determined. How can these 5 points be placed so that the minimum area of any triangle is maximized?
2. Can a square be partitioned into 5 triangles of equal area? Does number theory hold the answer?
3. Can results in convex geometry be used to obtain number-theoretic results?
4. If points in a Euclidean space are coloured either red or blue, what patterns in one colour can be guaranteed?
This talk is for a general audience.

### 22 September 2017, 3:30 pm, 418 Machray Hall

Speaker: Sergei Tsaturian
Title: Survey of Euclidean Ramsey Theory

Abstract:

### 29 September 2017, 3:30 pm, 418 Machray Hall

Speaker: Karen Gunderson
Title: Sets with no 3-term arithmetic progressions

Abstract: This is a survey talk in the area of additive combinatorics on the maximum size of sets in $\mathbb{Z}_n$ or $\mathbb{Z}_p^n$ with no arithmetic progressions. I will survey results in the area and sketch the proofs of some of the bounds on the sizes of these sets, including the bounds obtained by Fourier analysis and recent bounds using a polynomial method. This talk is for a general audience.

### 27 October 2017, 3:30 pm, 418 Machray Hall

Title: Elliptic Curves in Combinatorics

Abstract: The adjective 'elliptic' in the above title comes from the so-called elliptic functions which arise from the problem of finding the arc length of an ellipse. Thus the origin of elliptic curves lies in complex analysis. However, the topic has penetrated many fundamental areas of mathematics including algebra, number theory, geometry, cryptography, combinatorics and even physics. In this talk, I will go through some typical examples and sketch the proofs illustrating the applications of elliptic curves in finite geometries and combinatorics. This talk is for a general audience.

References

1. Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Block configurations on real cubic curves. J. Combin. Theory Ser. A 58 (1991), no. 1, 131-135
2. Mendelsohn, N. S.; Padmanabhan, R.; Wolk, B. Designs embeddable in a plane cubic curve. Note de Mat. (Italy) 7 (1987), no. 1, 113-148.

### 3 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Avery Miller
Title: Treasure Hunting in Graphs Without a Map

Abstract: A mobile agent starts somewhere in an arbitrary graph, and traverses edges until it finds the single node in the graph that contains a treasure. The difficulty is, the agent doesn’t have a map of the graph. A further difficulty is that the nodes of the graph are not labeled, and the agent cannot leave marks or breadcrumbs to remember where it has been. At each time step, the agent is located at a node v, can only see the edges incident to this node, and these edges are labeled 0,…,deg(v)-1. In this talk, I will present some results that describe the relationship between: (i) how much information the agent knows about the graph, a priori, and (ii) the number of traversals used by the agent to find the treasure. On the one hand, we will look at a search strategy that works with limited information, and on the other hand, we will look at impossibility results of the form "if the agent must find the treasure within T steps, you must give the agent at least f(T) bits of information about the graph, no matter which strategy it uses".

### 10 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Amy Shaw
Title: Catching a fast robber

Abstract: The game of Cops and Robbers is played on a graph by a set of cops and one robber. The game begins with the cops being placed onto vertices of their choice in $G$ and then the robber, being fully aware of the placement of the cops, positions himself on a vertex of his choosing. They then take turns moving along the edges of the graph, starting with the cops. During their turn, each cop may move to an adjacent vertex, or remain stationary, and the same goes for the robber. We also allow multiple cops to occupy the same vertex. The cops win if at some time there is a cop at the same vertex as the robber; otherwise, the robber wins. The minimum number of cops for which the cops have a winning strategy, no matter how the robber plays, is called the cop number of $G$. Our focus is on a variant on the $n \times n$ grid in which the robber may move faster than the cops, i.e. the robber may traverse several edges in one turn. We provide upper and lower bounds on the cop number for this version of the game.

### 24 November 2017, 3:30 pm, 418 Machray Hall

Speaker: Anthony Bonato (Ryerson)
Title: Burning spiders and path forests

Abstract: Graph burning is a simplified model for the spread of memes and contagion in social networks. A fire breaks out in each time-step and spreads to its neighbours. The burning number of a graph measures the number of time-steps it takes so that all vertices are burning. While it is conjectured that the burning number of a connected graph of order n is a most the ceiling of the square root of n, this remains open in general.

We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests.

### 1 December 2017, 3:30 pm, 418 Machray Hall

Speaker: Shahin Kamali
Title: $k$-server problems: a review of the old results and recent developments

Abstract: k-server problem is a classic problem in the context of competitive analysis. Given an undirected graph and a sequence of requests to vertices of the graph, the goal is to move k servers in way that at least one server is present at each request and the total distance moved by servers is minimized. At the heart of the k-server problem lies the k-server conjecture, which states that there is a deterministic algorithm with competitive ratio of exactly k. In the first half of this talk, we review the existing results with respect to the k-server conjecture. This will include a lower bound for competitive ratio of deterministic algorithms, particular case of trees, and also the work-function algorithm which is conjectured to answer the k-server conjecture in the affirmative. In the past few years, there has been efforts to study k-server problem using alternative settings. One of them is advice model where the online constraint is relaxed and an online algorithm receives partial information about the input sequence. In the second part of the talk, we review the existing results on the advice complexity of the k-server problem. We conclude with discussing a few open problems.

### 8 December 2017, 3:30 pm, 418 Machray Hall

Speaker: Andrii Arman
Title: The crossing number of a graph

Abstract: A graph $G$ is called "planar" if $G$ can be drawn in the plane so that no edges cross. It is known that the graphs $K_5$ and $K_{3,3}$ are not planar. For a graph $H$ that is not planar, one can measure the "non-planarity" by counting its "crossing number", the minimum number of edge crossings required in any drawing of $H$ in the plane.

This talk surveys some facts about crossing numbers and their variants, some basic inequalities, and applications.

## Winter 2017 Schedule

Date Speaker Title
13 Jan 2017 No Combinatorics Seminar UW Seminar by Karen Meagher on "Cocliques in Derangement Graphs" (1L06 Lockhart Hall)
20 Jan 2017 Avery Miller (Computer Science) Cover-Free Families of Sets with Applications
27 Jan 2017 Sergei Tsaturian Some results in asymmetric Euclidean Ramsey theory
3 Feb 2017 Julien Arino Some applications of graph theory to math biology
10 Feb 2017 Karen Gunderson Independence density in graphs and hypergraphs
17 Feb 2017 Narad Rampersad (UW) Computer Proofs of Results in Combinatorics on Words
24 Feb 2017 No Combinatorics Seminar Reading Week
17 Mar 2017 Andrii Arman An upper bound on the size of a $k$-uniform intersecting hypergraph with cover number $k$.
24 Mar 2017 No Combinatorics Seminar Faculty of Science Big Data Revolution talk at 3:00 pm
31 Mar 2017 Colin Desmarais A history of partition regularity on the integers
7 Apr 2017 Rob Craigen The double core and duality
14 Apr 2017 No Combinatorics Seminar Good Friday
21 Apr 2017 Ortrud Oellermann (UW) On Mean Subtree Orders of Trees

## Abstracts

### 20 January 2017, 3:45 pm, 111 Armes

Speaker: Avery Miller (CS)
Title: Cover-Free Families of Sets with Applications

Abstract: A k-cover-free family of sets has the property that no set in the family is contained in the union of k of the other sets. These families can be used to solve certain puzzles that involve quickly finding a 'defect' in a large collection, such as finding a counterfeit coin using a scale, a diseased soldier using blood tests, or a poisoned bottle of wine using rats. These puzzles all fall under the umbrella of "combinatorial group testing". In this talk, I will give an introduction to cover-free families and the above examples, and then discuss a very different application: solving communication tasks in wireless networks. On the one hand, we can get efficient algorithms by using cover-free families when specifying radio transmission schedules, and on the other hand, we can prove lower bounds for certain tasks by showing that every algorithm produces a sequence of radio transmissions that corresponds to a cover-free family. If there is time, I will discuss an extension of cover-free families that includes an additional "thickness" parameter: this takes into account how many times a set is covered by the union of k other sets in the family. This extension allows us to solve a more general class of group testing problems, and gives more general results about communication in wireless networks. The talk will be self-contained, e.g., no familiarity with wireless network algorithms will be assumed.

### 27 January 2017, 3:30 pm, 111 Armes

Speaker: Sergei Tsaturian
Title: Some results in asymmetric Euclidean Ramsey theory

Abstract: A typical question in Euclidean Ramsey theory has the following form: is it true that for any colouring of Euclidean space E^n into two (or more) colours there exists a monochromatic copy of some fixed geometric configuration F? I will focus on the asymmetric version of this question - is it true that for any colouring of E^n in red and blue, there exists either a blue copy of F_1 or a red copy of F_2?

Most of the questions in this field are very easy to state, but even some simplest cases are still open. I will give a brief overview of known results. I will also present our recent result with Andrii Arman, that deals with the case of E^3, F_1 being the configuration of two points at distance 1 to each other, and F_2 being 6 points on a line with distance 1 between consecutive points.

### 3 February 2017, 3:30 pm, 111 Armes

Speaker: Julien Arino
Title: Some applications of graph theory to math biology

Abstract: Graph theory plays an important role in mathematical biology for a variety of reasons. Graphs, in particular directed graphs, help formalize the interactions between state variables. The structure of interaction graphs further determine the range of behaviours a model exhibits. Graphs also provide a means for describing some spatial processes such as those occurring in the spread of epidemics. I will present several examples illustrating the rich interconnection between graph theory and mathematical biology.

### 10 February 2017, 3:30 pm, 111 Armes

Speaker: Karen Gunderson
Title: Independence density in graphs and hypergraphs

Abstract: A set of vertices in a graph or hypergraph is said to be independent if it contains no edges. Of interest in this talk are the size, number, and distribution of the independent sets in hypergraphs. Relationships between these and other parameters can provide insight to applications not only from graph theory, but also to additive combinatorics and the hard-core model from statistical physics. In the case of infinite hypergraphs, one can also ask for a measure of the density of independent sets: if each vertex is chosen independently with a fixed probability, what is the probability that the selected set is independent? I will give some history on this topic and present new results on sets of real numbers that are the independence density of some countably infinite hypergraph. This is joint work with P. Balister and B. Bollobás.

### 17 February 2017, 3:30 pm, 111 Armes

Title: Computer Proofs of Results in Combinatorics on Words

Abstract: One of the main topics in combinatorics on words is the avoidability of patterns. An example of a pattern is XX, which denotes two consecutive repetitions of the same sequences of letters: for instance "tartar". Thue (1906) constructed an infinite word using just three symbols that contains no occurrence of XX. He also constructed an infinite word on two symbols that avoids XXX. Around 1979/80 mathematicians began to consider words avoiding patterns on several variables, such as XYZXZY. In most cases, if a pattern can be avoided, the typical way to construct a word avoiding it is by iterating a morphism of the free monoid: e.g., to avoid XXX, iterate the substitution rule 0 → 10, 1 → 10. This generates an infinite set of words avoiding XXX. However, the proof in each case is often an ad hoc argument based on the specific morphism used and the pattern to be avoided. In recent years, a computer algorithm has been developed that automates such proofs: provide the morphism and a description (in first order logic) of the pattern to be avoided, and the computer algorithm will produce a certificate that the words generated by the morphism avoid the pattern. We will give an overview of the method and some recent results proved with it.

### 17 March 2017, 3:30 pm, 111 Armes

Speaker: Andrii Arman
Title: An upper bound on the size of a $k$-uniform intersecting hypergraph with cover number $k$.

Abstract: A $k$-uniform hypergraph $F$ is called intersecting iff any two hyperedges of $F$ have non-empty intersection. A subset $C$ of vertices of $F$ is a called a cover of $F$ iff every hyperedge of $F$ intersects with $C$. The size of the smallest cover of $F$ is called the cover number of $F$. Define $r(k)$ to be the maximum size (number of hyperedges) of an intersecting $k$-uniform hypergraph $F$ with cover number $k$.

In 1975, Erdős and Lovász proved that $r(k)$ cannot exceed $k^k$. In this talk I will present the proof idea for an upper bound of order $k^{k-1}$ based on a Chooser-Guesser game played on a hypergraph $F$. This talk is based on a joint work with Troy Retter.

### 31 March 2017, 3:30 pm, 111 Armes

Speaker: Colin Desmarais
Title: A history of partition regularity on the integers

Abstract: What is today called arithmetic Ramsey theory has its origins with Hilbert's cube lemma of 1892, Schur's theorem of 1916, and van der Waerden's theorem of 1927; all of which predate Ramsey's publication of his now famous theorem in 1930. These results guarantee a monochromatic solution to a particular system of equations in any finite colouring of the positive integers: for example, Schur's theorem states that every finite colouring of the positive integers has a monochromatic solution to $x+y=z$. Such an equation or system of equations is called partition regular.

In this talk I will give an overview of early results in arithmetic Ramsey theory, including Rado's 1933 characterization of partition regular systems. I will also discuss Deuber's proof in 1973 of a conjecture of Rado's that in any finite colouring of the positive integers some colour class contains solutions to every partition regular system. Finally, I will briefly state results in infinite and nonlinear partition regular systems.

### 7 April 2017, 3:30 pm, 111 Armes

Speaker: Rob Craigen
Title: The double core and duality: where generalized Hadamard matrices, generalized weighing matrices and projective planes meet.

### 21 April 2017, 3:30 pm, 111 Armes

Speaker: Ortrud Oellermann
Title: On Mean Subtree Orders of Trees

Abstract: The study of the mean subtree order of a given tree was initiated in a 1983 paper of Jamison. While the structure of trees of a given order with minimum mean subtree order have been characterized, the problem of describing trees of a given order with maximum mean subtree order is still largely open. This talk begins with an overview of known results followed by recent results on trees of maximum subtree order within certain classes of trees. (New results are joint work with Lucas Mol.)

## Fall 2016 Schedule

Date Speaker Title
9 Sep 2016 Rob Craigen (Manitoba) Algebraic design theory - Part 2
23 Sep 2016 Michael Szestopalow (Manitoba) Matchings and Covers in Hypergraphs
30 Sep 2016 Karen Gunderson (Manitoba) Percolation and infinite trees
14 Oct 2016 David Gunderson A result in finite projective planes used for dimension theory of posets
21 Oct 2016 Ranganathan Padmanabhan (Manitoba) Term Spectra and their Minimal Extensions
4 Nov 2016 Asha Rao (RMIT) Low-density Parity-check codes (Room change: 3M63 at the University of Winnipeg)
25 Nov 2016 Andrii Arman and Sergei Tsaturian Maximum number of cycles in a graph
2 Dec 2016 Bob Quackenbush Ramsey Clones

## Abstracts

### 9 September 2016, 3:30 pm, 111 Armes

Speaker: Rob Craigen
Title: Algebraic design theory - Part 2

Abstract: Part 2 of talk from 8 April 2016.

Warwick de Launey pondered a series of ideas about how to create a basic framework for designs that would capture the entirety of the field using higher analytic tools more than case-by-case analysis, placing the entire field onto some common framework. He decided that the fundamental concept making the field what it is was a sort of "orthogonality" based on the pairwise relationship between two rows in an array of symbols. In the last 5 years of his life he developed these rudimentary ideas, with coauthor Dane Flannery, into an overarching theory in which algebra plays the part of an "engine" driving the various objects that arise in the theory and setting out pathways along which a panoply of other, even as-yet undiscovered, objects may be explored.

de Launey passed away to cancer in 2010 just as their book was still being completed. A couple of years later I had the privilege of writing its Math Review. Later, in 2014 I visited for 3 months with Flannery to discuss the development of ideas in the book, open questions that arise, and what future directions suggest themselves based on its framework.

In this talk I will survey the basic elements of the setup of Algebraic Design Theory, its key theorems and what, to me, are some of the more obvious deficiencies (and merits) of this approach. We will see some open questions.

### 23 September 2016, 3:30 pm, 111 Armes

Speaker: Michael Szestopalow
Title: Matchings and Covers in Hypergraphs

Abstract: A matching of a hypergraph H is a set of pairwise disjoint edges of H and a cover of H is a set of vertices that meets every edge of H. The well-known Konig-Egervary Theorem says that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum cover. We will consider similar results for hypergraphs. In particular, we will discuss problems and results related to conjectures of Ryser and Tuza.

### 30 September 2016, 3:30 pm, 111 Armes

Speaker: Karen Gunderson
Title: Percolation and infinite trees

Abstract: A bootstrap process is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: `healthy' or 'infected'. For any positive integer r, the r-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least r infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected.

Of interest is the random case, where each vertex is infected independently with a fixed probability p. For an infinite graph, one would like to know the values of p for which the probability of percolation is positive. I will give some of the history of this problem for infinite trees and present some new results on the possible values of critical probabilities for such processes on Galton-Watson trees.

This talk is based on joint work with Bollobás, Holmgren, Janson, and Przykucki.

### 14 October 2016, 3:30 pm, 111 Armes

Speaker: David Gunderson
Title: A result in finite projective planes used for dimension theory of posets

Abstract: A few weeks ago, at the 6th PCC in Poland, I attended a talk by Tom Trotter about posets. He mentioned a paper by Biró, Hamburger, Pór, and himself, where finite projective planes (FPPs) were used to produce a certain family of posets, thereby proving something about dimension of posets. Csaba Biró was at the conference, and it turned out that we shared a taxi to the airport. So I asked him about how FPPs fit into their work. He gladly gave me a minilecture. One result really caught my eye, and so I want to share it:

Theorem [BHPT, 2016]: Let Π be a FPP of order q, let X be a set of points in Π, and let Y be a set of lines in Π, each containing no point of X. Then |X| ⋅ |Y| ≤ q3.

I will give (or at least outline) two similar proofs of the above theorem, one of which was sent to me by Csaba just a few days ago. Both proofs use double counting (or some call it quadratic counting), and is very similar to the 1975 Bruen-Silverman proof for blocking sets.

If time allows, I hope to also give some idea as to how the above theorem translates into one about "standard examples" in posets and dimension theory. Instead of using incidences in FPPs (as is often the case in graph theory), their poset uses "anti-incidence".

### 21 October 2016, 3:30 pm, 111 Armes

Title: Term Spectra and their Minimal Extensions

Abstract: For an algebra A, let pn(A) denote the number of essentially n-ary term functions - that is those n-ary operations which are derived or generated from the basic operations of the algebra and which depend on all n variables. The pn-sequence of A is the integer sequence

p(A) = {p0(A), p1(A),...,pn(A),..}.

One can easily determine the free spectrum of the algebra from the sequence p(A) by a well-known combinatorial formula. In this talk, we give typical examples of the term spectra, their minimal extensions and the free spectra of certain equational classes which one often comes across in algebras and finite geometries.

References

1. G. Grätzer and R. Padmanabhan, On idempotent, commutative and non-associative groupoids. Proc. Amer. Math. Soc 28 (1971) 75-80.
2. G. Grätzer and A. Kisielewicz, A survey of some open problems on pn-sequences and the free spectra of algebras and varieties, Universal algebra and quasigroup theory, Haldermann Verlag, Berlin 1992, 57-88.
3. J. Dudek, Affine spaces over GF(3), Studia Logica 72 (2002), 363-366.
4. R. Padmanabhan, Free spectrum of shelf algebras, Rings and Modules Seminar, University of Manitoba, 06 October, 2015 (unpublished).

### 4 November 2016, 3:30 pm, 3M63 at the University of Winnipeg (not the usual location!)

Speaker: Asha Rao
Title: Low-density Parity-check codes

Abstract: Low-density parity-check codes were first discovered by Robert Gallager in 1962, and then left unnoticed for the next 30 years, until they were re-discovered in the 1990s by McKay and Neal. The main attraction of these codes is their ability to achieve rates close to the Shannon limit. The codes originally designed by Gallagher were pseudorandom and good LDPC codes were found mainly by computer searches. I will describe these codes and why there are of interest, and then give some insight into some, more recently discovered ways of constructing these codes from combinatorial structures.

### 25 November 2016, 3:30 pm, 111 Armes

Speaker: Andrii Arman and Sergei Tsaturian
Title: Maximum number of cycles in a graph

Abstract: A problem of bounding the number of cycles in a graph is more than a century old. In 1897, Ahrens gave bounds on the number of cycles using the cyclomatic number. Since then, there have been many results about maximum number of cycles for a graph with fixed number vertices, fixed cyclomatic number, and other restrictions.

In this talk we consider a question of determining the maximum number of cycles over two different classes of graphs: graphs with fixed average degree and graphs with fixed number of edges. Results of our recent joint work show that for both cases maximum number of cycles in a graph has bounds exponential in the number of edges of a graph. We will also present the solution of similar problems for multigraphs.

### 2 December 2016, 3:30 pm, 111 Armes

Speaker: Bob Quackenbush
Title: Ramsey Clones

Abstract: This is an introductory talk about Ramsey theory centered around the concept of a parameter set. It will be phrased in the language of universal algebra and, in particular, the concept of a clone of functions (a set of functions closed under composition of functions).

## Winter 2016 Schedule

Date Speaker Title
29 Jan 2016 Ranganathan Padmanabhan (Manitoba) Sylvester-Gallai Configurations
12 Feb 2016 Sergei Tsaturian (Manitoba) Triangle-free graphs with the maximum number of cycles
26 Feb 2016 Stephane Durocher (Manitoba) The locality of route-finding in a graph
11 Mar 2016 Rob Craigen (Manitoba) Survey of negacyclic weighing matrices
1 Apr 2016 Steve Kirkland (Manitoba) Kemeny's Constant and an Analogue of Braess' Paradox for Markov chains
8 Apr 2016 Rob Craigen (Manitoba) Algebraic design theory

## Abstracts

### 29 January 2016, 3:30 pm, 115 Armes

Title: Sylvester-Gallai Configurations

Abstract: A finite set S of points in an affine or a projective plane over a field k is called a Sylvester-Gallai configuration if any line joining a pair of points of S contains at least three points of S. A finite set of collinear points in a plane is SG, called the trivial configuration.The now famous Sylvester-Gallai theorem states that the any SG-configuration in projective or affine plane over the field of all real numbers is trivial. A powerful consequence of this result is that any attempt to draw a non-trivial SG-configuration in the real plane, there must be at least one straight line which is not straight. Most well-known example of this kind is the familiar 7-point Fano configuration where one always gets at least one circle. By way of contrast, there are algebraically closed fields which admit non-trivial SG-configurations. Also, every finite field admits nontrivial SG-configurations (an example given below). In this talk, we will go through some of the proofs and non-trivial examples and also mention some new directions of research being done in this area.
Further details on the talk

### 12 February 2016, 3:30 pm, 115 Armes

Speaker: Sergei Tsaturian
Title: Triangle-free graphs with the maximum number of cycles

Abstract: One of the central questions in extremal graph theory is determining maximal possible number of edges in a graph with given number of vertices that doesn't contain a specific subgraph. Examples of such statements are famous Mantel's and Turan's theorems.
More general questions can be considered - determining how many copies of some fixed subgraphs (or collections of subgraphs) can be there in a graph that satisfies some conditions. I will talk about some results of that kind.
In particular, I will show the result of our recent work with A.Arman and D.Gunderson about maximal number of cycles in a graph that doesn't contain triangles, and discuss possible generalizations and open questions.

### 26 February 2016, 3:30 pm, 115 Armes

Speaker: Stephane Durocher
Title: The locality of route-finding in a graph

Abstract: We examine theoretical bounds on the locality of finding a path between two given nodes in a graph. A local forwarding algorithm A at a vertex v receives a message P and selects one of its neighbours to which to forward P using only local information. Specifically, in addition to knowing the node for which P is destined, algorithm A may also know the node from which P originated, the neighbour from which node v received P, and the subgraph corresponding to all nodes within distance k of node v. Our objective is to determine which of these parameters are necessary and/or sufficient to permit successful message delivery as k varies. We establish tight bounds on k for the feasibility of deterministic k-local path finding for various combinations of these parameters. Although motivated by applications in networks, this work consists of combinatorial and graph-theoretic arguments. This is joint work with Prosenjit Bose and Paz Carmi.

### 11 March 2016, 3:30 pm, 115 Armes

Speaker: Rob Craigen
Title: Survey of negacyclic weighing matrices

Abstract: A square or rectangular matrix is circulant if every row after the first is a right circular shift of its predecessor. Negacyclic matrices are defined the same way except that the first entry of each row is negated after circulating the preceding row. A partial Hadamard matrix is a rectangular kxn (1,-1)-matrix M satisfying MM^T = nI. In the summer of 2013 I hired four sharp undergraduate students to tackle a problem about circulant partial Hadamard matrices. The question of existence of certain negacyclic weighing matrices kept coming up, so we devoted some energy to exploring this largely uncultivated territory. In the end we produced, apparently for the first time, a fairly comprehensive survey of these objects, their structure, why certain classes exist and others cannot. The flavour of the existence questions for this class of weighing matrices is decidedly different from that of group-developed form, even though much of the theory is the same. We discuss some situations in which negacyclic weighing matrices naturally appear, and conclude with some tantalizing new open questions arising from the work.

### 1 April 2016, 3:30 pm, 115 Armes

Speaker: Steve Kirkland
Title: Kemeny's Constant and an Analogue of Braess' Paradox for Markov chains

Abstract: A square matrix that is entrywise nonnegative and has all row sums equal to 1 is called a stochastic matrix, and such matrices play a central role in the study of Markov chains. Given a stochastic matrix A, Kemeny's constant K(A) measures the expected number of steps required for the Markov chain to transition from a given initial state to a randomly chosen final state.

In this talk, we will begin by giving an introduction to Kemeny's constant. We will then go on to explore an analogue of Braess' paradox (wherein adding a road to a network can have the counter-intuitive effect of increasing travel times). Specifically, we will discuss how adding an edge into an undirected graph can increase the value of Kemeny's constant for a certain Markov chain that is naturally associated with the graph.

### 8 April 2016, 3:30 pm, 115 Armes

Speaker: Rob Craigen
Title: Algebraic design theory

Abstract: Warwick de Launey pondered a series of ideas about how to create a basic framework for designs that would capture the entirety of the field using higher analytic tools more than case-by-case analysis, placing the entire field onto some common framework. He decided that the fundamental concept making the field what it is was a sort of "orthogonality" based on the pairwise relationship between two rows in an array of symbols. In the last 5 years of his life he developed these rudimentary ideas, with coauthor Dane Flannery, into an overarching theory in which algebra plays the part of an "engine" driving the various objects that arise in the theory and setting out pathways along which a panoply of other, even as-yet undiscovered, objects may be explored. de Launey passed away to cancer in 2010 just as their book was still being completed. A couple of years later I had the privilege of writing its Math Review. Later, in 2014 I visited for 3 months with Flannery to discuss the development of ideas in the book, open questions that arise, and what future directions suggest themselves based on its framework. In this talk I will survey the basic elements of the setup of Algebraic Design Theory, its key theorems and what, to me, are some of the more obvious deficiencies (and merits) of this approach. We will see some open questions.

## Fall 2015 Schedule

Date Speaker Title
11 Sept 2015 Karen Gunderson (Manitoba) Saturation and graph processes
18 Sept 2015 Andrii Arman (Manitoba) Fibonacci-sum graphs
25 Sept 2015 Ben Li (Manitoba) Minimum total vertex covers and algorithms for computing them
2 Oct 2015 Rob Craigen (Manitoba) Matrices equivalent to their transpose by permutation
9 Oct 2015 Stephane Durocher (Manitoba) Local Geometric Routing in Convex Subdivisions
16 Oct 2015 David Gunderson (Manitoba) Ramsey arrows for induced graphs
23 Oct 2015 Bill Kocay (Manitoba) Constructing Graphs with a High Reconstruction Number
30 Oct 2015 Vaclav Linek (Winnipeg) Polyhedral Designs
6 Nov 2015 Ortrud Oellermann (Winnipeg) Progress on the Oberly-Sumner Conjecture
13 Nov 2015 Colin Desmarais (Manitoba) Norm-graphs and their applications
20 Nov 2015 Sergei Tsaturian (Manitoba) Counting certain subgraphs in a graph and its complement
27 Nov 2015 Bob Quakenbush (Manitoba) Asymptotic philatelic enumeration
4 Dec 2015 Jason Semeraro (Bristol) Hypergraph Turán densities for r-triangles

### 11 September 2015, 3:30 pm, 115 Armes

Speaker: Karen Gunderson
Title: Saturation and graph processes

Abstract: Saturation is a type of extremal problem for graphs and hypergraphs that was introduced by Erdős, Hajnal, and Moon in 1964. A graph G is said to be F-saturated if G contains no copies of F and the addition of any further edge to G creates a copy of F. A more general notion, introduced by Bollobás in 1968 is a weakly F-saturated graph, which is a graph G for which there is an ordering of the non-edges of G so that adding the non-edges one by one to the graph creates a new copy of F at each step. The central question is, for a given graph F and natural number n, what is the fewest number of edges in either an F-saturated or weakly F-saturated graph on n vertices? I will give some of the history of these problems and sketch the proofs of some of the central tools that answer these questions for complete graphs. Finally, I will discuss the edge-adding graph process arising from weak saturation and some of my recent work on this in an Erdős-Rényi random graph.

### 18 September 2015, 3:30 pm, 115 Armes

Speaker: Andrii Arman (Manitoba)
Title: Fibonacci-sum graphs

Abstract: For each positive integer n, the Fibonacci-sum graph Gn is the graph with vertex set V(Gn)= {1,2,..., n} and edge set consisting of those pairs that sum to a Fibonacci number. Properties of Gn were investigated in 2014, when K. Fox, Kinnersley, McDonald, Orlow, and Puleo characterized those n for which Gn has a Hamiltonian path and described all such paths. In this talk I will show other properties of Gn, namely that Gn is connected, bipartite, planar and that the automorphism group of Gn is of order at most 2. This is joint work with Gunderson and Li.

### 25 September 2015, 3:30 pm, 115 Armes

Speaker: Ben Li (Manitoba)
Title: Minimum total vertex covers and algorithms for computing them

Abstract: Let G=(V,E) be a simple, undirected, connected graph with at least two vertices. A total vertex cover (TVC) of G is a vertex cover C of G with the additional property that each connected component of the subgraph of G induced by C contains at least two vertices. The total vertex cover problem is to find a total vertex cover of G of minimum size.
I will show that this problem is NP-Hard, talk briefly about parameterized algorithms for this problem and give an efficient algorithm for finding a minimum-cardinality total vertex cover in a tree. I will conclude with some open problems that I am currently working on.

### 2 October 2015, 3:30 pm, 115 Armes

Speaker: Rob Craigen (Manitoba)
Title: Matrices equivalent to their transpose by permutation

Abstract: We consider the following question: what can be said about matrices M such that PMQ = Mt, where P and Q are permutation matrices (that is, matrices permutation equivalent to their transpose)? In particular, is M permutation equivalent to a symmetric matrix (clearly the converse is true)? These questions arise in combinatorial matrix theory. We show that the answer to the latter question is ''no'', and that if it does not hold for M, then M is permuation equivalent to a matrix which may be nontrivially decomposed into circulant submatrices.

### 9 October 2015, 3:30 pm, 115 Armes

Speaker: Stephane Durocher (Manitoba)
Title: Local Geometric Routing in Convex Subdivisions

Abstract: In various wireless networking settings, node locations and proximity to neighbouring nodes determine a network's topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required O(log n) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).

### 16 October 2015, 3:30 pm, 115 Armes

Speaker: David S. Gunderson (Manitoba)
Title: Ramsey arrows for induced graphs

Abstract: A simple form of Ramsey's theorem says that for any positive integer m, there exists an n = R(m) so that no matter how the pairs of an n-set are partitioned into two colours, some m-subset has all its pairs the same colour. In terms of graphs, this says if the edges of a Kn are 2-coloured, a monochromatic copy of Km (as a subgraph) can always be found. An edge can also be thought of as the graph K2. Such a statement is often expressed in “Ramsey arrow” notation. There have been many generalizations of Ramsey questions for numbers and for graphs. In this survey, the focus is on some of the special situations where induced subgraphs are used instead of just subgraphs.

### 23 October 2015, 3:30 pm, 115 Armes

Speaker: Bill Kocay (Manitoba)
Title: Constructing Graphs with a High Reconstruction Number

Abstract: Ulam's conjecture, also known as the Graph Reconstruction Conjecture, states that the structure of a graph is determined by its subgraphs. A method will be described for constructing a pair of graphs G, H on 2n vertices such that G and H have n vertex-deleted subgraphs in common. The method uses Paley groups from finite field theory.

### 30 October 2015, 3:30 pm, 115 Armes

Speaker: Vaclav Linek (Winnipeg)
Title: Polyhedral Designs

Abstract: Take 40 identical pieces of paper, each shaped as an equilateral triangle, one side white and one side black. For each 3-subset {x,y,z} of {1,2,3,4,5,6} take a triangle and write x, y, z at the corners on the white side. Then take another triangle and write x, z, y at the corners on the white side, i.e., this time write the numbers in the opposite orientation. Can you assemble these 40 triangles into 5 octahedrons so that the white sides face outward and at each corner all the labels agree?
Five such octahedra make an oriented OCT(6) design, an oriented OCT(v) design being defined similarly. An unoriented OCT(v) design is made from triangles that are white on both sides and labelled on both sides. Hanani (1978) settled the existence of unoriented octahedral designs. We show that an oriented OCT(v) design exists iff v = 1,2,6 (mod 8), and we solve the subsystem problem for octahedral designs. We will also give the existence result for cube designs, and shall say what is known about designs based on the other Platonic solids as well as the deltahedra.
This is joint work with Brett Stevens and Leonard Soicher.

### 6 November 2015, 3:30 pm, 115 Armes

Speaker: Ortrud Oellermann (Winnipeg)
Title: Progress on the Oberly-Sumner Conjecture

Abstract: For a given graph property P we say a graph G is locally P if the open neighbourhood of every vertex induces a graph that has property P. Oberly and Sumner (1979) conjectured that every connected, locally k-connected, K_{1,k+2}-free graph of order at least 3 is hamiltonian. They proved their conjecture for k=1, but it has not been settled for any k at least 2. We define a graph to be k-P_3-connected if for any pair of nonadjacent vertices u and v there exist at least k distinct u-v paths of order 3 each. We make progress toward proving the Oberly-Sumner conjecture by showing that every connected, locally k-P_3-connected, K_{1,k+2}-free graph of order at least 3 is hamiltonian and, in fact, fully cycle extendable. (This is joint work with S. van Aardt, M. Frick, J. Dunbar and J.P. de Wet.)

### 13 November 2015, 3:30 pm, 115 Armes

Speaker: Colin Desmarais (Manitoba)
Title: Norm-graphs and their applications

Abstract: For finite fields K of order q and F of order qm, so that F extends K, the Field Norm of an element α ∈ F is defined as N(α) = (α)1 + q + ... + q^{m-1}. I will discuss some basic properties of this norm, and demonstrate constructions of so called "Norm-Graphs". The extremal number ex(n;F) is the largest number of edges in a graph G on n vertices that does not contain F as a weak subgraph. I will demonstrate how the Norm-Graphs are used to improve on the lower bound for ex(n;K3,3), and more generally on the lower bound for ex(n; Ks, (s-1)!+1). Next, I will provide generalizations of these constructions that improve on the lower bounds for hypergraph extremal problems. Finally, I will discuss the impact of Norm-graphs on a graph-Ramsey problem.

### 20 November 2015, 3:30 pm, 115 Armes

Speaker: Sergei Tsaturian (Manitoba)
Title: Counting certain subgraphs in a graph and its complement

Abstract: For a graph G on n vertices, what is the minimal number of triangles in G or its complement? In 1959, A.W. Goodman proved that this number is at least roughly n3/24. The more general question can be asked: for a fixed graph H, and a graph G on n vertices, how many copies of H are guaranteed to be in either G or its complement? In my talk, I will show known results on this topic, and some further generalizations.

### 27 November 2015, 3:30 pm, 115 Armes

Speaker: Bob Quakenbush (Manitoba)
Title: Asymptotic philatelic enumeration or: Counting directly irreducible algebras in finite varieties

Abstract: A finite variety is a class of finite algebras which is closed under homomorphic images, subalgebras, and finite direct products; familiar examples are FBA (finite boolean algebras), FAB (finite abelian groups), FV(q) (finite-dimensional vector spaces over the field of order q), and FL (finite lattices). We are interested in computing the ratio of the number of directly irreducible algebras of size ≤ n to the number of all algebras of size ≤ n; I assume that the finite variety has unique direct factorization. For instance, for FBA, FAB, and FV(q), the ratio goes to 0. For finite varieties of lattices, I will give an easy proof that the ratio goes to 1.

For an arbitrary finite variety A, the ration need not converge. So we consider the limit set of the sequence of ratios for A (consisting of all limit points of convergent subsequences). This is a closed subset of [0, 1]; are there further restrictions? I will present an easy proof that for any a ∈ [0, 1], there is a finite variety Aa whose ratio converges to a. The algebras in Aa will all have cardinality a power of 5; this changes a more difficult multiplicative problem into an easier additive problem and yields a problem in the theory of Asymptotic Philatelic Enumeration (an explanation will be given).

What I don't know is whether there is an A whose ration limit set is {0, 1}.

### 4 December 2015, 3:30 pm, 115 Armes

Speaker: Jason Semeraro (Bristol)
Title: Hypergraph Turán densities for r-triangles

Abstract: The Turán number ex(H, n) for H is the maximum number of hyperedges in any r-uniform hypergraph on n vertices containing no copy of H. The Turán density of H is defined to be π(H) = lim_{n → ∞} ex(H, n) (n \choose r)^{-1}. π(H) always exists, but is notoriously hard to calculate in general, so we focus on a special case: Define an r-triangle H_r to be an r-hypergraph on r+1 vertices with three r-hyperedges having pairwise intersection of size r-1. By Mantel's Theorem, π(H_2)=1/2, with complete bipartite graphs realizing the extremal case. In general, it is known that π(H_r) <= 1/r. When r=3, Frankl-Füredi showed that π(H_3) >= 2/7, and various results (using flag algebra techniques) suggest that equality should also hold in this case. Baber has shown that π(H_4)=1/4 using a tournament construction. Motivated by Baber's work, we develop new methods for bounding π(H_r) (r > 3) using switching classes of tournaments. These methods have their origins in group theory via the action of PGL(2,q) on the extended Paley tournament. So far, we have been able to produce an infinite family of extremal examples in the case r=4 (simultaneously giving a new proof of the fact that π(H_4)=1/4), and to establish a new lower bound in the case r=6: π(H_6)>=9/64.