Spring 2003
Place: WMAX 216. 
Time: Wednesday, 4.30-5.30pm 
 

15th Jan	Steph van Willigenburg (UBC)
	Peak functions and Eulerian enumeration: In 1995 the complete duality of Q -- the Hopf algebra of quasisymmetric functions -- and NC -- the Hopf algebra of nonommutative symmetric functions -- was realised by Malvenuto and Reutenauer. Since then a natural question to ask is: Given a Hopf subalgebra of Q, can the dual quotient Hopf algebra in NC be found?  One instance of success has been in finding the dual of the peak algebra of Stembridge. In this talk we will introduce the above Hopf algebras and the dual to the peak algebra, and relate this duality to the cd-index often studied by geometers.
*27th Jan* MATX 1102 3-4pm	Nantel Bergeron (York University)
	Combinatorial Hopf Algebras: A Combinatorial Hopf algebra [CH-algebra] is a pair (H, z) where H is a graded connected Hopf algebra over a field F, and z: H -> F is a multiplicative functional. These algebraic objects often encode combinatorial structures in various area of mathematics and physics. Our first result is to show that the CH-algebra of quasi-symmetric functions is the terminal object the category of CH-algebras. We say that (H, z) is eulerian if its Mobius function satisfies certain conditions we describe. We show that given any CH-algebra (H, z), there is a unique maximal eulerian CH-subalgebra (E, z), and its elements are characterized by the generalized Dehn-Sommerville relations. Moreover eulerian CH-algebras form an induced subcategory. Depending on time, we characterize the eulerian CH-subalgebras of important CH-algebras introduced: that of quasi-symmetric functions, that of Malvenuto-Reutenauer, and that of Loday-Ronco.
12th Feb	Jaydeep Chipalkatti (UBC)
	Classical invariant theory and coincident root loci: Let F(x) be a degree n polynomial in a single variable x with complex coefficients. It is classical that F has a double root iff its discriminant vanishes. It is not so well-known that all the roots of F coincide iff the Hessian of F is identically zero. Now, in general, we can fix a partition \lambda of n, and ask for algebraic conditions on the coefficients of F so that the roots follow the pattern dictated by the parts in \lambda. I will outline a solution to this problem using a little classical invariant theory and graph theory.
26th Feb	Jeremy Barbay (CS, UBC)
	Bak Sneppen models for Coevolution: The Bak Sneppen system is described by n real variables forming a ring. The variables are initialized uniformly at random in the unit interval. At each step of the process the values of the variable of minimal value and its two neighbors on the ring are reset, again uniformly at random in the unit interval. In simulations this system converges to a state where all values are uniformly distributed above a threshold experimentally evalued to ~.742. From this state the system goes back to smaller values by a sequences of "avalanches", to converge again. This behavior is described as "Self-Organized Criticality", as the system brings itself to the critical state, as in the sand pile models. The Physicists P.~Bak and K.~Sneppen published in 1993 (Phys. Rev. Lett. 71, 4083) this model as a simplistic model of the coevolution of species, and interpreted the self-organized behavior as an argument in favor of the Punctuated Equilibrium theory, a controversial theory in the field of the study of evolution. We analyzed the discrete version of this model with Kenyon in 2001 ("On the discrete Bak-Sneppen model of self-organized criticality", Barbay and Kenyon, SODA, January 2001).  Meester and Znamenski completed more recently this analyzis and gave an analysis of the bak sneppen model itself ("Non-triviality of a discrete Bak-Sneppen evolution model", to appear in JSP. 15; "There is a phase transition in the Bak-Sneppen evolution model", to appear in The Annals of Probability). I will try to introduce the Bak Sneppen and the Discrete Bak Sneppen models, and the tools used to analyze it. Without entering into the controversy of the Punctuated Equilibrium theory I will point out one open problem which once solved or proved not solvable could help to validate or invalidate this theory.
12th Mar	Catherine Webster (UBC)
	Braid groups and cryptography: In this talk we discuss two possible  cryptosystems based on the braid group, one using a canonical form for braid  words and one using an unfaithful matrix representation. We will then discuss possible attacks to these cryptosystems.
*24th Mar* MATX 1102 3-4pm	Stefan Mykytiuk (York University)
	Peak and Shifted Quasi-Symmetric Functions: Quasi-symmetric functions, a generalization of symmetric functions, have played an increasingly important role in combinatorics during the past twenty years. 'Peak' and 'shifted' quasi-symmetric functions are of particular interest because they are connected with counting chains of faces in polytopes, and because they possess universal properties which allow us to transfer combinatorial problems from one setting to another. We shall show how algebraic operations on these functions can be described in terms of simple operations on partially ordered sets.
9th Apr	Petr Lisonek (SFU)
	Caps in binary projective spaces:  Let PG(n,q) denote the n-dimensional projective space over GF(q). A cap in PG(n,q) is a set of points no three of which are collinear. Caps naturally correspond to linear q-ary codes with minimum distance at least 4.  We review some known results about caps for general q and then we will focus on q=2 for the rest of the talk.  Several new  combinatorial constructions of caps will be given and their geometrical properties will be discussed.  We will demonstrate the relevance  of our constructions to the problem of finding the least dependent caps  of a given cardinality in a given dimension, where the dependency of a cap  is the number of linearly dependent (coplanar) quadruples of points in it,  and we will mention applications in coding theory and in experiment design.   We will also discuss an algorithm for an isomorph-free classification of caps  and other similar geometrical structures in PG(n,q). This is joint work with Mahdad Khatirinejad Fard.