This page was translated automatically using artificial intelligence (DeepL). The German version is binding. More information about automatic translation
News Intranet
This page was translated automatically using artificial intelligence (DeepL). The German version is binding. More information about automatic translation
On 20 March 2023, Hany Ibrahim successfully defended his doctoral thesis, entitled “Edge Contraction and Forbidden Induced Subgraphs”, at the Faculty of Mathematics and Computer Science at the Technical University Bergakademie Freiberg. The thesis was produced as part of a joint doctoral programme between Mittweida University of Applied Sciences and the Technical University Bergakademie Freiberg and was funded by an ESF grant.
Networks play an immense role in our lives. We all live within a network of social relationships and are surrounded by technical networks (road networks, water supply networks, computer networks). Last but not least, we all have a vast neural network in our minds. All these networks are the subject of scientific research. From a mathematical perspective, they all have something in common: their structure can be modelled using the language of graph theory. A graph is an abstract model, consisting of nodes and edges, which represents the topology of a network. However, graphs (networks) are generally not constant over time; they are subject to change, for example due to construction work, technical failures or biological development. Furthermore, graphs are often deliberately altered locally (reductions) to make it easier to calculate certain parameters.
An important question in this context is how graph properties – such as connectivity or independence properties – change when the graph is modified locally. This is precisely where Hany Ibrahim’s research project comes in. In his PhD project, he is investigating the characterisation of graph properties that are preserved when edges are contracted. Graph classes that can be defined by forbidden subgraphs play an important role in this context. To put it more simply, these are networks that must not contain certain patterns or local substructures. The figure shows a graph in which the specified subgraph (H) occurs twice, whilst another (L) does not occur at all.
These graph classes play a major role in questions concerning the computational complexity of problems on graphs. Often, problems that are generally extremely difficult to compute on arbitrary graphs (NP-hard problems) can be solved efficiently on restricted graph classes.
To this end, Hany Ibrahim first developed a hierarchy of graph classes, as well as a theory of relations and constructions for these classes, which then enabled him to characterise known classes of graphs in a new way through contraction properties. The mathematical proofs required to establish the correctness of this characterisation are technically extremely demanding. The results of the doctoral thesis suggest further interesting applications in the structural theory of graphs.
Hany Ibrahim worked in the Discrete Mathematics research group led by Professor Peter Tittmann. As well as their shared enthusiasm for research into graph theory, the two are united by their common hobby of hiking. Although Hany Ibrahim only moved to Germany from Cairo a few years ago, he actually knows far more hiking trails in Saxony from his own experience than most of the people who have lived here for a long time.