Researchers: Dr Raymond Booth, Associate Professor Vladimir Ejov , Professor Jerzy Filar (leader), Dr David GlynnDr 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 safety-critical 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 (determinant-like functions such as hyperdeterminants and the permanent of a matrix)
  • Coding Theory (which are used for error-correction in things like CDs and DVDs and for error-free communications)
  • Quantum Codes (which will be necessary once the next-generation 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 socio-technical systems.
Illustration of the Four Colour Problem
Illustration of the Four Colour Problem

 

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 sub-cycles. 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^{n-1} 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, Addison-Wesley, 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 long-distance communication systems. The Reed-Solomon codes are examples, see Reed-Solomon error correction.

They are also commonly used in cryptography, see MDS matrix. Geometrically they are equivalent to k-arcs 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 Reed-Solomon 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 9-point and Desargues 10-point 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 3-regular bipartite graph with 2n vertices and 3n edges associated with such a configuration and it would have very interesting properties, see Levi graph.


Moebius 8_4 configuration

 

 

Glynn 8_4 configuration on a hyperbolic quadric  

MP4 - Configuration on a hyperbolic quadric