Jason I. Brown
Faculty of Computer Science and Department of Mathematics and Statistics
Dalhousie University
Abstract: A well-covered graph is a graph all of whose maximal independent sets have the same size. We extend this notion of well-coveredness via linear algebra. The extension, while of indepedent interest in its own right, can also be used to produce a structure theorem for well-covered graphs without cycles of length 4. We also discuss extensions to other combinatorial structures such as matroids. Finally, we shall mention a number of algorithmic and theoretical questions that remain open.
Yue Zhao
University of Central Florida
Abstract: In this talk, I will first introduce the edge reconstruction conjecture. Then I will talk about results on this conjecture and how to use the discharging method to approach this conjecture.
Andrew King
Department of Computer Science
University of Toronto
Abstract: A permutation pi on the interval [n] is indecomposable if and only if pi([m])=[m] for no m<n, i.e. if and only if it has no proper prefix which is itself a permutation. The number of such permutations, I(n), is equal to SUM_{j=0}^{n-2}{ (n-j-1)*I(n-j-1)*(j!) }. I will discuss this recurrence briefly and explain how it leads to a transposition Gray code for such permutations, the generation algorithm for which can be implemented in CAT (constant amortized time).
I will also discuss a much simpler CAT generation algorithm for indecomposable permutations, which is based on the Steinhaus-Johnson-Trotter algorithm for generating all permutations in adjacent transposition Gray code order.
This work is based on my undergraduate honours project, supervised by Frank Ruskey.
|
|