Past Combinatorics Seminars

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

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

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.

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

Speaker: Ranganathan Padmanabhan
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

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

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.