COseminar

Ottawa-Carleton Combinatorics and Optimization Seminar 2012-13

TITLE:	Nonrepetitive Coloring via Entropy Compression
SPEAKER:	Gwenaël Joret (Université Libre de Bruxelles)
DATE:	Friday, November 30, 2012
TIME:	2:00 pm
ROOM:	B004
ABSTRACT:	A vertex coloring of a graph is nonrepetitive if there is no path whose first half receives the same sequence of colors as the second half. As for many other graph coloring problems, Lovasz's Local Lemma can be used to obtain nonrepetitive colorings where the number of colors is bounded by a function of the maximum degree \Delta. This was first observed by Alon et al in 2002, who obtained a bound of c \Delta^2 for some large constant c. The value of the constant c was subsequently improved several times over the years, down to c = 10.4 by Kolipaka, Szegedy, and Xu in 2012. In this talk I will present a proof for c = 1. The proof is based on the entropy compression method introduced by Moser and Tardos in their constructive proof of the Local Lemma. A general message of the talk will be that their approach is not only very useful to obtain efficient algorithms, but can moreover be used to get improved bounds, often with simpler proofs. Joint work with Vida Dujmovic, Jakub Kozik, and David Wood.

TITLE:	Connected Factorization of Complete Uniform Hypergraphs
SPEAKER:	Amin Bahmanian (University of Ottawa)
DATE:	Friday, November 16, 2012
TIME:	2:00 pm
ROOM:	B004
ABSTRACT:	Baranyai found necessary and sufficient conditions for the existence of a factorization for the complete uniform hypergraph. Using a new proof technique, in this talk I prove a more general result that in particular allows us to guarantee that each factor is connected, answering a question by Katona.

COMBINATORICS AND OPTIMIZATION SEMINAR

TITLE:       On Sheehan’s Conjecture for graphs with symmetry
SPEAKER:     Mateja Sajna (University of Ottawa)
DATE:        Friday, November 2, 2012
TIME:        2:00 pm
ROOM:        KED B004

ABSTRACT:     It is known that every (simple) regular graph of degree d that has a Hamilton cycle in fact possesses a second Hamilton cycle if d is odd or 
d is at least 23. Sheehan conjectured that the statement is also true for d=4, which would imply that it is true for every d greater than 2.
Fleischner showed that Sheehan's conjecture fails for 4-regular multigraphs, but it is not difficult to prove it for 4-regular vertex-transitive simple graphs. 
In this talk, we outline the proof of Sheehan's conjecture for 4-regular simple graphs satisfying certain conditions on the automorphism group that are 
weaker than vertex transitivity. This is joint work with Andrew Wagner.

Note: This is a half-hour talk. The rest of the hour will be devoted to informal discussion.

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 real-representable 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.