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

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.

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 |

**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:

- 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?
- Can a square be partitioned into 5 triangles of equal area? Does number theory hold the answer?
- Can results in convex geometry be used to obtain number-theoretic results?
- If points in a Euclidean space are coloured either red or blue, what patterns in one colour can be guaranteed?

**Speaker**: Sergei Tsaturian

**Title**: Survey of Euclidean Ramsey Theory

**Abstract: **

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

**Speaker**: Ranganathan Padmanabhan

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

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

**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".

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

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

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

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

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

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

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

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

**Speaker**: Narad Rampersad

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

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

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

**Speaker**: Rob Craigen

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

**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.)

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 |

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

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

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

**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| ≤ q ^{3}*.

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

**Speaker**: Ranganathan Padmanabhan

**Title**: Term Spectra and their Minimal Extensions

**Abstract: **
For an algebra *A*, let *p _{n}(A)* denote the number of essentially

p(A) = {p_{0}(A), p_{1}(A),...,p_{n}(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**

- G. Grätzer and R. Padmanabhan, On idempotent, commutative and non-associative groupoids. Proc. Amer. Math. Soc 28 (1971) 75-80.
- 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.
- J. Dudek, Affine spaces over GF(3), Studia Logica 72 (2002), 363-366.
- R. Padmanabhan, Free spectrum of shelf algebras, Rings and Modules Seminar, University of Manitoba, 06 October, 2015 (unpublished).

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

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

**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).

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 |

**Speaker**: Ranganathan Padmanabhan

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

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

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

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

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

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

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

**Speaker**: Andrii Arman (Manitoba)

**Title**: Fibonacci-sum graphs

**Abstract: ** For each positive integer *n*, the Fibonacci-sum graph *G _{n}* is the graph with vertex set

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

**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 = M ^{t}*, where

**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).

**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 K_{n} are 2-coloured, a monochromatic copy of K_{m} (as a subgraph) can always be found. An edge can also be thought of as the graph K_{2}. 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.

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

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

**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.)

**Speaker**: Colin Desmarais (Manitoba)

**Title**: Norm-graphs and their applications

**Abstract: ** For finite fields *K* of order *q* and
*F* of order *q ^{m}*, so that

**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
*n ^{3}/24*. The more general question can be asked: for
a fixed graph

**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
A_{a} whose ratio converges to a. The algebras in
A_{a} 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}.

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