Department of Mathematical Sciences


Discrete Mathematics

Research undertaken by this group’s two faculty members, Professor Helmut Prodinger and Dr Stephan Wagner, lies in the intersection of several branches of mathematics, including combinatorics, graph theory, analysis, also number theory and probability theory to a certain extent. There is active collaboration with other South African universities, and the group also keeps strong international contacts, with researchers from Germany, Spain, China, France, Austria, Belgium, the United States and other countries.

Analysis of algorithms, which involves understanding the complexity of algorithms, is the main research interest of Prof Prodinger. Worst-case evaluations are widely explored in the literature, however Prof Prodinger’s approach focuses on methods for average-case and probabilistic analysis.

Properties of random strings, permutations, trees and graphs are essential ingredients in this work. Motivation and problems often come from computer science.

Enumeration problems, in particular counting in a graph-theoretical context, form the main research focus of Dr Wagner. Graph theoretical parameters are used in theoretical chemistry for predicting the physical behaviour of molecules, and they also play a role in statistical mechanics. A particularly interesting class of graphs in this context is the class of self-similar graphs, which are related to fractal shapes. Natural questions that arise are: Which graphs within a given class maximise or minimise a certain parameter? What is the average (exact or asymptotic) value of a certain parameter? How can one compute the (exact or asymptotic) values for specific types of graphs?

Part of Prof Wild’s research (besides lattice theory) involves combinatorial enumeration, but his focus Is more on programming techniques (as opposed to theoretic complexity analysis) for NP-hard enumeration problems, such as counting all Hamiltonian cycles or all closed sets of a closure system.

There are plenty of possibilities for research in this area, since several branches of mathematics interact. Details of specific projects may be obtained from the members of the group. For an idea of the research involved please refer to the group members’ webpages.
Some recent publiscations showing the work of the group:

  1. C. Heuberger and H. Prodinger, On alpha-greedy expansions of numbers, Advances in Applied Mathematics, 38 (2007), 505-525.
  2. C. Heuberger and S. Wagner, Chemical Trees Minimizing Energy and Hosoya Index, Journal of Mathematical Chemistry 46/1 (2009), 214- 230.
  3. G. Louchard and H. Prodinger, Generalized Approximate Counting Revisited, Theoretical Computer Science 391 (2008), 109-125.
  4. A. Panholzer and H. Prodinger, The level of nodes in increasing trees revisited, Random Structures and Algorithms 31 (2007), 203-226.
  5. H. Prodinger, Records in geometrically distributed words: sum of positions, Applicable Analysis and Discrete Mathematics 2 (2008), 234-240.
  6. H. Prodinger and S. Wagner, Minimal and maximal plateau lengths in Motzkin paths, Proceedings of the 2007 Conference on Analysis of Algorithms, Juanles pins, June 17-22, 2007, pp. 353-362.
  7. E. Teufl and S. Wagner, Enumeration problems for classes of selfsimilar graphs. Journal of Combinatorial Theory, Series A 114/7 (2007), 1254-1277.
  8. S. Wagner, On the average Wiener index of degree-restricted trees, Australasian Journal of Combinatorics 37 (2007), 187-203.
  9. S. Wagner, On tries, contention trees and their analysis, Annals of Combinatorics 12/4 (2009), 493-507.