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:
- Latin squares,
- matrix permanents
- graph theory
- permutations
- Hadamard matices
Below is a sample of questions that interest me. My actual wishlist
is a lot longer than this though...
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.
- Why are the numbers of latin squares divisible by such a
high power of two?
- Can you build a latin square of every order > 6 that does
not have any proper latin subsquares?
- Does every latin square of odd order have a transversal?
Does every latin square of even order have a near transversal?
- Estimate the number of transversals of the cyclic groups of odd order.
(Equivalently, estimate the number of complete mappings/orthomorphisms).
- Computational searches for sets of mutually orthogonal latin squares
(MOLS) aimed at finding families of such objects.
- 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...
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:
-
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.
-
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.
-
Attack any of the remaining questions in Minc's famous catalogue of
conjectures and open problems.
A graph in this sense is a network of nodes and connections between
nodes. Here are some possible project topics:
- 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.
- 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?
- 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.
- 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.
- 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,...
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.
-
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.
-
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.
-
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
Back to my home page