Possible research topics

I am on the lookout for students who would like to do research in combinatorics, whether it be at honours, masters or PhD level. Depending on your interests it could be pure combinatorics or it might have an algebraic, number theoretic or algorithmic flavour.

## Research Interests

I'm interested in supervising students in any of the following areas:

Below is a sample of questions that interest me. My actual wishlist is a lot longer than this though...

## Latin Squares

A Latin square is a matrix in which each number occurs exactly once in every row and once in every column. There are loads of questions I want to answer about Latin squares. Here's just a couple.
1. Why are the numbers of latin squares divisible by such a high power of two?
2. Can you build a latin square of every order > 6 that does not have any proper latin subsquares?
3. Does every latin square of odd order have a transversal? Does every latin square of even order have a near transversal?
4. Estimate the number of transversals of the cyclic groups of odd order. (Equivalently, estimate the number of complete mappings/orthomorphisms).
5. Computational searches for sets of mutually orthogonal latin squares (MOLS) aimed at finding families of such objects.
6. Constructions for maximal MOLS (that is, sets of MOLS that cannot be extended to larger sets). We have some techniques for building such things now...

## Permanents

The permanent of a matrix is like the determinant but without those fiddly signs (+/-) on each term. Questions I'd like to investigate here are:
1. What is the largest power of 2 that divides the permanent of a Hadamard matrix of order n? Is this power the same for every Hadamard matrix of a given order? If so, this would prove a conjecture that the permanent of a Hadamard matrix never vanishes.
2. Concerning (0,1) matrices whose permanents and determinants agree up to sign: (1) What is the most 1's they can have? (Probably the optimal arrangement is n(n+1)/2, achieved by triangular matrices) (2) What is the largest value of the permanent among such matrices? (3) Same question, but with restrictions on the row and or column sums.
3. Attack any of the remaining questions in Minc's famous catalogue of conjectures and open problems.

## Graph theory

A graph in this sense is a network of nodes and connections between nodes. Here are some possible project topics:
1. In a recent paper, Friedland, Krop and Markstrom conjecture an interesting generalisation of Bregman's theorem (which deals with bipartite graphs which maximise the number of perfect matchings). They suggest that the same structure maximises the number of matchings of any given size. It seems possible to prove this conjecture (at least asymptotically) using techniques such as rook polynomials, that I have applied in related problems. The same FKM paper has some other interesting conjectures too.
2. Suppose I take a face 2-colourable triangulation of the plane. I label each vertex with an indeterminate, and I add a relation that says the indeterminates around each white face add to zero. What group do I get? Is it the same group if I use the black faces?
3. There are various conjectures dealing with the existence of one-factorizations and perfect one-factorisations of graphs. Attacks on these could be computational or theoretical, or more likely a mixture of both.
4. Moore graphs. I'm fascinated by the missing Moore graph. I have something I'd like to try with it, in terms of counting walks and certain subgraphs of the graph if it exists. Of course there is much not known about the degree-diameter problem generally, and plenty of scope for original work.
5. Suppose I have a k-regular bipartite graph on 2n vertices (where n>2k) and I know that among all such graphs my graph has the most 4-cycles. Does my graph necessarily contain a complete bipartite component? Can also ask similar questions for 6-cycles, 8-cycles,...

## Permutations

What is the smallest subset S of the permutations of {1,2,3,...,n} with the property that every other permutation of {1,2,3,...,n} agrees with at least one member of S in at least k places? This problem has connections with something called "covering radius" in coding theory, as well as with transversals in latin squares. It can also be phrased in terms of finding a small dominating set in a certain graph.

1. What is the largest power of 2 that divides the permanent of a Hadamard matrix of order n? Is this power the same for every Hadamard matrix of a given order? If so, this would be prove a conjecture that the permanent of a Hadamard matrix never vanishes.
2. Do Hadamard matrices exist for all orders that are multiples of 4? Of course that is a big question, but I wouldn't mind do what we can to chip away at it.
3. Another classic: Prove that there is no circulant Hadamard matrix of order greater than 4. How hard can it be??? (Ans, probably quite hard, but then it is a fascinating question...).

## Contact Information

Tel: +61 3 99054442
E-mail: Is of the standard form firstname.lastname@sci.monash.edu.au
Snail-mail:
```
Dr Ian Wanless
School of Mathematical Sciences
Monash University
Vic 3800 Australia
```