Researchers: Dr Raymond Booth, Associate Professor Vladimir Ejov , Professor Jerzy Filar (leader), Dr David Glynn, Dr Michael Haythorpe, Mr Serguei Rossomakhine , Dr Shaowen Qin
The advent of high speed computing accompanied by advances in theoretical computer science and engineering are just some of the current drivers of discrete mathematics. For instance, the “four colour problem” that asks whether every planar map could be coloured with just four colours so that no two adjacent regions have the same colour, stimulated much research in graph theory.
That problem was first posed in 1852 and finally proved, in the affirmative, by Appel and Haken in 1976 using computing methods in ways that would have been unimaginable only a few decades earlier. Discrete mathematics has played a critical role in fundamental problems of information technology, codes, cryptography, bioinformatics, statistical designs, computational geometry and safetycritical systems. In business applications, the closely related problems of integer programming and shortest and critical path methods of operations research have established a direct link with the subject of optimisation, or mathematical programming.
Consequently, the work of Flinders’ Discrete Mathematics, Optimisation and Operations Research group focuses on problems such as:
 Minimal Networks (the linking of given points by the most economical routes, especially Steiner networks)
 Finite Geometry (e.g. linear codes correspond to sets of points in geometries over finite fields)
 Combinatorics (counting methods are used a lot here)
 Invariant Theory (determinantlike functions such as hyperdeterminants and the permanent of a matrix)
 Coding Theory (which are used for errorcorrection in things like CDs and DVDs and for errorfree communications)
 Quantum Codes (which will be necessary once the nextgeneration quantum computers are here)
 Analysis of the famous Hamiltonian cycle and closely related travelling salesman problems
 Development of algorithms and heuristics for the above problems
 Perturbation theory for mathematical programming problems
 Design optimisation of complex processes and sociotechnical systems.
Professional and community engagement
David Glynn is an assessor for the Australian Research Council (ARC) as an "expert of International standing".
Jerzy Filar serves as Associate Editor of Operations Research published by INFORMS and is the winner of the 2005 Ren Potts Medal Awarded by ASOR (Australian Society of Operations Research).
Shortest network problems
Given a set of points in the plane, (or in three dimensional space), a Steiner network is a tree of shortest total length interconnecting the given points. Extra junctions are permitted. Much is known about the general problem in the two dimensional case, due to much activity since 1961.
A significant contribution to the problem was provided by Dr Jia Weng, who researched here at Flinders University in the early 1990s, and subsequently at the University of Melbourne. But there are still questions requiring satisfactory answers in three dimensions for as few as four given points. Ray has been considering these problems since 1985, and continues to do so with people at the University of Melbourne.
Hamiltonian cycle problem from a stochastic perspective
In 1994, Jerzy Filar and Dmitry Krass introduced the idea of embedding two famous combinatorial optimisation problems: the Hamiltonian Cycle (HCP) and Travelling Salesman (TSP) problems in singularly perturbed controlled Markov chains.
The key idea was to treat simple cycles in a graph as ergodic classes of Markov chains and to use a (singular) perturbation technique to differentiate between Hamiltonian cycles and unions of disjoint subcycles. This innovation led both to theoretical characterisations of Hamiltonian cycles and algorithmic approaches based on the properties of the perturbed stationary distributions of these chains.
More recently we continued this line by considering the limiting behaviour of fundamental matrices of the underlying Markov chains in the class of doubly stochastic matrices. This led to interesting asymptotic analysis that recently culminated in a major result:
The Hamiltonian cycle problem is equivalent to the problem of minimising the variance of a first return time to the home node; in a singularly perturbed controlled Markov chain over the convex space of stationary controls inducing doubly stochastic transition matrices, provided that the perturbation is sufficiently small.
Algorithmic advances are also being made with increasingly more complex graphs being solved either by exact algorithms, or by heuristics. There is now a large team consisting of FMSL staff members, students, and national and international researchers working on this problem. The work on HCP can be seen on the Flinders Hamiltonian Cycle Project website.
Euler’s Knight’s Tour Problem
Permanent of a matrix
In 2010 David Glynn published a formula to calculate the permanent of a square n by n matrix which appears to be even faster than the previously known algorithm due to H.J. Ryser (1963). It uses the order of 2^{n1} operations (times a polynomial factor) whereas Ryser's uses the order of 2^n operations. See Computing the_permanent, and also D.E. Knuth, The Art of Computer Programming, Vol. 2, AddisonWesley, 1981, page 497, Exercise 11.
If there is a way to obtain the permanent with the number of operations being only a polynomial in n (not exponential in n), then the important P=NP? problem would be solved in the affirmative. At the moment we are working on even faster generalisations of the known formulae, which involve investigations about a classical algebraic variety called the "Veronesean".
Maximal Distance Separable (MDS) Codes
Another direction of David Glynn’s research is in codes and especially MDS codes. These are in some ways the best, most efficient codes. They are used in particular in CDs, DVDs and in longdistance communication systems. The ReedSolomon codes are examples, see ReedSolomon error correction.
They are also commonly used in cryptography, see MDS matrix. Geometrically they are equivalent to karcs or hyperovals (sets of points in space that are maximally independent). There has been much work in this area (starting with B. Segre in Italy in the 1950s) but there are still major unsolved problems such as classifying the maximal MDS codes for many dimensions over larger finite fields. In most dimensions it appears that the ReedSolomon codes are optimal but for a limited number of dimensions there are known to exist other MDS codes that are at least as good (e.g. the code of length 10 in dimension 5 over the finite field GF(9) discovered by Glynn; see arc).
Fundamental configurations in geometry
In the last few years David Glynn has developed a method to construct many of the fundamental configurations in geometry (such as Pappus, Moebius, Reidemeister, bundle theorem) by using maps with certain properties on a topological surface (e.g. in the plane). There are still gaps in the theory, such as how to put Desargues configuration into this picture, and so further research is needed.
One problem is to see if Pappus 9point and Desargues 10point configurations can be generalised. Do there exist configurations with n>10 points and n lines in the plane with three points on each line, and three lines through each point, such that when one constructs the configuration in the plane the final point/line incidence is automatic? There is a 3regular bipartite graph with 2n vertices and 3n edges associated with such a configuration and it would have very interesting properties, see Levi graph.


MP4  Configuration on a hyperbolic quadric
