Balasingham Balamohan
Home university:
University of Toronto
Supervisor:
Bruce Richter
Project:
It is known that there is a unique set \(\Pi\) of primal graphs having the following two properties:
- for any (simple) graph \(G\) there is a partition \(\{E_1,\dots,E_k\}\)of its edges so that the subgraphs\(G[E_1],\dots,G[E_k]\) are pairwise nonisomorphic and are all in \(\Pi\); and
- if $G\in \Pi$, then the only such partition is $\{E\}$. It is very difficult to determine which graphs are primal, although primal graphs with maximum degree at most two are fairly well understood. In this project, we hope to determine primal forests with maximum degree at most three.
Update 2008:
PhD student, University of Toronto.
Lei Chu
Home university:
University of Waterloo
Supervisor:
Chris Godsil
Project:
The goal of this project is to investigate certain graph colouring problems.
The graphs in question come from association schemes, and will often be Cayley graphs for abelian groups. The student's task will be to write some software in Maple and C to construct these graphs, and to get information about relevant parameters (chromatic number, independence number,...) . Where possible, this software will be based on existing packages. He or she will also be expected to develop an understanding of the related mathematics.
Once this software is in place and producing useful output, the student will help to analyse the results produced and, ideally, will prove some new results based on the information we obtain.
Marshall Drew-Brook
Home university:
University of Waterloo
Supervisor:
Bertrand Guenin
Project:
A graph is said to have an odd \(K_5\) minor, if \(K_5\) can be obtained from that graph by deleting a subset of the vertices and the edges and by contracting all edges on a cut. It is conjectured that all graphs without an odd \(K_5 \) minor can be obtained by pasting together some elementary graphs along some small cutsets. These elementary graphs come into two basic classes which we call, nearly bipartite and topological. Nearly bipartite graphs are graphs where all the odd circuits are intersected by a small set of vertices and edges. Topological graphs include planar graphs and some graphs which can be embedded into other surfaces such that all the faces have even length. This conjecture predicts that graphs with no odd \(K_5 \) minors but with many triangles should be close to being planar. The project is to investigate some aspects of this problem. A software package which was developed during a previous Undergraduate Research Assistant (URA) project will be one of the tools.
Ian Harrower
Home university:
University of Waterloo
Supervisor:
Joseph Cheriyan
Ross Kang
Home university:
University of Victoria
Supervisor:
Jim Geelen
Update 2008:
DPhil in Mathematics, University of Oxford, 2007, Natural Sciences and Engineering Research Council of Canada (NSERC) PDF, McGill.
Craig Sloss
Home university:
University of Waterloo
Supervisor:
Ashwin Nayak
Project:
Recently, a great deal of activity in the computer science community has been devoted to characterizing the power of quantum-mechanical computers in complexity-theoretic terms. Of special interest is the notion of a "quantum proof'' for the validity of statements about computational problems, and when short and easily verifiable (i.e., "efficient'') quantum proofs exist. In this project, we plan to study proofs for lattice based problems, especially the f(n)-unique shortest lattice vector problem. Here, the function f parametrizes the computational complexity of the problem: the smaller f(n) is, the harder the problem gets. Efficient classical proofs are known to exist for this problem when f(n) = sqrt(n). The goal of this project would be to devise, if possible, efficient quantum proofs for a function f that grows slower than sqrt(n). This would demonstrate, yet again, the advantage of quantum computation for an important computational problem.
Update 2008:
PhD Student, Combinatorics and Optimization Department, University of Waterloo.
Yuli Ye
Home university:
University of Waterloo
Supervisor:
Ian Goulden
Project:
In the famous paper of Kontsevich, "Intersection Theory on the Moduli Space of Curves and the Matrix Airy Function", there is a mysterious change of variables used in an integral, as part of the proof of the main result. This transformation has a simple combinatorial description in terms of a graph embedded in a surface, but there is no hint of a proof in those terms. The purpose of this project is to discover and prove the general combinatorial result of which Kontsevich's integral evaluation is a special case.
Update 2008:
Graduate student in the Theory of Computation Group of the Department of Computer Science, University of Toronto.
Martha Yip
Home university:
University of Waterloo
Supervisor:
David Jackson
Project:
A set of \(n\) objects is partitioned into \(L\) sets of size \(k_{0},\ldots ,k_{L-1}.\) Let \mathbf{k}\(=$\left( k_{0},\ldots ,k_{L-1}\right) \) .Under the action of a permutation \(\pi \in {\cal S}_{n}\), $\(\theta_{\mathbf{k}}\left( \pi \right) \) of the elements are moved outside their sets. The generating series, suitably scaled, for permutations in \({\cal S}_{n}\) with respect to \(\theta _{\mathbf{k}}\left( \pi \right)\) is of interest. The problem is to investigate its properties. A conjecture of Suhov and Voice is the generating has a "nice'' expression in terms of the power sums \(p_{r}=\sum_{i=0}^{L-1}k_{i}^{r},$ $r=1,2,\ldots\) in the sizes of the blocks of the partition. For example, the first few terms of the series are \(x^{n}+\left( p_{1}^{2}-p_{2}\right) x^{n-2}+\frac{1}{6}x^{n-3}\left( p_{1}^{3}-3p_{2}p_{1}^{2}+p_{3}\right) +\cdots\) . At present, little more than this is known. In particular, no tractable expression for the coefficients of the generating series is known. This kind of problem arises in Quantum Information Theory and Quantum Computing, where physicists are trying to understand "entanglement.'' There is a further conjecture about the form of a scaled limit of a transformation of the generating series, but this clearly depends upon progress on the above conjecture.