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

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