
COMBINATORICS AND OPTIMIZATION SEMINAR
Date and time: Friday, October 19, 2012, at 14:00
Place: University of Ottawa, Room KED B004
Speaker: Mike Newman (University of Ottawa)
Title: "The missing axiom of matroid theory is (once again) lost forever"
Abstract: Given a set of vectors in a vector space, what can we say about the collection of subsets that are linearly independent? Choosing
different sets of vectors gives different collections of independent subsets, but clearly, we cannot choose a set of vectors so as to
obtain any collection of subsets as the independent sets (that's an exercise). Can we describe the "admissible" collections in some way?
Of course, there is the answer we tell our students: namely, the independent subsets are those for which the corresponding system of
equations has no solutions over the particular field in question. But we would prefer simple axioms, describing the collection purely
as a collection of subsets.
There are simple necessary conditions on the collection of independent subsets (that's an intermediate exercise), that were first explicitly
mentioned as such by Whitney in the 1930's; he defined a "matroid" to be a collection of subsets that satisfies these axioms. Clearly then,
the collection of linearly independent subsets of a fixed set of vectors is an example of a matroid, but there are (many!) other
collections of subsets that do not arise in this way (that's a harder exercise). Can we add some more (simple!) axioms and so characterize
exactly those matroids which are, in reality, just the collection of linearly independent subsets of a fixed set of vectors? As Whitney
asks: Are realrepresentable matroids finitely axiomatizable?
It turns out that matroids representable over a finite field are finitely axiomatizable, if the order of the field is less than 5.
Rota's conjecture would imply finite axiomatizability with respect to any finite field.
For an infinite field, the situation is more complicated. In the 1970's Vamos said "no" in a paper with an alluring and unambiguous
title. However, a careful reading of his paper reveals that his notion of both "matroid" and "axiom" differs significantly from what
one would want.
We show in this talk that, under the correct notion of "matroid" and a reasonable definition of "axiom", it is not possible to finitely
axiomatize matroids representable over any particular finite field. This talk will not presume knowledge of matroids or axioms, nor
completion of the exercises (though I promise that at least one of them is easy).
This is joint work with Geoff Whittle and Dillon Mayhew.

COMBINATORICS AND OPTIMIZATION SEMINAR
TITLE: Cycle Systems: A Neverending Fascination
SPEAKER: Mateja Sajna (Ottawa)
DATE: Friday, October 5, 2012
TIME: 2:00 pm
ROOM: KED B004
ABSTRACT: This talk begins with an account of the fascinating history of combinatorial designs and cycle systems. We then introduce some of the
most important problems involving cycle systems: cycle decomposition of complete (and nearly complete) graphs, and the Oberwolfach problem, both
in its directed and undirected variant. We briefly sketch some of the proofs of the solved problems, and give an update on the status of the
open ones. Finally, we discuss the author’s progress (joint work with Andrea Burgess and Patrick Niesink) on the directed Oberwolfach problem
with constant cycle lengths.

COMBINATORICS AND OPTIMIZATION SEMINAR
Date and time: Friday, September 21, 2012, at 14:00
Place: University of Ottawa, Room KED B004
Speaker: Nevena Francetic
Title: Covering arrays with row limit
Abstract: Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group
divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial
models for interaction test suites.
In this talk we consider the central questions regarding CARLs: the bounds on their size and constructions of (optimal) object. We discuss their
relationship to their predecessors in terms of asymptotic growth. Also, we present some constructions of optimal CARLs with row limit four. Finally,
we consider a packing version of the same problem, namely packing arrays with row limit, PARLs, and transformation from optimal CARLs to optimal
PARLs.