Mathematics Colloquium
" The Life of Pi "

Mathematics Colloquium
" An Elementary Proof of a Theorem of Gabriel on degenerate bilinear forms "

Every square matrix A over any field is congruent to the direct sum of nilpotent Jordan blocks whose sizes are uniquely determined by A and an invertible matrix whose congruence class is determined by that of A. Moreover, a nilpotent Jordan block is indecomposable under congruence. These facts are a reformulation of a theorem due to P. Gabriel. We shall present an elementary proof of them. Joint work with Dragomir Djokovic.

Mathematics Colloquium
" Some New (and old) Unsolved Problems in Combinatorial Game Theory "

Combinatorial games are played between two people, there are no chance devices (cards, dice, spinners, etc) and the last person to move wins. I will talk about three classes of games.

1. A seemingly easy set of games are those called Subtraction Games (e.g. from a heap of counters take away 1, 2 or 3 from the heap) and their variants. There is much to be discovered.
2. Clobber was invented in 2002. (Take a 6x7 checkerboard with black pieces on all the black squares and white on all the white squares. A piece can only be moved one square horizontally or vertically provided there is an opponent's piece on the other square which is now clobbered and removed.) Very little is known about this game although much has been conjectured.
3. Cutthroat is played on a graph whose vertices are coloured either red or blue. One player deletes the red vertices while the other deletes the blue. Any monochromatic component disappears. Restricting the game to playing on stars ($K_{1,n}$) holds some surprises.

The talk will be self-contained and is suitable for undergraduates.

Mathematics Colloquium
" Tail probability of low-priority queue length in a discrete-time priority BMAP/PH/1 queue "

We investigate the tail probability of the queue length of low-priority class for a discrete-time priority BMAP/PH/1 queue which consists of two priority classes, with BMAP (Batch Markovian Arrival Process) arrivals of high-priority class and MAP (Markovian Arrival Process) arrivals of low priority class.

A sufficient condition under which this tail probability has the asymptotically geometric property is derived.

A method is designed to compute the asymptotic decay rate if the asymptotically geometric property holds.

For the case where the BMAP for high-priority class is the superposition of a number of MAP's, though the parameter matrices representing the BMAP is huge in dimension, the sufficient condition is numerically easy to verify and the asymptotic decay rate can be computed efficiently.

 
First Prairie Discrete Mathematics Workshop
at the University of Regina

Probability/Statistics seminar
" On the Self-normalized Bounded Laws of Iterated Logarithm in Banach Space "

For a sequence of independent symmetric Banch space valued random variables {X_n, n>=1}, we obtain the self-normalized law of iterated logarithm and give the upper bound for the non-random constant.

Algebra & Number Theory Seminars
Fall 2003

Since "Algebra and Number Theory" is perhaps a little exclusive considering the varied research interests around the department this year, let me point out that this was just the name we had for the seminar involving many of the same suspects last fall. So this year we will only stipulate that talks in this seminar are only required to use words related to Algebra (such as "linear algebra", "operator algebra", "group", "ring", "module", "field", or "category") or to Number Theory (like "prime", "zeta-function", "theta-function", "elliptic curve", or "modular form") at least once during the course of the talk in order to be considered acceptable for this seminar.

Mathematics Colloquium
" Matrix Completion Problems for Various Classes of P-Matrices "

Mathematics Colloquium
" Classification of C^*-dynamical systems "

Mathematics Colloquium
" An algorithmic characterisation of k-cop-win digraphs "

Cops and Robber is a pursuit game usually played on a digraph G with no vertices of outdegree zero, which may have loops at some vertices. To start the game, each of the k>0 cops chooses a vertex of G, and then the robber chooses a vertex of G. The cops and the robber then move alternately, with the cops moving first. A move for the cops consists of each cop travelling along an arc from his present vertex to a neighbouring vertex. A move for the robber is defined analogously. When a vertex has a loop, a cop or the robber can use it to remain at his current position. The game is played with perfect information, so that the cops and the robber always know each other's location. The cops win the game if they can move so that one of them eventually catches -- occupies the same vertex as -- the robber. The robber wins if he can move never to be caught. A digraph is k-cop-win if k cops have a winning strategy, and robber-win otherwise. Historically, 1-cop-win digraphs have been called cop-win.

This game was first described for reflexive undirected graphs with one cop and one robber by Nowakowski and Winkler, and Quilliot, independently. Both papers characterise the cop-win graphs. Beyond the one-cop case, no characterisations are known. It is a long standing open problem to characterise the k-cop-win reflexive undirected graphs for k>1. Cops and robber games on digraphs have not received as much attention. The reflexive digraphs on which a single cop can always win have also not been characterised.

We describe an algorithmic characterisation of the cop-win finite digraphs. It is in terms of an auxiliary digraph constructible in polynomial time. We then describe how any k-cop game can be reduced to a 1-cop game, thus giving a characterisation of the k-cop-win digraphs. We conclude by describing how these methods can be applied to some variants of the game.

Mathematics Colloquium
" Mobility of vertex-transitive graphs "

We define the mobility of a graph automorphism to be the minimum distance between a vertex and its image under the automorphism, and the mobility of a graph as the maximum mobility of its automorphisms. In this talk, we present some recent results on mobility of vertex-transitive graphs, and in particular, Cayley graphs. This is joint work with Gabriel Verret, an undergraduate student at the University of Ottawa.

Mathematics Colloquium
" Bounding the Search Number of Cayley graphs on Dihedral Groups "

This talk repesents the first new work coming out of the MITACS Searching Networks Project, and is joint work of Brian Alspach, Denis Hanson and Xiangwen Li. Mathematical research can be a humbling experience. You will see why that remark is pertinent as the development of the result and its proof is traced out.

Mathematics Colloquium
" Multigroupoids and Relation Algebras "

Mathematics Colloquium
"The Inverse Eigenvalue Problem for Symmetric Acyclic Matrices"

Graduate Seminar
"On a Nonlinear Matrix Equation"

We consider the nonlinear matrix equation X + A^TX^-1A = Q, where Q is symmetric positive definite. We present a necessary and sufficient condition for the existence of positive definite solutions. The maximal positive definite solution is of particular interest. Two algorithms for finding the maximal solution are presented and compared.

As an application, we show that the maximal solution can be used to find all eigenvalues of the quadratic eigenvalue problem:

(l² M + l G + K)x = 0,
where M is symmetric positive definite, K is symmetric negative definite, and G is skew-symmetric.

The 44th Basterfield Lecture
" Retirement Security and Population Aging "

In his lecture, Professor Brown will report on two recent research projects on which he has been working. Both have to do with the Macro-economic impacts of Population Aging on Retirement systems.

Initially, Professor Brown will argue that our present system of Registered Pension Plans (RPPs) and Registered Retirement Savings Plans (RRSPs) will provide the government(s) with exactly the correct amount of cash flow and at exactly the right time, to pay for the increased demand for health care created by the aging baby boomers. Thus, accidentally, we may have created the perfect macro-economic immune portfolio (i.e. RPP/RRSPs versus Health Care costs). However, this is dependent upon the government not looking at RPPs/RRSPs as a source of "Tax Expenditures" but rather as the perfect deferred tax asset. In particular, the government must embrace a philosophy whereby the RPP/RRSP system will be allowed to expand as rapidly as per unit health care costs are allowed to rise.

In the second part of his lecture, Professor Brown will argue that it is inevitable that the labour force retirement age will rise sometime after 2006. Depending on the level of labour force productivity that we can achieve, this rise in the retirement age may not have a large political impact. However, once incentives for early retirement change into incentives for later retirement, we can expect some kind of behaviourial response from the work force. In particular, we should expect demands for more flexible retirement systems as workers attempt to smoothly "transit" into retirement. Many of the requests for pension flexibility are now obviated by pension legislation. Thus, this legislation will have to be questioned and (hopefully) redesigned.

Mathematics Colloquium
" Combinatorial aspects of electrical network theory "

In 1847 Kirchhoff published his famous paper describing electrical network response functions in terms of enumerators for spanning trees in weighted graphs. I will present Kirchhoff's formula for effective admittance as the motivation for some combinatorial questions. Two physically intuitive (and easily proven) analytic properties of the effective admittance are ''Rayleigh monotonicity'' and ''real--part positivity''. Both of these properties can be translated from physics into statements of combinatorial significance. From this point of view, a generalization from graphs to matroids is natural (no matroid theory will be assumed in this talk). One result among many is a third setting in which matroids occur ''in nature'', complementing the way in which they generalize graphs or matrices. This is in part joint work with Young-Bin Choe, James Oxley, and Alan Sokal.

Mathematical Sciences Colloquium
" The mathematical background of asymmetric cryptosystems "

Cryptography is used to safeguard information that is stored or sent through channels like the internet. Using asymmetric cryptosystems, one can make the encryption procedure public while keeping the corresponding decryption algorithm secret. Alternatively, one can use an asymmetric cryptosystem to safely exchange keys for symmetric cryptosystems (which in general are more effective), and then send the information using the latter.

I will give a survey on the algebraic and number theoretical methods used for asymmetric cryptosystems. I will explain the basic idea of asymmetric cryptosystems. Then I will describe the Merkle-Hellman Knapsack cryptosystem, RSA, the discrete logarithm problem, Diffie-Hellman key exchange and the El Gamal cryptosystem. Finally, I will quickly describe the use of elliptic curves in connection with the discrete logarithm problem. If time permits, I will also discuss possible attacks on these cryptosystems.

The talk is directed to a general audience with basic knowledge in mathematics.