Past Event! Note: this event has already taken place.
Discrete Math Day
May 11, 2012
| Location: | 4351 Herzberg Laboratories |
| Cost: | Free |
Discrete Mathematics Day is a forum for discrete mathematics researchers from the Ontario/Quebec area (and beyond!) to meet and collaborate. We cover combinatorics in a broad sense, including graphs, designs, finite fields, enumeration and algorithms.
INVITED SPEAKERS
Richard Anstee (University of British Columbia)
Forbidden Configurations
Ada Chan (York University)
Type II Matrices
Richard Nowakowski (Dalhousie University)
Herding Cats and Dogs Through a Maze-
An Introduction to Combinatorial Game Theory
Claude Tardif (Royal Military College)
Speaking about Electoral Systems to Non-mathematicians
The Discrete Mathematics Day will be held on Friday, May 11. There is no registration fee but we ask that people register to give us an idea of attendance.
Discrete Mathematics Day gratefully acknowledges the Student Committee of the Canadian Mathematical Society, the School of Mathematics and Statistics, and the National Science and Engineering Research Council for their financial support.
Lectures
Speaker: Richard Anstee (University of British Columbia)
Title: Forbidden Configurations
Time: 9:30 – 10:30
Abstract: The notion of VC-dimension and shattered sets has had applications in Machine Learning and Covering Arrays. The problems often involve what I call simple matrices, namely (0,1)-matrices with no repeated columns. Given a set of rows S with |S|=k, we say that a matrix A shatters the k-set S if the submatrix of A formed by the rows S contains all possible k-rowed (0,1)-columns.
The notion of a forbidden configuration(s) is one way to generalize some of these results. Given a matrix F we say A has F as a configuration if some submatrix of A is a row and column permutation of F. If we define K_k to denote the kx2^k matrix of all columns on k rows, then A shatters a k-set if and only if A has K_k as a configuration. One important extremal problem is to compute forb(m,F), which is the maximum, over all m-rowed simple A where A has no configuration F, of the number of columns in A.
The original results of Sauer (72), Perles and Shelah (72), Vapnik and Chervonenkis (71) yield forb(m,K_k) exactly. We outline related results which can be viewed as asking for F for which forb(m,F) is either equal to forb(m,K_k) or asymptotically equal.
Speaker: Ada Chan (York University)
Title: Type II Matrices
Time: 11:00 – 12:00
Abstract: First introduced by Sylvester in 1867 as inverse orthogonal matrices, a type II matrix is an invertible n X n matrix that has no zero entry, whose inverse can be easily obtained by inverting every entry, taking the transpose and multiplying by n^{-1}.
Type II matrices regained popularity in 1990’s after spin models were introduced to give link invariants. In this talk, we give a survey of type II matrices, to see where else they show up and their connections to combinatorics.
Speaker: Richard Nowakowski
Title: Herding Cats and Dogs Through a Maze—An Introduction to Combinatorial Game Theory
Time: 2:30 – 3:30
Abstract: In these games, such as Chess, Go, Checkers, the last player to move determines the winner. There is a rich theory that goes along with these games. Using the games of Cats & Dogs and Maze, I’ll introduce the basic and not-so-basic concepts. The material is easy, even though `games are hard’, and is accessible to undergraduates, although it may be disturbing to some set theorists $\infty -1 < \infty$. Unsolved games and problems will be presented along the way.
Speaker: Claude Tardif (Royal Military College)
Title: “Speaking about Electoral Systems to Non-mathematicians”
Time: 4:00 – 5:00
Abstract: I chose the subject of this talk over very specialised possibilities involving adjoint functors and Hedetniemi’s conjecture. In 2006 I followed the proceedings of the Ontario Citizens’ Assembly on electoral reform. I participated in the subsequent referendum campaign, and joined Fair Vote Canada. I have been interested in electoral systems ever since.
At one end, electoral systems are a specialized mathematical topic involving May’s theorem, Arrow’s impossibility theorem and the Gibbard–Satterthwaite theorem. At the other end, talking about them to the general public confronts one with the general understanding (and misunderstanding) of arIthmetical concepts such as majority and proportions, with how people understand other electoral systems and their properties, and even how people understand other people’s understanding of electoral systems. I find it to be a fascinating subject as a mathematician, even though I am not tempted to pursue mathematical research in it.
For accommodations click here: