Points are particularly discrete.
Discrete mathematics derives from the Latin discernere, which means “to separate”. “Discrete mathematics is about delimited or clearly separated objects – such as points, lines or sequences of integers,” explains Oswin Aichholzer, a computer scientist at Graz University of Technology (TU Graz). “Points are particularly discrete,” he adds with a grin. Smiling because, beyond that, the research area of discrete mathematics is very difficult to define. Discrete mathematics is about delimited objects of observation. Like the sequence of numbers, 1, 2, 3, 4 and so on. With this sequence, you always know which number follows the last one – it is “countable”. It is not countable, and therefore not discrete, if, for example, all numbers that can be represented as decimal numbers are considered. Between 1 and 2 is 1.5. Between 1.5 and 1.6 is 1.51. Between 1.51 and 1.52 is 1.511. Thus, between any two numbers there are an infinite number of other numbers – they are “uncountable”.
But it is much better to see discrete mathematics as the sum of its parts, as Bettina Klinz, head of the Institute of Discrete Mathematics, also confirms: “Basically, there is no clear definition. The boundaries are difficult to draw – they can be broad or narrow. It’s much easier to explain discrete mathematics through the issues we address.” Disciplines that are counted as discrete mathematics include cryptography, coding theory, combinatorics, graph theory, algebra, number theory, algorithm theory and discrete optimization. Meanwhile, we encounter some of these areas regularly in our everyday lives, but often without most of us being aware of it. Cryptography, for example, ensures that data can be encrypted and transmitted securely; something which is playing an increasingly important role in the digital world. Coding theory deals with codes, their properties and the detection and correction of errors that can occur during the transmission or storage of data. Ubiquitous codes in everyday life include national insurance numbers, supermarket bar codes and QR codes (the black and white squares encode bits 0 and 1). “To a certain extent, QR codes remain decipherable even when parts are missing or faded,” explains Bettina Klinz.
Discrete optimization
Her own speciality is discrete optimization, which deals with optimization tasks involving discrete/integer decisions. For example, should a factory be built on one site or not? How many vehicles are needed to handle all planned trips? What the mathematician particularly appreciates about her field of research is that it covers the range between basic research and concrete application. In the area of fundamentals, the focus is on issues such as the optimal planning of journeys on the basis of various criteria, such as costs, journey duration or sustainability. But it is also about the most efficient routes for drills that drill holes in circuit boards. “Questions like these may sound simple and banal, but a drill like this has to drill 10,000 holes a day. It is very important for it to have an efficient sequence of movements,” explains Klinz.
Long before there were practical optimization problems such as those mentioned above, the mathematician Leonhard Euler laid essential foundations for discrete mathematics in the 18th century. He formulated and solved the Seven Bridges of Königsberg problem, in which all seven bridges in Königsberg are to be crossed once and once only and at the end the walker is to be returned to the starting point. The same question arises when you want to draw a given closed figure (for example a lantern) without putting down the pencil or twice drawing a line. “Euler already recognized at that time that the task can be abstracted with the help of a model with points (places) and lines (bridges/routes). This creates a so-called graph with nodes (points) and edges (lines). Mathematicians still work with such abstract graphs today – and not only in graph theory. “Only two things are relevant to the answer to Euler’s question: can you reach any other point from any point? And do all the points have an even number of neighbouring points?” Then and only then is it possible to plan the route without duplicating routes. Procedures based on Euler’s considerations are still used in route planning today.
In optimization, in addition to the solution quality, the robustness factor is generally becoming more and more important. This means safeguarding decisions and solutions, such as chosen routes or a production and transport plan, against the effects of data uncertainties.” It is important to find solutions that react as stably as possible to changing framework conditions. “One idea is to safeguard the chosen solution against the worst-case scenario from today’s point of view and to adjust the plans continually. In a research project funded by the FFG, we are looking at robust optimization problems in transport planning.”
Discrete principles in computer science
Oswin Aichholzer is deputy head of the Institute of Software Technology and uses methods of discrete mathematics to create foundations for computer applications. So he is primarily involved in basic research, dealing with graphs and ways of making them comprehensible to a computer. “For example, we are currently working on making a computer understand curves in a graph. This is not such an easy problem to solve, especially when not all the information is available,” he explains. Graphs are relevant in train or road plans, for example, and become particularly crucial when crossings occur, when two supposedly parallel routes are not parallel by a small factor and intersect at some point. “Teaching this problem to a computer is difficult, but also extremely relevant in real-world route planning.”
He describes his research interests in discrete mathematics and computer science as “very specific”. This is because much is simply already known in these areas and it is necessary to dive very deeply into a topic in order to experience and discover something new. “We look at a problem very intensively and try to really understand it down to the smallest detail. So we can still find new, relevant interrelations about it.”
Algorithmic topology
Michael Kerber, deputy head of the Institute of Geometry, took over the leadership of the Doctoral Program in Discrete Mathematics at TU Graz in the autumn, a PhD training programme that TU Graz has been running together with the University of Graz and the University of Leoben for several years. The programme is in its final phase and will be extended until mid-2024. The Graz School of Discrete Mathematics is currently being founded, and is intended to continue the successful doctoral programme as a successor structure.
Michael Kerber’s work in the field of algorithmic topology is mainly concerned with simplicial complexes. These represent extensions of graphs in higher dimensions and make it possible to calculate with topological spaces as well. He classifies this area as part of discrete mathematics. “In contrast, if you only look at the properties of toplogical spaces, you end up with algebraic topology,” defines Kerber. In his current research project – funded by the Austrian Science Fund FWF – he is looking at the topological properties of objects on several scales. “You usually look at objects on one scale: if it’s further away, you see less detail, if it’s closer, you see more detail. Here the scale corresponds to the distance, but there are many more possible scales,” says Kerber. For example, the three colour channels of RGB images red, green and blue. Things get complicated when several scales are to be considered simultaneously. “Many things are simply no longer calculable and this procedure was long considered too difficult and unfeasible. But in recent years, the field has picked up again with the algorithmic consideration of multi-parameters.” Areas of application are then machine learning and biotechnology.
Defined field without definition
Discrete mathematics is much needed and extensively used in diverse areas of science, in theory as well as in application. But there is no clear definition. “Many mathematicians don’t care what the field in which they work is called. What is important for us is to gain new knowledge and insights as well as to solve unsolved mathematical problems beforehand, and any kind of mathematics that serves this goal is welcome,” concludes Bettina Klinz. And that is actually also a beautiful summary.
This research area is anchored in the Field of Expertise “Information, Communication & Computing”, one of five strategic foci of TU Graz.
You can find more research news on Planet research. Monthly updates from the world of science at Graz University of Technology are available via the research newsletter TU Graz research monthly.
