Graph Classes of Bonded Shrubdepth
Mathematics
Final Report Abstract
In the last years many theoretically interesting and possibly practically relevant results have been achieved about sparse structures. A structure is sparse if it has not many relations between its elements compared to the number of elements. The cutting edge of the research in this direction is to transfer those results to dense structures. The general idea is to find an internal sparse structure in a dense one. Structures that have such a sparse backbone can be called structurally sparse. We improved our knowledge and intuition around the modern notions dealing with density. Those notions include logical, model-theoretical, algorithmic and combinatorial aspects that can be nicely combined in the sparse case. In our work, we established a connection between some dense variants of those notions. As not unusual in fundamental research, practical applications of our results is a matter of the distant future. A possible way to them is over an even deeper understanding of structurally sparse dense structures to constructing efficient algorithms for them for everyday computational problems that probably have no efficient solution in general.
