• Research Groups
• Postgrad Study
• Conferences
• Seminars
• Postgrad Resources
• Publications

Computer Science Theory

Welcome | People | Research | Publications | Seminars | Talks | Courses | Events | Useful Links

Seminars

We run a study group that meets every week during the teaching semesters.

The study group ran for the firsttime in the second semester of 2000; as a result, we wrote a 5 authorpaper on the permutations of a multiset that avoid various patterns. The paper is available in postscript form and appears in the European Journal of Combinatorics.

In first semester 2001 we studiedalgorithms for the recognition of patterns within permutations. We wrote a 4 author paper also available in postscript form which was accepted at ISAAC 01.

In second semester 2001 we studied the packing density of permutations. Our 5 author paper is available in postscript form and appears in the Electronic Journal of Combinatorics.

In first semester 2002 we studiedhow to find longest subsequences of various types within permutations. We wrote a 7 author paper which is available in postscript form and appears in the Australian Journal of Combinatorics.

In second semester 2002 we studied 1324-avoiding permutations.We used this applet.  We found connections with certain queue data structures and wrote a 6 author paper, was accepted by Discrete Mathematics, and is available in postscript form.

In first semester 2003 we studied problems having to do with secret transmissions and geometric configurations. Our 5 author paper on this was accepted by the Australian Journal of Combinatorics and is available in postscript form.

In second semester 2003 we studied machines which permute their input data while being sensitive to the relative values. Our 6 author paper on this was accepted by the journal Theoretical Computer Science and is available in pdf form.

In first semester 2004 we studied the composition of permuting machines. Our 7 author draft paper on this is available in pdf form.

In second semester 2004 we studied classes of permutations that are not only closed under involvement but are also closed downwards in the strong and weak orders on permutations. These closure conditions are natural ones for a sorting machine. Our 7 author paper on this was accepted by the Electronic Journal of Combinatorics and is available in pdf form.

In first semester 2005 we studied closed classes in which we impose an extra condition on the involvement relation. Eventually, we took this extra condition to be that of being closed under cyclic rotations. Our 8 author paper is available in pdf form.

In second semester 2005 we studied a combinatorial game associated with the Erdos-Szekeres theorem. Our paper on this is available as a pdf file.

In first semester 2006 we studied properties of pattern classes that critical in the sense that the class does not have the property but all its proper subclasses do.

Because of sabbaticals and other upheavals the seminar did not run in 2007.

In first semester 2008 we looked at pattern classes whose permutations are the unions of r increasing subsequences and d decreasing subsequences.

In second semester 2008 we had a slight change of focus and looked at permutation classes defined by avoiding one or more permutations consecutively. Our 3 author paper is available as a pdf.