Search

Abstract Corona, Klimawandel, Künstliche Intelligenz, Massenverfahren und Vieles mehr – die Herausforderungen der Moderne sind mit den traditionell dogmatischen, einzelfallbezogenen Methoden der Rechtswissenschaft und dem im FAZ-Politikteil erworbenen Allgemeinwissen kaum noch zu bewältigen. Daten und ihre Analyse rücken immer mehr in den Mittelpunkt. Abseits von rituell wiederholten Floskeln wie „Big Data ist die Zukunft!“, „KI wird grundlegende Veränderungen hervorrufen!“ und dem allseits beliebten „Daten sind das neue Öl!“ agieren Jurist:innen weitgehend hilf- und mutlos in dieser neuen Welt. Wahrheit wird in der Moderne zunehmend durch Statistik geschaffen. Statistische Kennzahlen wie die 7-Tage-Corona-Inzidenz haben die Macht, eine gesamte Gesellschaft abzuschalten. Der Klimawandel ist kein einzelnes Ereignis, sondern vollzieht sich schleichend in Zehntel-Grad-Schritten, die kontinuierlich die prozentuale Wahrscheinlichkeit für Extremwetter, Naturkatastrophen und das Kippen von Umweltsystemen erhöhen. Große Sprachmodelle wie ChatGPT und GPT-4 erwecken den Eindruck, durch die statistische Vervollständigung von Wortfolgen wahre Antworten auf allgemeine und fachliche Probleme des Lebens geben zu können. Aber auch abseits dieser Megatrends beruht unser Verständnis von Wahrheit (z.B. Meinungsumfragen als Wählerwille, Wirksamkeit von Medikamenten, Beweiskraft von Gentests, Aufdeckung von gesundheitlichen Risiken durch kommerzielle Produkte) auf statistischen Hochrechnungen. Wie können Jurist:innen – und vor allem Richter:innen – mit Wahrheit und Wahrscheinlichkeit besser umgehen lernen? Wie lässt sich für Praktiker:innen zumindest eine Basiskompetenz in der Datenanalyse erwerben? Legal Data Science kann eine Brücke zwischen dem Informationsbedarf praktizierender Jurist:innen und den komplexen Wahrheiten der Moderne schaffen. Wir werden einige grundlegende Konzepte besprechen, hilfreiche (aber grobe!) Leitlinien aufstellen und danach sofort an praktischen Problemen arbeiten und dafür leicht zu erlernende, aber sehr nützliche statistische Methoden anwenden. Der praktische Teil ist zum Mitmachen! Sie können selbstverständlich zusehen, aber nur in der Anwendung lernt man Datenanalyse richtig. Testen Sie bitte im Vorfeld den Link zu dem Statistik-Werkzeug R, indem Sie „1+1“ eingeben und „Enter“ drücken: https://webr.r-wasm.org/latest/ (benötigt 1-2 Minuten zum Laden). Es ist keine Installation notwendig, alles passiert lokal in Ihrem Browser. Kontext Diese Präsentation war Grundlage für den von Seán Fobbe am 3. Mai 2023 auf Einladung der Digitalen Richterschaft gehaltenen Vortrag »Legal Data Science: Der moderne Weg zur Wahrheit«. Varianten Die Präsentation ist in zwei Varianten veröffentlicht: Nur Folien Folien und Notizen (Hinweise, Literatur zur Vertiefung und Quellenangaben) Einstieg in Legal Data Science Um Ihnen den Einstieg in Legal Data Science zu erleichtern habe ich für Sie auf meiner Homepage eine Materialsammlung zusammengestellt: Wie fange ich mit Legal Data Science an? Vertiefung Fobbe, S. (2022). Legal Data Science verständlich erklärt — Teil I: Was ist das?. Legal Tribune Online. https://www.lto.de/persistent/a_id/48673/ Fobbe, S. (2022). Legal Data Science verständlich erklärt — Teil II: Wie man sie nutzen kann. Legal Tribune Online. https://www.lto.de/persistent/a_id/49024/ Fobbe, S. (2021). Juristische Netzwerkdaten für Einsteiger. RECHTS|EMPIRIE. https://rechtsempirie.de/10.25527/re.2021.11/juristische-netzwerkdaten-fuer-einsteiger/ Fobbe, S. (2021). Open Legal Data: Das Fundament des Rechtsstaates. VOTUM, Heft 1, 21–26. https://doi.org/10.5281/zenodo.4646696 Über den Vortragenden Seán Fobbbe ist Völkerrechtler und Legal Data Scientist. Seine Forschungsinteressen liegen im internationalen Menschenrechtsschutz, der Friedensforschung, dem Kulturgüterschutz und der maschinellen Analyse juristischer Texte mittels statistischer Methoden. Website: www.seanfobbe.de &nbsp

This thesis aims to study Costas arrays from different points of view. A Costas array of size n is an n × n binary matrix such that no two of the (n/2) line segments connecting 1s have the same length and slope. Costas arrays are attractive, highly combinatorial objects with applications in radar engineering and signal processing that motivates us to study them carefully. Firstly, we investigated equivalent definitions and the methods, based on finite fields, that allow us to construct Costas arrays for infinitely many sizes, but not all sizes. There are three main approaches currently being considered to study Costas arrays; algebraic constructions based on finite fields by which we can construct Costas arrays of sizes equal to or a bit less than prime powers (systematically constructed). The other method is computer search, and the third is heuristic techniques. The enumeration of all Costas arrays up to size 29 has been completed via exhaustive search methods, revealing that more than 90% of these arrays are of completely unknown origin, called sporadic Costas arrays. So far, there is a general lack of research on the properties of sporadic Costas arrays, indicating an unclear relationship between sporadic Costas arrays and systematically constructed ones. One possible approach to make a link between systematically constructed Costas arrays and sporadic ones could be defining transformations that transform systematically generated Costas arrays to sporadic ones and vice versa. Our primary concern is to examine how it is possible to transform a given Costas array to obtain another Costas array or create another array close to being a Costas array and then examine the violation causes to the Costas property. Then, we can investigate the possible ways to eliminate or reduce these violation causes. We introduce a new transformation with the property that we can obtain another Costas array by transforming a given one for some Costas arrays. Surprisingly, some of the systematically constructed Costas arrays produce sporadic Costas arrays after applying the transformation. Costas arrays have perfect aperiodic properties, a solid property to ask, namely permutation matrices with aperiodic autocorrelation of at most one. By applying our new transformation on a given Costas array, we obtain a new array with the property that the values of its aperiodic autocorrelation function for all possible non-zero shifts are at most two. These arrays are called almost Costas arrays. We will also examine Costas arrays from permutation points of view and prove that we could not construct a Costas array for a specific class of permutation, namely odd permutation. The distinctness of all line segments formed by joining pairs of ones in a given Costas array implies that a permutation matrix fails to be a Costas array if and only if it includes ones that form a (possibly degenerate) parallelogram. We refer to these parallelograms as forbidden configurations. Therefore, a Costas array has no forbidden configurations. Consequently, a permutation matrix is close to being a Costas array if and only if it contains as few as possible forbidden configurations. With this in mind, we investigate the number of forbidden configurations in some classes of permutation matrices and introduce a transformation by which we can reduce the total number of forbidden configurations for these classes. We discover a close relationship between the class of odd permutations and exponential Welch Costas arrays. Exponential Welch Costas arrays have G-symmetric properties. We will show how G-symmetric arrays can be constructed using transforming odd permutations. Moreover, we realized that this transformation significantly reduces the number of forbidden configurations in a given odd permutation array. This perspective also helped us to construct a class of permutation polynomials over finite fields that is differentially at most 6-uniform, meaning the permutation matrices associated with this permutation polynomials have the property that for all possible non-zero shifts, the periodic autocorrelation function values are at most 6. These differentially 6-uniform mappings can be constructed by transforming an inverse function over a finite field. We also observe that constructing G-symmetric permutation matrices from odd permutations leads to much fewer forbidden configurations, meaning the permutation matrices associated with these transformed odd permutations are closer to Costas arrays. Moreover, we will see that all G-symmetric Costas arrays of even sizes can be found by applying this transformation on odd permutations. This attitude allows us to search for G-symmetric Costas arrays by checking the Costas property of (2 n/2 x (n/2)!) permutation matrices instead of n!, which results in a notable reduction in the search space. In the last chapter, we discuss a surprising link between exponential Welch Costas arrays and power mappings constructed over a finite field with p elements, where p is a prime. We determine the maximal aperiodic crosscorrelation of pairs of power mappings using an exhaustive search. In some exceptional cases, we will provide theoretical proof for the maximal crosscorrelation of the family of power mappings. We will discuss how the maximal crosscorrelation of the family of power mappings is almost the same as the maximal crosscorrelation of the family of exponential Welch. This observation motivates us to extend the family of Welch Costas arrays with the family of power mappings and then investigate the maximal crosscorrelation of this extended family. We determine the maximal crosscorrelation of this extended family by exhaustive search. Surprisingly, the maximal crosscorrelation of this extended family is equal to the maximal crosscorrelation of the family of exponential Welch, constructed over a finite field with p elements, where p is not a safe prime. In the case where p is a safe prime also, there is a close relationship that we will discuss. Moreover, we will discuss why providing theoretical proof for our observed results regarding the maximal crosscorrelation of this extended family can be tremendously complex. Families of arrays with low crosscorrelation properties are desirable for application in multiuser and multiplexing systems. Therefore, families of Costas arrays with low crosscorrelation are beneficial for such applications. With this in mind, we will introduce a subfamily of Lempel-Golomb Costas arrays that indicate lower crosscorrelation than the family of all Lempel- Golomb Costas arrays., In dieser Dissertation sollen Costas-Matrizen aus verschiedenen Blickwinkeln untersucht werden. Eine Costas-Matrix der Größe n ist eine n × n 0-1-Matrix, bei der keine zwei der (n2 ) Liniensegmente, die Einsen verbinden, die gleiche Länge und Steigung haben. Costas-Matrizen sind Interessant, kombinatorische Objekte mit Anwendungen in der Radartechnik und der Signalverarbeitung, die uns dazu motivieren, sie sorgfältig zu untersuchen. Zunächst untersuchten wir die äquivalenten Definitionen und die auf endlichen Körpern basierenden Methoden, die es uns erlauben, Costas-Matrizen für unendlich viele Größen, aber nicht für alle Größen, zu konstruieren. Derzeit werden drei Hauptansätze zur Untersuchung von Costas-Matrizen erwogen: algebraische Konstruktionen auf der Grundlage der Theorie endlicher Körper, mit denen wir Costas-Matrizen mit Größen gleich oder etwas kleiner als Primzahlen konstruieren können (systematisch konstruiert). Die zweite Methode ist die Computersuche, und die dritte sind heuristische Techniken. Die Aufzählung aller Costas-Matrizen bis zur Größe 29 wurde mit Hilfe erschöpfender Suchmethoden abgeschlossen, wobei sich herausstellte, dass mehr als 90% dieser Matrizen völlig unbekannten Ursprungs sind, nämlich die so genannten sporadischen Costas-Matrizen. Bislang ist die Beziehung zwischen sporadischen Costas-Matrizen und systematisch konstruierten Matrizen unklar. Ein möglicher Ansatz, eine Verbindung zwischen systematisch konstruierten Costas-Matrizen und sporadischen Matrizen herzustellen, könnte darin bestehen, Transformationen zu definieren, die systematisch generierte Costas-Matrizen in sporadische umwandeln und umgekehrt. unser Hauptziel ist es, zu untersuchen, wie es möglich ist, eine gegebene Costas-Matrix umzuwandeln, um eine andere Costas-Matrix zu erhalten oder eine andere Matrix zu erstellen, die einer Costas-Matrix nahe kommt, und dann die Ursachen der Verletzung der Costas-Eigenschaft zu untersuchen. Anschließend können wir untersuchen, wie sich die Ursachen für diese Verstöße beseitigen oder verringern lassen. Wir führen eine neue Transformation ein, die einige Costas-Matrizen in andere Costas- Matrix transformiert. Überraschenderweise ergeben einige der systematisch konstruierten Costas-Matrizen nach Anwendung der Transformation sporadische Costas-Matrizen. Costas-Matrizen haben perfekte aperiodische Eigenschaften, was bedeutet, dass diese Permutationsmatrizen eine aperiodische Autokorrelation von höchstens eins haben. Durch Anwendung unserer neuen Transformation auf eine gegebene Costas-Matrix erhalten wir eine neue Matrix mit der Eigenschaft, dass die Werte ihrer aperiodischen Autokorrelationsfunktion für alle möglichen Verschiebungen ungleich Null höchstens zwei sind. Diese Matrizen werden als Fast-Costas-Matrizen bezeichnet. Wir werden Costas-Matrizen auch unter Permutationsgesichtspunkten untersuchen und beweisen, dass wir für eine bestimmte Klasse von Permutationen, nämlich ungerade Permutationen, keine Costas-Matrizen konstruieren können. Die Unterscheidbarkeit aller Liniensegmente, die durch das Verbinden von Paaren von Einsen in einer gegebenen Costas- Matrize gebildet werden, impliziert, dass eine Permutationsmatrix dann und nur dann keine Costas-Matrix ist, wenn sie Einsen enthält, die ein (möglicherweise entartetes) Parallelogramm bilden. Wir bezeichnen diese Parallelogramme als verbotene Konfigurationen. Eine Costas- Matrix hat also keine verbotenen Konfigurationen. Folglich kommt eine Permutationsmatrix einer Costas-Matrize nur dann nahe, wenn sie so wenige verbotene Konfigurationen wie möglich enthält. Vor diesem Hintergrund untersuchen wir die Anzahl der verbotenen Konfigurationen in einigen Klassen von Permutationsmatrizen und führen eine Transformation ein, mit der wir die Gesamtzahl der verbotenen Konfigurationen für diese Klassen reduzieren können. Wir entdecken eine enge Beziehung zwischen der Klasse der ungeraden Permutationen und exponentiellen Costas-Matrizen. Exponentielle Costas-Matrizen haben G-symmetrische Eigenschaften. Wir werden zeigen, wie G-symmetrische Matrizen durch Transformation ungerader Permutationen konstruiert werden können. Außerdem haben wir festgestellt, dass diese Transformation die Anzahl der verbotenen Konfigurationen in einer gegebenen Matrize mit ungeraden Permutationen erheblich reduziert. Diese Perspektive hat uns auch geholfen, eine Klasse von Permutationspolynomen über endlichen Körpern zu konstruieren, die differentiell höchstens 6-uniform ist, was bedeutet, dass die Permutationsmatrizen, die mit diesen Permutationspolynomen verbunden sind, die Eigenschaft haben, dass für alle möglichen Nicht- Null-Verschiebungen die periodischen Autokorrelationsfunktionswerte höchstens 6 sind. Diese differentiell 6-uniformen Abbildungen können durch Transformation einer Umkehrfunktion über einen endlichen Körper konstruiert werden. Wir beobachten auch, dass die Konstruktion von G-symmetrischen Permutationsmatrizen aus ungeraden Permutationen zu viel weniger verbotenen Konfigurationen führt, was bedeutet, dass die mit diesen transformierten ungeraden Permutationen verbundenen Permutationsmatrizen näher an Costas-Matrizen sind. Außerdem werden wir sehen, dass alle G-symmetrischen Costas-Matrizen gerader Größe durch Anwendung dieser Transformation auf ungerade Permutationen gefunden werden können. Diese Sichtweise ermöglicht es uns, nach G-symmetrischen Costas-Matrizen zu suchen, indem wir die Costas- Eigenschaft von (2 n/2 x (n/2)!) statt n! Permutationsmatrizen überprüfen, was zu einer beträchtlichen Reduzierung des Suchraums führt. Im letzten Kapitel diskutieren wir eine überraschende Verbindung zwischen exponentiellen Costas-Matrizen und Potenzabbildungen, die über einem endlichen Körper mit p Elementen konstruiert sind, wobei p eine Primzahl ist. Wir bestimmen die maximale aperiodische Kreuzkorrelation von Paaren von Potenzabbildungen mit Hilfe einer erschöpfenden Suche. In einigen Ausnahmefällen werden wir einen theoretischen Beweis für die maximale Kreuzkorrelation der Familie der Potenzabbildungen liefern. Wir werden erörtern, dass die maximale Kreuzkorrelation der Familie der Potenzabbildungen fast die gleiche ist wie die maximale Kreuzkorrelation der Familie der exponentiellen Welch. Diese Beobachtung motiviert uns, die Familie der Costas-Matrizen um die Familie der Potenzabbildungen zu erweitern und dann die maximale Kreuzkorrelation dieser erweiterten Familie zu untersuchen. Wir bestimmen die maximale Kreuzkorrelation dieser erweiterten Familie durch erschöpfende Suche. Überraschenderweise ist die maximale Kreuzkorrelation dieser erweiterten Familie gleich der maximalen Kreuzkorrelation der Familie der exponentiellen Welch, die über einem endlichen Körper mit p Elementen konstruiert wurde, wobei p keine sichere Primzahl ist. Auch für den Fall, dass p eine sichere Primzahl ist, gibt es eine enge Beziehung, die wir diskutieren werden. Außerdem werden wir erörtern, warum ein theoretischer Beweis für die von uns beobachteten Ergebnisse bezüglich der maximalen Kreuzkorrelation dieser erweiterten Familie äußerst komplex sein kann. Familien von Matrizen mit geringer Kreuzkorrelation sind für Anwendungen in Multiuser- und Multiplexing-systemen wünschenswert. Daher sind Familien von Costas-Matrizen mit geringer Kreuzkorrelation für solche Anwendungen von Vorteil. In diesem Sinne werden wir eine Unterfamilie von Costas-Matrizen einführen, die eine geringere Kreuzkorrelation aufweisen als die Familie aller Costas-Matrizen.

Mathematische Fachtermini haben verschiedene Ursprünge: Teilweise sind Wörter aus der Alltagssprache übernommen, teilweise aus Fremdsprachen. In manchen Fällen liegen diese Prozesse schon viele Jahrhunderte zurück, sodass die ursprüngliche Bedeutung der Fachtermini aufgrund von Sprachwandel in der Alltagssprache nicht mehr geläufig ist (Siebel, 2005). Davon ausgehend gibt es verschiedene Modelle zur Kategorisierung von Fachtermini, die beschreiben, ob mathematische Fachwörter auch in der Alltagssprache erscheinen und wenn ja, ob die Bedeutungen dort ähnlich oder verschieden sind (Meyer & Tiedemann, 2017; Vollrath, 1978). Die Kategorien sind jedoch nicht immer komplett trennscharf und manche Fachwörter sind schwer eindeutig einzuordnen. Pimm (1987, S. 77–93) und Vollrath (1978) beschreiben Schwierigkeiten im Schulunterricht beim Umgang mit Fachwörtern, die in der Alltagssprache mit einer ähnlichen oder ganz anderen Bedeutung vorkommen, während Staats (2009) die Chancen aufzeigt, die diese Homonymie bietet. Arbeiten zum Fachworterwerb von Studierenden sind uns nicht bekannt, dabei gibt es auch in der höheren Mathematik viele Termini, die alltagssprachliche Homonyme haben, wie z.B. Gruppe, Ring und Körper in der Algebra. Die hier vorgestellte Untersuchung soll einen Beitrag zu der Frage leisten, ob die Schwierigkeiten im Umgang mit aus der Alltagssprache bekannten Termini auch bei Studierenden bestehen und entsprechend in der universitären Lehre mehr berücksichtigt werden sollten.

Diskrete Mathematik und mathematische Modellierung haben viele Verbindungen. Wir beschreiben im Rahmen einer Fallstudie Modellierungsaktivitäten mit Lernenden am Ende der Sekundarstufe I. Die Lösungsprozesse der Lernenden für dieses graphentheoretische Optimierungsproblem werden beschrieben und ihr Vorgehen wird anhand der Phasen des Modellierungskreislaufs mit der Methode der qualitativen Inhaltsanalyse untersucht. Die Analyse erlaubt es, die Verbindung der erforderlichen Modellierungsteilkompetenzen mit der diskreten Mathematik herauszuarbeiten.

Vertex and edge orderings of graphs are commonly used in algorithmic graph theory. Such orderings can encode structural properties of graphs in a condensed way and, thus, they can be used to process a graph efficiently. A common approach to find particular vertex orderings are graph searches. Here, we study the complexity of deciding whether vertex orderings with special properties can be found by particular graph searches. The properties of these orderings concern their end-vertices, their search trees or constraints encoded by partial orders. Many graph classes can be characterized via special vertex orderings. We introduce another example, the semi-proper interval graphs, generalizations of connected proper interval graphs that are characterized via special variants of perfect elimination orderings. We study the structure of these graphs, present a linear-time recognition algorithm and show that they share some strong properties on Hamiltonian paths and cycles with proper interval graphs. We also generalize the notion of graph classes to the case of edge-weighted graphs. A weighted graph is a member of such a weighted class if subgraphs containing edges of particular weights are members of the respective unweighted graph class. We present conditions on an unweighted graph class that ensure a linear-time recognition algorithm for its corresponding weighted graph class. This conditions make use of a novel edge monotonicity and of particular edge orderings. We apply this result to three well-known graph classes, namely split graphs, threshold graphs, and chain graphs. Finally, we consider dynamic algorithms on threshold and chain graphs. These algorithms update certain properties of a graph after small modifications are applied to its vertex or edge set. We present certifying dynamic recognition algorithms of these classes, i.e., if the graph leaves the class after the modification, we can prove this by providing a forbidden induced subgraph of bounded size. Building on these results, we extend the notion of dynamic recognition algorithms to whole sets of edges and vertices. Furthermore, we present dynamic algorithms for the Hamiltonian path and cycle problems., Knoten- und Kantenordnungen von Graphen werden häufig in der algorithmischen Graphentheorie verwendet. Solche Ordnungen können Eigenschaften von Graphen in komprimierter Form kodieren und können damit zur effizienten Verarbeitung eines Graphen verwendet werden. Ein gängiger Ansatz, um bestimmte Knotenordnungen zu finden, sind Graphensuchen. Wir untersuchen hier wie schwer es ist zu entscheiden, ob Knotenordnungen mit speziellen Eigenschaften durch bestimmte Graphensuchen gefunden werden können. Die Eigenschaften dieser Ordnungen betreffen ihre Endknoten, ihre Suchbäume oder Einschränkungen, die durch partielle Ordnungen gegeben sind. Viele Graphenklassen lassen sich durch spezielle Knotenordnungen charakterisieren. Wir stellen ein weiteres Beispiel vor, die Semi-Proper-Intervallgraphen, Verallgemeinerungen von zusammenhängenden Proper-Intervallgraphen, die durch spezielle Varianten perfekter Eliminationsordnungen charakterisiert sind. Wir untersuchen die Struktur dieser Graphen, stellen einen Linearzeit-Erkennungsalgorithmus vor und zeigen, dass sie einige starke Eigenschaften in Bezug auf Hamiltonpfade und -kreise mit Proper-Intervallgraphen teilen. Wir verallgemeinern auch den Begriff der Graphenklassen auf den Fall von Graphen mit gewichteten Kanten. Ein gewichteter Graph ist Element einer solchen gewichteten Klasse, wenn Untergraphen mit Kanten bestimmter Gewichte Elemente der jeweiligen ungewichteten Graphenklasse sind. Wir präsentieren Bedingungen für eine ungewichtete Graphenklasse, die einen Erkennungsalgorithmus mit linearer Laufzeit für die entsprechende gewichtete Graphenklasse sicherstellen. Diese Bedingungen nutzen eine neuartige Monotonieeigenschaft und spezielle Kantenordnungen. Diese Ergebnisse wenden wir auf drei bekannte Graphenklassen an: Split-Graphen, Threshold-Graphen und Chain-Graphen. Am Ende betrachten wir dynamische Algorithmen für Threshold- und Chain-Graphen. Diese Algorithmen aktualisieren bestimmte Eigenschaften eines Graphen, nachdem kleinere Änderungen an seiner Knoten- oder Kantenmenge vorgenommen wurden. Wir stellen zertifizierende dynamische Erkennungsalgorithmen für diese Klassen vor, das heißt falls der Graph die Klasse nach der Modifikation verlässt, können wir dies mit einem verbotenen induzierten Untergraphen von beschränkter Größe beweisen. Aufbauend auf diesen Ergebnissen erweitern wir den Begriff der dynamischen Erkennungsalgorithmen auf ganze Mengen von Kanten und Knoten. Außerdem stellen wir dynamische Algorithmen für das Hamiltonpfad- und das Hamiltonkreis-Problem vor.

Die Netzwerkanalyse zielt darauf ab, nicht-triviale Erkenntnisse aus vernetzten Daten zu gewinnen. Beispiele für diese Erkenntnisse sind die Wichtigkeit einer Entität im Verhältnis zu anderen nach bestimmten Kriterien oder das Finden des am besten geeigneten Partners für jeden Teilnehmer eines Netzwerks - bekannt als Maximum Weighted Matching (MWM). Da der Begriff der Wichtigkeit an die zu betrachtende Anwendung gebunden ist, wurden zahlreiche Zentralitätsmaße eingeführt. Diese Maße stammen hierbei aus Jahrzehnten, in denen die Rechenleistung sehr begrenzt war und die Netzwerke im Vergleich zu heute viel kleiner waren. Heute sind massive Netzwerke mit Millionen von Kanten allgegenwärtig und eine triviale Berechnung von Zentralitätsmaßen ist oft zu zeitaufwändig. Darüber hinaus ist die Suche nach der Gruppe von k Knoten mit hoher Zentralität eine noch kostspieligere Aufgabe. Skalierbare Algorithmen zur Identifizierung hochzentraler (Gruppen von) Knoten in großen Graphen sind von großer Bedeutung für eine umfassende Netzwerkanalyse. Heutigen Netzwerke verändern sich zusätzlich im zeitlichen Verlauf und die effiziente Aktualisierung der Ergebnisse nach einer Änderung ist eine Herausforderung. Effiziente dynamische Algorithmen sind daher ein weiterer wesentlicher Bestandteil moderner Analyse-Pipelines. Hauptziel dieser Arbeit ist es, skalierbare algorithmische Lösungen für die zwei oben genannten Probleme zu finden. Die meisten unserer Algorithmen benötigen Sekunden bis einige Minuten, um diese Aufgaben in realen Netzwerken mit bis zu Hunderten Millionen von Kanten zu lösen, was eine deutliche Verbesserung gegenüber dem Stand der Technik darstellt. Außerdem erweitern wir einen modernen Algorithmus für MWM auf dynamische Graphen. Experimente zeigen, dass unser dynamischer MWM-Algorithmus Aktualisierungen in Graphen mit Milliarden von Kanten in Millisekunden bewältigt. Network analysis aims to unveil non-trivial insights from networked data by studying relationship patterns between the entities of a network. Among these insights, a popular one is to quantify the importance of an entity with respect to the others according to some criteria. Another one is to find the most suitable matching partner for each participant of a network knowing the pairwise preferences of the participants to be matched with each other - known as Maximum Weighted Matching (MWM). Since the notion of importance is tied to the application under consideration, numerous centrality measures have been introduced. Many of these measures, however, were conceived in a time when computing power was very limited and networks were much smaller compared to today's, and thus scalability to large datasets was not considered. Today, massive networks with millions of edges are ubiquitous, and a complete exact computation for traditional centrality measures are often too time-consuming. This issue is amplified if our objective is to find the group of k vertices that is the most central as a group. Scalable algorithms to identify highly central (groups of) vertices on massive graphs are thus of pivotal importance for large-scale network analysis. In addition to their size, today's networks often evolve over time, which poses the challenge of efficiently updating results after a change occurs. Hence, efficient dynamic algorithms are essential for modern network analysis pipelines. In this work, we propose scalable algorithms for identifying important vertices in a network, and for efficiently updating them in evolving networks. In real-world graphs with hundreds of millions of edges, most of our algorithms require seconds to a few minutes to perform these tasks. Further, we extend a state-of-the-art algorithm for MWM to dynamic graphs. Experiments show that our dynamic MWM algorithm handles updates in graphs with billion edges in milliseconds.

Die Arbeit begibt sich auf die Suche, was im wissenschaftlichen Kontext als Jugend zu verstehen ist und welchen Einfluss dies wiederum auf die damit verbundene Theoriebildung einer aktuell nur unstrukturiert vorhandenen Jugendarbeitstheorie hat. Das Erkenntisinteresse liegt darauf, eine Begrifflichkeit zu finden und diese mit universellen Kategorien und Attributen zu versehen, mit der eine Theoriebildung möglich wird. Diese von der individuellen Perspektive oder dem Normverständnis der jeweiligen Jugendarbeitstheorie oder Praxis, der Sozialen Arbeit, der jeweiligen Bezugswissenschaft, der Gesellschaft oder der die Arbeit finanzierenden Institutionen zu trennen, ist Untersuchungsgegenstand und Ziel zugleich. Dies wird nur möglich, indem der Begriff Jugend, auf dem sich dann die existierende Jugendarbeitstheorie aufbaut, untersucht und von der Vielfalt der Perspektiven zu Jugend abstrahiert wird. Im Rahmen der Arbeit wird mithilfe der Netzwerkanalyse nach Harrison White und der Graphentheorie, basierend auf den Überlegungen von Norbert Elias eine Analysemethode vorgestellt, um die unüberschaubare Menge an Beschreibungen von Jugend über die letzten Jahrhunderte zu strukturieren. Durch diese Analyse kann eine Definition von Jugend entwickelt werden, welche auch auf die grundlegenden Unterschiede von einer Perspektive der Herrschaft und einer der Emanzipation aufmerksam macht. Dadurch können kritische Machtperspektiven innerhalb der Sozialen Arbeit und dem Sozialstaat in Deutschland identifiziert werden. Die Arbeit schlägt eine allgemeingültige Definition von Jugend vor, welche durch die angewandte Methode flexibel und wandlungsfähig entsprechend wissenschaftlicher Maßstäbe bleibt., https://nbn-resolving.org/urn:nbn:de:bsz:l189-qucosa2-804689

Many recently published research papers examine the representation of nanostructures and biomimetic materials, especially using mathematical methods. For this purpose, it is important that the mathematical method is simple and powerful. Theory of fractals, artificial neural networks and graph theory are most commonly used in such papers. These methods are useful tools for applying mathematics in nanostructures, especially given the diversity of the methods, as well as their compatibility and complementarity. The purpose of this paper is to provide an overview of existing results in the field of electrochemical and magnetic nanostructures parameter modeling by applying the three methods that are “easy to use”: theory of fractals, artificial neural networks and graph theory. We also give some new conclusions about applicability, advantages and disadvantages in various different circumstances., publishedVersion

In this thesis, we present some new developments in the spectral theory of quantum graphs. The topics we are primarily interested in are nodal properties of Schrödinger operators on metric graphs, eigenvalue bounds for Laplacians on metric graphs and spectral minimal partitions of metric graphs. In the first part of this thesis, we establish metric graph counterparts of Pleijel’s theorem on the asymptotics of the number of nodal domains of the n-th eigenfunction(s) of a broad class of operators on compact metric graphs, including Schrödinger operators with a variety of vertex conditions as well as the p-Laplacian with standard vertex conditions. In the second part, we provide new eigenvalue estimates for Laplacians on metric graphs with standard vertex conditions. We are particularly interested in the role played by planarity or – more generally – embeddability into more general surfaces and derive upper eigenvalue bounds in dependence of the genus of said surface. An important tool in the proof of one of these bounds is a recently developed transfer principle by Amini and Cohen–Steiner. We demonstrate how this transfer principle can be used to also derive good lower eigenvalue bounds for graphs that possess certain types of so-called double covers. Finally, we derive eigenvalue bounds in terms of the graph’s inradius if on additionally imposes Dirichlet vertex conditions at some vertices. In the third and final part, we study properties of spectral minimal partitions of metric graphs within the framework recently introduced by Kennedy, Kurasov, Mugnolo and Léna. We provide sharp lower and upper estimates for minimal partition energies in different classes of partitions; while the lower bounds are reminiscent of the classic isoperimetric inequalities for metric graphs, the upper bounds are more involved and mirror the combinatorial structure of the metric graph as well. Combining them, we deduce that these spectral minimal energies also satisfy a Weyl-type asymptotic law similar to the well-known one for eigenvalues of quantum graph Laplacians with various vertex conditions., In der vorliegenden Arbeit stellen wir einige neue Ergebnisse der Spektraltheorie von Quantengraphen vor. Die Teilgebiete, für die wir uns hauptsächlich interessieren, sind Nodaleigenschaften von Schrödinger-Operatoren auf metrischen Graphen, Eigenwertabschätzungen für Laplace-Operatoren auf metrischen Graphen sowie Spektralminimalpartitionen von metrischen Graphen. Im ersten Teil stellen wir eine Quantengraphenversion des Satzes von Pleijel über das asymptotische Verhalten der Nodalzahl der n-ten Eigenfunktion vor. Die Klasse von Operatoren, mit der wir uns hierbei beschäftigen, sind einerseits Schrödinger-Operatoren mit sehr allgemeinen Knotenbedingungen und anderseits p-Laplace-Operatoren mit Standardknotenbedingungen. Im zweiten Teil leiten wir eine Reihe neuer Eigenwertabschätzungen für Laplace- Operatoren mit Standardknotenbedingungen her. Hierbei sind wir besonders an planaren Graphen oder Graphen, die sich in allgemeinere Flächen einbetten lassen, interessiert. Genauer gesagt, leiten wir obere Eigenwertabschätzungen in Abhängigkeit des topologischen Geschlechts des Graphen her. Ein wichtiges Hilfsmittel in einem der Beweise ist ein Transferprinzip von Amini und Cohen–Steiner. Wir zeigen, dass dieses Transferprinzip auch effektive Anwendungen für die Herleitung unter Eigenwertabschätzungen vorweist. Schließlich leiten wir Eigenwertabschätzungen in Abhängigkeit des Innenradiuses metrischer Graphen her, wobei wir hier zusätzlich annehmen, dass eine endliche Anzahl von Knoten mit Dirichlet-Bedingungen ausgestattet ist. Im dritten und letzten Teil der Arbeit beschäftigen wir uns mit der kürzlich von Kennedy, Kurasov, Mugnolo und Léna vorgestellen Theorie von Spektralminimalpartitionen metrischer Graphen. Wir erhalten untere und obere Abschätzungen für die zugehörigen Minimalpartitionsenergien her. Während die unteren Abschätzungen eher an bereits bekannte isoperimetrischen Abschätzungen für Eigenwerte erinnern, sind die oberen Abschätzungen komplizierter und spiegeln die kombinatorische Struktur des Graphen wider. Mit Hilfe der Abschätzungen sind wir in der Lage ein Weyl’sches Gesetz für die Minimalpartitionsenergien zu folgern.

Komplexität ist eine der großen Herausforderungen unserer Zeit. Daher müssen Ingenieure besonders in der Entwicklung die stetig steigende Komplexität in diversen Domänen beherrschen, um den Produkt- und damit Unternehmenserfolg zu realisieren. Für die zweckmäßige Modellierung der vielen verschiedenen Elemente und Relationen komplexer Systeme sind domänenübergreifende, integrative und damit holistische Modellierungsansätze erforderlich, welche jeweils kontextbezogen nützliche, mathematische Analyse- sowie Visualisierungsmöglichkeiten erlauben um Entwicklern eine multikriterielle Bewertung bestimmter Handlungsalternativen zu ermöglichen. Derzeit bestehende Ansätze eignen sich hierfür jedoch unter anderem aufgrund methodischer Defizite, ihres hohen Modellierungsaufwands, eingeschränkter Analyse- und Visualisierungsmöglichkeiten oder ihrer geringen Unterstützung bei der multikriteriellen Bewertung nur eingeschränkt. Daher wird in der vorliegenden Arbeit ein Konzept vorgestellt, mit dem Entwickler beim holistischen Komplexitätsmanagement in der Produktentwicklung unterstützt werden, indem kontextbezogen jeweils geeignete Methoden für die integrierte Modellierung, Analyse, Visualisierung und Bewertung komplexer Systeme für eine zielgerichtete Entscheidungsfindung zur Verfügung gestellt werden. Zur effektiven und effizienten Anwendung der Methodik wird ein IT-Werkzeug präsentiert, das Entwickler bei deren Aufgaben im Rahmen des holistischen Komplexitätsmanagements unterstützt., Complexity is one of the great challenges of our time. Therefore, especially in development, engineers must master the constantly increasing complexity in diverse domains in order to realize product and thus company success. For the appropriate modelling of the many different elements and relations of complex systems, cross-domain, integrative and thus holistic modelling approaches are required, which allow context-related, useful mathematical analysis as well as visualization possibilities in order to enable developers a multi-criteria evaluation of certain action alternatives. However, currently existing approaches are only suitable to a limited extent due to methodological deficits, their high modelling effort, limited analysis and visualization options, or their low support for multi-criteria evaluation. Therefore, this thesis introduces a concept to support developers in holistic complexity management in product development by providing contextually appropriate methods for integrated modelling, analysis, visualization, and evaluation of complex systems for goal-oriented decision making. For effective and efficient application of the methodology, an IT tool is presented that supports developers in their holistic complexity management tasks., FAU Studien aus dem Maschinenbau; 396

The increasing amount of automotive radar sensors leads to a higher risk of undesired interferences. Complex traffic scenarios comprise several vehicles, each one equipped with multiple sensors. As a result, a significant number of time-variable interference links are present in the scenario. Making use of the graph coloring theory, this paper analyzes a highway and an intersection scenario and gives boundaries regarding the minimum number of resources needed to completely suppress the existent interference links. Based on these results, the scenarios are simulated using the current unregulated scheme and considering a wise distribution of the sensor parameters. It is shown that even in such complex scenarios with thousands of interference links, it is possible to significantly reduce the interference if the available sensor resources are wisely assigned., acceptedVersion

This thesis contains results about embeddings and decompositions of graphs and hypergraphs.

In den letzten Jahren wurden komplexere Charakterisierungen von d��nnbesetzten Graphen, die nirgendwo-dichte Graphklassen und Graphklassen mit beschr��nkter Expansionumfassen. Beide fallen in die Kategorie der strukturellen Sparsit��t und erm��glichen in der Theorie eine Vielzahl effizienter Algorithmen.W��hrend es viele Charakterisierungen f��r diese Graphklassen gibt, kann eine in Form von schwachen F��rbungszahlen angegeben werden. F��r jeden Radius r ��� N werden diese durch lineare Ordnungen von Knoten eines Graphen definiert. Jede Ordnung von Knotenin einem Graphen hat eine schwache r-F��rbungszahl, und die schwache r-F��rbungszahl eines Graphen ist die minimale schwache r-F��rbungszahl der Ordnungen seiner Knoten.Die schwache r-F��rbungszahl eines Graphen misst Erreichbarkeitseigenschaften an der Entfernung r, hat aber auch direkte algorithmische Anwendungen.Obwohl es viele Forschungsartikel gibt, die sich auf obere und untere Schranken von schwachen F��rbungszahlen in spezifischen Graphklassen konzentrieren, gibt es bis jetzt wenig Forschung in Bezug auf Komplexit��tsergebnisse f��r die Berechnung schwacher r-F��rbungszahlen und den Entwurf von Algorithmen zur Berechnung von Ordnungen mit kleinen schwachen F��rbungszahlen. Es hat sich gezeigt, dass die Berechnung schwacher r-F��rbungszahlen f��r r ��� 3 NP-vollst��ndig ist, und daher ben��tigen wir effiziente Heuristiken, um gute obere Schranken f��r schwache r-F��rbungszahlen zu berechnen.In dieser Arbeit entwerfen wir mehrere Heuristiken zur Berechnung oberer Schranken von schwachen F��rbungszahlen, die das Turbocharging-Framework verwenden. In der allgemeinsten Fassung kann das Framework als ���Erweitern eines heuristischen Algorithmus mit einem exakten Algorithmus��� beschrieben werden, oder mit anderen Worten, ���Turbocharging der Heuristik���. Mittels einiger bekannter Heuristiken entwickeln wir mehrere exakte Algorithmen, die diese Heuristiken lokal erg��nzen und zus��tzlich beweisen wir obere und untere Komplexit��tsgrenzen dieser Algorithmen. Wir implementieren die daraus resultierenden Ans��tze und f��hren eine umfassende experimentelle Auswertung f��r reale Graphinstanzen durch.Dabei diskutieren wir Vor- und Nachteile des Turbocharging-Ansatzes, die w��hrend unserer Forschung auftraten und f��r zuk��nftige Forschungen relevant sein k��nnten., In recent years, more involved characterizations of sparse graphs were introduced, involving nowhere dense graph classes and graph classes of bounded expansion. Both fall into the category of structural sparsity and exhibit a wide variety of efficient algorithms in theory. One characterization for these graph classes can be given in terms of weak coloring numbers. They are defined in terms of vertex orderings of a graph for a given radius r ��� N.Each ordering has a weak r-coloring number, and the weak r-coloring number of a graph is the minimum weak r-coloring number over all its vertex orderings. The weak r-coloring number of a graph measures reachability properties at distance r, but also has direct algorithmic applications. Although there are many results focusing on upper and lower bounds for weak coloring numbers in specific graph classes, there is little research with regard to complexity results for computing weak r-coloring numbers and designing heuristics that compute vertex orderings with small weak r-coloring number. Computing weak r-coloring numbers is NP-complete for r ��� 3, and thus we need efficient algorithms to compute good upper bounds on weak r-coloring numbers. In this thesis, we propose several algorithms that compute orderings of small weak coloring numbers by applying the turbocharging framework. In the most general form, the framework can be described as ���augmenting a heuristic algorithm with an exact algorithm���, or in other words, ���turbocharging the heuristic���. Given some known heuristics that iteratively compute an ordering of small weak coloring numbers, we propose several exact algorithms that locally augment these heuristics, and additionally, prove upper and lower complexity bounds of these algorithms. We implement the resulting approaches and provide a thorough experimental evaluation for real-world graph instances. In the process, we discuss advantages and drawbacks of the turbocharging approach that came up during our research and might be relevant for future research.

This doctoral thesis is based on six research papers. We give upper and lower bounds on the number of subsets of the vertex set of a graph with certain properties, often we also characterize the extremal graphs. The results can be divided in four main parts. In the first part we give upper bounds on the number of maximum independent sets in connected graphs and trees in terms of the independence number and the order of a graph. We examine a similar problem for dominating sets in the second part by giving upper bounds on the number of minimum (total) dominating sets in forests. We give tight lower bounds on the number of rainbow triangles in edge colored graphs in terms of the number of colors and the number of edges of the graph in the third part of the thesis. We also characterize the extremal graphs. In the last part we give a tight upper bound on the number of Hamiltonian cycles in claw-free cubic graphs and characterize the set of graphs that fulfill this bound with equality.

In dieser Arbeit wird das Problem der Bestimmung einer maximalen kantendisjunkten Kreispackung bzw. der Bestimmung der Kreispackungszahl von Graphen untersucht. Die Bedeutung dieser theoretischen Problemstellung wird durch die Vorstellung dreier Anwendungen verdeutlicht. Da die Bestimmung solcher maximalen kantendisjunkten Kreispackungen sowie die Bestimmung der Kreispackungszahl NP-schwer sind, besteht die grundlegende Idee dieser Arbeit darin, Graphzerlegungen bestimmter Graphklassen zu nutzen und einen Bezug zwischen einer Kreispackung der Zerlegung und einer Kreispackung des Ursprungsgraphen herzustellen. F��r serienparallele Graphen wird ein Linearzeitalgorithmus basierend auf einer SPQR-Zerlegung vorgestellt und evaluiert. Weiterhin wird eine Zerlegung f��r minimal 3-zusammenh��ngende Graphen vorgestellt, mit der verschiedene Ergebnisse f��r Halin-Graphen entwickelt werden. Unter anderem wird f��r spezielle Halin-Graphen gezeigt, dass die Bestimmung der Kreispackungszahl auf die Bestimmung der Kreispackungszahlen der Komponenten in der Zerlegung zur��ckgef��hrt werden kann.

In der vorliegenden Arbeit untersuchen wir verschiedene Klassen kryptografisch bedeutsamer Funktionen wie beispielsweise bent, plateaued und differentially uni-form Funktionen sowie aus diesen Funktionen konstruierte Inzidenzstrukturen. Zunächst untersuchen wir vektorielle bent Funktionen in wenigen Variablen. Wir klassifizieren und enumerieren alle vektoriellen bent Funktionen in sechs Variablen. Damit vervollständigen wir die Klassifizierung perfekter nichtlinea-rer Funktionen in sechs Variablen vom algebraischen Grad höchstens drei und die Liste der bent Funktionen in sechs Variablen. Darüber hinaus zeigen wir, dass im Gegensatz zu Booleschen bent Funktionen nicht alle vektoriellen bent Funktionen in sechs Variablen bis auf EA-Äquivalenz durch Maiorana-McFarland und Desarguesian partial spread Konstruktionen beschrieben werden können. Wir untersuchen ferner, ob sich bestimmte Eigenschaften von Booleschen und vektoriellen bent Funktionen sowie deren Verallgemeinerungen in den zugehö-rigen Inzidenzstrukturen widerspiegeln, die in einigen Fällen zur gut erforsch-ten Klasse der kombinatorischen Designs gehören. In diesem Zusammenhang stellen wir eine neue Konstruktion von Inzidenzstrukturen aus Booleschen und vektoriellen Funktionen vor und präsentieren zwei Anwendungen dieser Objek-te zur Untersuchung von bent Funktionen. Die erste Anwendung ist eine de-signtheoretische Charakterisierung von bent Funktionen innerhalb der plateau-ed Funktionen, die zweite ist eine kombinatorische Interpretation des Erweiter-barkeitsproblems für bent Funktionen. Wir stellen ferner eine große Klasse fast perfekt-nichtlinearer Funktionen (APN-Funktionen) vor, deren lineare Codes 2-Designs tragen. Aus diesem Ergebnis entwickeln wir eine neue hinreichende Bedingung für die CCZ-Nichtäquivalenz von APN-Funktionen mit dem klassi-schen Walsh-Spektrum zu quadratischen Funktionen. Zum Abschluss untersuchen wir kubische Boolesche bent Funktionen. Wir beweisen, dass im Gegensatz zu den Fällen mit n = 6 und n = 8 Variablen die Maiorana-McFarland Konstruktion für alle n ≥ 10 nicht die gesamte Klasse der kubischen bent Funktionen in n Variablen beschreiben kann. Außerdem zeigen wir für unendlich viele n ≥ 10 die Existenz kubischer bent Funktionen in n Variablen, die homogen sind, keine affinen Ableitungen haben und nicht in der abgeschlossenen Maiorana-McFarland Klasse sind., In this thesis, we investigate various classes of cryptographically significant func-tions, including bent, plateaued and differentially uniform functions, as well as the incidence structures constructed from these mappings. First, we investigate vectorial bent functions in a small number of variables. We classify and enumerate all vectorial bent functions in six variables. Thereby, we complete the classification of perfect nonlinear functions in six variables of algebraic degree at most three and the enumeration of bent functions in six vari-ables. Moreover, we show that all vectorial bent functions in six variables, in con-trast to the Boolean bent functions, cannot be described, up to EA-equivalence, by Maiorana-McFarland and Desarguesian partial spread constructions. Furthermore, we investigate whether certain properties of Boolean and vecto-rial bent functions, as well as their generalizations, may be reflected by the asso-ciated incidence structures, which in some cases, fall into the well-studied class of combinatorial designs. In particular, we introduce a new construction of inci-dence structures from Boolean and vectorial functions called nonvanishing flats and provide two applications of this object to study bent functions. The first is a design-theoretic characterization of bent functions among plateaued functions, and the second is a combinatorial interpretation of the extendability problem for bent functions. We also provide a large class of APN functions, whose linear codes support 2-designs. Using this result, we give a new sufficient condition for APN functions with the classical Walsh spectrum to be CCZ-inequivalent to quadratic functions. Finally, we investigate cubic Boolean bent functions. We prove that, in con-trast to the cases of n = 6 and n = 8 variables, the Maiorana-McFarland con-struction does not describe the whole class of cubic bent functions in n variables for all n ≥ 10. Moreover, we show that cubic bent functions in n variables that are homogeneous, have no affine derivatives and are not in the completed Maiorana-McFarland class exist for infinitely many n ≥ 10.

Daten von sich bewegenden Objekten werden heutzutage in großem Umfang generiert, beispielsweise durch mit GPS-Trackern ausgestattete Tiere. In der vorliegenden Arbeit werden algorithmische Ansätze zur Analyse solcher Daten betrachtet, insbesondere mit dem Ziel die Bewegung von Gruppen zusammenzufassen- und miteinander vergleichen zu können. Alle entwickelten Ansätze verwenden den Fréchet Abstand – ein verbreitetes Abstandsmaß zwischen Kurven (hier: Polygonzüge, die die Bewegung eines Individuums repräsentieren) - oder erweitern dieses Maß für andere Eingaben, genauer für Graphen und Punktmengen. Zunächst wird das Group \(\it Diagram\) als Framework zur Repräsentation der Bewegung von einer oder mehreren Gruppen vorgestellt. Anschließend wird ein neuer Ansatz zur Messung der Ähnlichkeit von eingebetteten Graphen, wie sie beispielsweise beim Berechnen eines Group Diagram entstehen präsentiert. Abschließend wir das Problem betrachtet, ähnlichen lineare Formationen in zwei Punktmengen zu finden.

Virtually all of the analysis of quantum contextuality is restricted to the case where events are represented by rank-one projectors. This restriction is arbitrary and not motivated by physical considerations. We show here that loosening the rank constraint opens a new realm of quantum contextuality and we demonstrate that state-independent contextuality can even require projectors of nonunit rank. This enables the possibility of state-independent contextuality with less than 13 projectors, which is the established minimum for the case of rank one. We prove that for any rank, at least 9 projectors are required. Furthermore, in an exhaustive numerical search we find that 13 projectors are also minimal for the cases where all projectors are uniformly of rank two or uniformly of rank three., 9+9 pages, 4 figures. Published version

Zertifikate sind in der Graphentheorie hilfreich um Eigenschaften von Graphen schnell nachweisen zu können. Elmasry, Mehlhorn und Schmidt setzten sich mit 3-Zusammenhang in Hamiltongraphen auseinander und entwickelten ein Zertifikat, welches mittels eines Algorithmus in Laufzeit O(m + n) verifiziert, ob ein Hamiltongraph 3-zusammenhängend ist. Schmidt hat dies 2010 auf allgemeine Graphen mithilfe der Barnett-Grünbaum-Pfade erweitert. Somit gibt es ein Zertifikat für 3-Zusammenhang in Graphen. In dieser Arbeit beschäftigt uns die Frage: Kann man auch ein Zertifikat für 4-Zusammenhang aufstellen? Dabei stützen wir uns auf die Resultate der Arbeiten von Martinov und von Mader bezüglich 4-zusammenhängender Graphen. Ziel ist es, einen vorgegebenen Graphen G aus einem kontraktionskritischen, 4-zusammenhängenden Ausgangsgraphen mittels einer Sequenz den 4-Zusammenhang erhaltenden Kantenexpansionen zu rekonstruieren., Certificates are useful in graph theory to quickly prove properties of graphs. Elmasry, Mehlhorn and Schmidt studied 3-connection in Hamilton graphs and developed a certificate which verifies whether a Hamilton graph is 3-connected using an algorithm in runtime O(m + n). Schmidt extended this to general graphs using the Barnett-Grünbaum Pfade in 2010. Thus there is a certificate for 3-connected graphs. In this thesis we are concerned with the question: Is it possible to create a certificate for 4-connected graphs? We base this on the results of Martinov's and Mader's work on 4-connected graphs. The goal is to reconstruct a given graph G from a contraction-critical, 4-connected initial graph by using a sequence of edge expansions that preserve the 4-connection.

Property testing considers decision problems in the regime of sublinear complexity. Most classical decision problems require at least linear time complexity in order to read the whole input. Hence, decision problems are relaxed by introducing a gap between “yes” and “no” instances: A property tester for a property Π (e. g., planarity) is a randomized algorithm with constant error probability that accepts objects that have Π (planar graphs) and that rejects objects that have linear edit distance to any object from Π (graphs with a linear number of crossing edges in every planar embedding). For property testers, locality is a natural and crucial concept because they cannot obtain a global view of their input. In this thesis, we investigate property testing in graphs and how testers leverage the information contained in the neighborhoods of randomly sampled vertices: We provide some structural insights regarding properties with constant testing complexity in graphs with bounded (maximum vertex) degree and a connection between testers with constant complexity for general graphs and testers with logarithmic space complexity for random-order streams. We also present testers for some minor-freeness properties and a tester for conductance in the distributed CONGEST model.

In dieser Dissertation wird die Erd��s-P��sa Eigenschaft verschiedener Klassen von Graphen untersucht. Inbesondere wird auf die Kantenversion der Eigenschaft eingegangen und diese f��r lange Kreise und K_4-Unterteilungen nachgewiesen. Au��erdem wird eine naheliegende Verallgemeinerung dieser zwei Aussagen (Kantenversion von Robertson and Seymours Satz) als falsch nachgewiesen. Dar��ber hinaus gibt es Untersuchungen zur Erd��s-P��sa Eigenschaft von A-Wegen und gerichteten Graphen.

We aim to develop epidemiological models that describe and predict the evolution of infectious diseases. To this end, we integrate mobility data, represented by networks with static and time-varying topologies. As a central result of this work, we present three disease models that facilitate an efficient analysis of complex epidemiological problems. First, in the context of global epidemics, we present a network-based measure, termed random-walk effective distance (RWED), as a proxy for the expected infection arrival time. Here, we use the global mobility network where nodes and edges represent urban regions and air traffic connections, respectively. The RWED integrates all potential transmission paths from the outbreak location to the target node and thus improves predictions about the course of a pandemic. Next, we are developing a matrix-based algorithm that integrates time-varying topologies with generic disease models. Based on Boolean algebra, we derive a reachability matrix in order to assess the vulnerability and damage potential of individual nodes in a temporal network. Finally, we present the so-called contact-based model as a versatile approach in which temporal edges instead of nodes form central elements of a dynamic system. This change of perspective improves previous, individual-based approaches for infectious diseases with permanent immunity. In particular, we derive an analytical criterium to determine the critical disease parameters that separate local and global outbreaks. The presented models integrate elements of statistical physics, nonlinear dynamics, and linear algebra to provide quantitative insights into epidemiological problems. We compare these analytical predictions with numerical models on numerous empirical mobility networks in order to evaluate the quality and limitations of our analytical approaches., Ziel dieser Arbeit ist es, epidemiologische Modelle zur Beschreibung infektiöser Krankheiten zu entwickeln. Dabei integrieren wir Mobilitätsdaten, die mathematisch durch Netzwerke mit statischen oder zeitlich veränderlichen Topologien beschrieben werden können. Als zentrales Ergebniss dieser Arbeit präsentieren wir drei Krankheitsmodelle, die eine effiziente Analyse komplexer Probleme gestatten. Zuerst stellen wir im Kontext globaler Epidemien ein Netzwerk-basiertes Maß vor und zwar die random-walk effective distance (RWED), mit dem die erwartete Ankunftszeit einer Krankheit abgeschätzt werden kann. Dazu gehen wir vom globalen Mobilitätsnetzwerk aus, in dem Knoten und Kanten urbane Regionen abstrahieren, die durch den globalen Flugverkehr verbunden sind. Die RWED berücksichtigt, entgegen früherer Methoden, alle potentiellen Übertragungswege vom Ausbruchsort bis zum Zielknoten und ermöglicht somit präzisere Vorhersagen zum Verlauf einer Pandemie. Als nächstes entwickeln wir einen Matrix-basierten Algorithmus, der zeitlich veränderliche Topologien mit generischen Krankheitsmodellen integriert. Durch boolesche Verknüpfungen leiten wir eine Erreichbarkeitsmatrix ab, mit der die Vulnerabilität und das Schadenspotential einzelner Knoten effizient untersucht werden können. Schließlich stellen wir mit dem Kontakt-basierten Modell einen versatilen Ansatz vor, in dem temporär auftretende Kanten statt Knoten zentrale Elemente eines dynamischen Systems sind. Dieser Perspektivwechsel ermöglicht präzisere Vorhersagen bei Infektionskrankheiten mit dauerhafter Immunität. Insbesonders leiten wir ein analytisches Kriterium ab, mit dem das Risiko eines globalen Krankheitsausbruchs effizient abgeschätzt werden kann. Die vorgestellten Modelle integrieren Elemente der statistischen Physik, nicht-linearen Dynamik und der linearen Algebra, um spezifische Fragestellungen der Epidemiologie zu beleuchten. Analytische Vorhersagen vergleichen wir mit numerischen Modellen auf zahlreichen empirischen Mobilitätsnetzwerken, um die Qualität und Grenzen unserer Methoden zu evaluieren.

A matching in a graph G is a set of pairwise disjoint edges of G. The matching number of G is defined as the maximum cardinality of a matching in G. In this thesis I will present several results for subgraph-restricted versions of the matching number. For a matching M in a graph G, let G(M) be the subgraph induced by the set of vertices that are incident with an edge in M. The matching M is uniquely restricted, acyclic, or induced if M is the unique perfect matching of G(M), if G(M) is acyclic, or if G(M) is 1-regular, respectively. I provide hardness results, tractable cases, characterizations, bounds, and approximation algorithms for the above restricted matching numbers.

Für die vorliegende Dissertation wurde mittels Magnetresonanztomographie untersucht, inwiefern interindividuelle Unterschiede bei Intelligenz und Allgemeinwissen auf Unterschiede in den strukturellen und funktionellen Eigenschaften des Gehirns zurückgeführt werden können. Im Rahmen der ersten Studie konnte gezeigt werden, dass das Allgemeinwissen eines Individuums mit einem graphentheoretischen Maß der strukturellen Hirnkonnektivität assoziiert ist. In der zweiten Studie konnte mittels "Neurite Orientation Dispersion and Density Imaging" nachgewiesen werden, dass die fluide Intelligenz eines Individuums negativ mit der Dendritendichte und -verästelung im Kortex korreliert ist. Für die dritte Studie wurde die Assoziation zwischen fluider Intelligenz und funktioneller Hirnkonnektivität im Ruhezustand untersucht. Hierbei zeigte sich, dass relevante funktionelle Verbindungen in erster Linie durch Hirnregionen konstituiert werden, die Teil der "Parieto-Frontal Integration Theory" sind.

Consider the continuum of points along the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the network distance, i.e., the weighted shortest path distance. The continuous diameter of a network is the largest network distance between any two points on the network. We study two intertwined problems within this metric space: The first problem is to minimize the continuous diameter of a geometric network by introducing one or more shortcuts that may connect any two points along the network. The second problem is to develop efficient data structures that support queries for the farthest points from a query point along a network. We study the first problem for geometric cycles and trees. For geometric cycles, a single shortcut never decreases the continuous diameter and two shortcuts always suffice to reduce the continuous diameter—except when the cycle consists of two degenerate line segments. We characterize optimal pairs of shortcuts for both convex and non-convex cycles. This allows us to produce an optimal pair of shortcuts for a geometric cycle with straight-line edges that has n vertices and k reflex vertices in O(n + k2n) time. For geometric trees, we minimize the continuous diameter when adding a single shortcut. Unlike in the discrete version of this network augmentation problem, the continuous diameter may increase when we add a shortcut to a tree. We characterize for which trees a single shortcut is sufficient to reduce the continuous diameter of a tree. We develop an algorithm that produces an optimal shortcut for a geometric tree with n vertices in O(n log n) time. For the second problem, we develop a sequence of data structures supporting farthest-point queries on increasingly complex types of networks. This sequence culminates in a data structure for series-parallel networks. A series-parallel network is a network where each bi-connected component can be generated from a single edge using series operations that introduce a new vertex along an existing edge and parallel operations that create a copy of an existing edge. These results are part of a larger strategy for treelike networks where we divide a network into its bi-connected components and combine data structures for each bi-connected component that are drawn from a catalogue of data structures for networks that we can handle effciently.

The Linear Ordering problem consists in finding a total ordering of the vertices of a directed graph such that the number of backward arcs, i.e., arcs whose heads precede their tails in the ordering, is minimized. A minimum set of backward arcs corresponds to an optimal solution to the equivalent Feedback Arc Set problem and forms a minimum Cycle Cover. Linear Ordering and Feedback Arc Set are classic NP-hard optimization problems and have a wide range of applications. Whereas both problems have been studied intensively on dense graphs and tournaments, not much is known about their structure and properties on sparser graphs. There are also only few approximative algorithms that give performance guarantees especially for graphs with bounded vertex degree. This thesis fills this gap in multiple respects: We establish necessary conditions for a linear ordering (and thereby also for a feedback arc set) to be optimal, which provide new and fine-grained insights into the combinatorial structure of the problem. From these, we derive a framework for polynomial-time algorithms that construct linear orderings which adhere to one or more of these conditions. The analysis of the linear orderings produced by these algorithms is especially tailored to graphs with bounded vertex degrees of three and four and improves on previously known upper bounds. Furthermore, the set of necessary conditions is used to implement exact and fast algorithms for the Linear Ordering problem on sparse graphs. In an experimental evaluation, we finally show that the property-enforcing algorithms produce linear orderings that are very close to the optimum and that the exact representative delivers solutions in a timely manner also in practice. As an additional benefit, our results can be applied to the Acyclic Subgraph problem, which is the complementary problem to Feedback Arc Set, and provide insights into the dual problem of Feedback Arc Set, the Arc-Disjoint Cycles problem.

Netzwerke stellen einen integralen Bestandteil unseres Lebens dar. Eines der wichtigsten Kommunikations-Netzwerke ist das Internet, welches zu starken Veränderungen im Alltag geführt hat. Diese werden in Teilaspekten in der vorliegenden Dissertation untersucht. Insgesamt ist die Dissertation in drei Bereiche unterteilt, welche auf der traditionellen Perspektive der drei Dimensionen von Informationssystemen basieren. Diese Dimensionen umfassen die Technologie, das Management und die Organisation. Im Zentrum der Dissertation steht hierbei die Technologie-Dimension in dessen Rahmen die Struktur und Robustheit des Internets sowie anderer Netzwerke unter Nutzung des mathematisch-methodischen Aspekts der Graphentheorie analysiert werden. Der zweite Teilbereich der vorliegenden Arbeit wechselt die Perspektive hin zum Management. Unter Nutzung von Methoden der prädikativen Modellierung stehen das bessere Verständnis und die Möglichkeit der Vorhersage von Nutzerverhalten im E-Commerce-Kontext im Fokus. Der dritte Bereich umfasst die Organisations-Perspektive aus Sicht der Nutzer. Hierbei werden zwei spezielle Unterbereiche betrachtet. Der erste Unterbereich umfasst Webseiten Sozialer Medien und analysiert wie verschiedene Nutzergruppen diese verwenden. Der zweite Unterbereich befasst sich mit dem Einfluss der weitläufigen Verbreitung von mobilen Endgeräten auf Aspekte des persönlichen und beruflichen Lebens von Individuen. Aufbauend auf diesen drei Dimensionen wurden im Rahmen dieser Dissertation insgesamt 18 Studien durchgeführt, die sich unterschiedlicher methodischer Anwendungen bedienen um wissenschaftliche Erkenntnisse zu den vorgestellten Teilbereichen zu erlangen., Networks constitute an integral part of our lives. One of the most important communication networks is the Internet which led to large changes in everyday life, which are examined in part in this dissertation. Overall, the present dissertation is subdivided into three areas, which are based on the traditional three dimensions of information systems, comprising perspectives technology, management and organization. At the core of this dissertation is the technological perspective, centered on an analysis of the structure and robustness of the Internet network using the mathematical-methodical aspect of graph theory. The second part of the thesis deals with the management perspective. The focus lies on the understanding and prediction of user behavior in the e-commerce context utilizing methods of predictive modeling. The third area includes the organizational perspective from the point of view of users. Here, two specific sub-areas are selected. The first sub-area revolves around social media websites, with the goal of understanding how sub-groups of users utilize them in different ways. The second area is centered around the aspect of how the propagation of mobile devices influences individuals in their personal and professional environments. Based on these three perspectives, a total of 18 studies were conducted within the scope of this dissertation, using different methodological applications to gain scientific insights with respect to the areas examined.

This thesis comprises the results of five research papers on domination and zero forcing. In "Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence" (Gentner, Henning, Rautenbach, 2016) and "Smallest Domination Number and Largest Independence Number of Graphs and Forests with given Degree Sequence" (Gentner, Henning, Rautenbach, 2017) we examine best possible bounds for the domination number, based on the degree sequence of a graph. In some cases these bounds coincide with the Slater number of the sequence, which is a simple lower bound for the domination number. In "Some Comments on the Slater number" (Gentner, Rautenbach, 2017), we explore some more results involving the Slater number. Particularly, we determine graph classes for which the domination number is bounded from above by a term that is linear in the Slater number. In "Extremal values and bounds for the zero forcing number" (Gentner, Penso, Souza, Rautenbach, 2016) we prove two conjectures on the zero forcing number. One of these conjectures is a special case of another one, which we partially prove in "Some Bounds on the Zero Forcing Number of a Graph" (Gentner, Rautenbach, 2016). Additionally, we establish further bounds for the zero forcing number using different techniques. Apart from these papers, we explain the original motivation for the zero forcing problem and its connection to domination. While the origins of zero forcing lie in algebraic graph theory and physics, a lot of other applications can be found. One of these is the power domination problem, which also establishes the connection between domination and zero forcing.

In this thesis we study various problems from the prominent area of graph colourings. We provide a characterisation of t-perfect triangulations and quadrangulations of the projective plane. For the latter class, a novel method to transform quadrangulations of the sphere is developed. The involved operations are simple and minor-preserving, in contrast to other known methods. We conjecture that any graph with treewidth k and maximum degree ∆ ≥ k + √k has chromatic index ∆. In support of the conjecture we prove its fractional version by developing a new upper bound on the edge number of such graphs. We further prove the list colouring conjecture for generalised Petersen graphs of the form GP (3k,k) and GP (4k,k). In doing so, we discover an interesting connection between the number of 1-factorisations of GP (3k,k) and the Jacobsthal numbers. Finally, we develop new techniques to construct cycle decompositions. They work on the common neighbourhood of two degree-6 vertices. With these techniques we find structures that cannot occur in a minimal counterexample to Hajós’ conjecture and verify the conjecture for Eulerian graphs of pathwidth at most 6. This is the first time the conjecture has been verified for graphs that are not 4-degenerate.

Wir betrachten verschiedene Probleme im Zusammenhang mit der algorithmischen Analyse von Bewegungsdaten, insbesondere das Zusammenfassen und Vergleichen dieser Daten. Wir betrachten die Komplexität dieser Probleme und geben Algorithmen an, die sie lösen. Das 1. Problem ist die Segmentierung und Klassifizierung von Trajektorien, basierend auf parameterisierte Bewegungsmodelle. Dann stellen wir die Flowdiagramme vor, die mehrere Trajektorien zusammenfassen, aufbauend auf Kriteriumbasierte Segmentierung. Ein Flowdiagramm ist ein gerichteter azyklischer Graph, der mindestens eine Segmentierung jeder Trajektorie als Pfad enthält. Zunächst betrachten wir den diskreten Fréchet Abstand von Trajektorien, deren Knotenpunkte nicht fest gegeben sind, sondern mittels einer Wahrscheinlichkeitsverteilung. Letztens stellen wir zwei neue Ähnlichkeitsmaße für eingebettete Graphen vor, die den Fréchet Abstand benutzen. Die Maße betrachten sowohl die Struktur als auch die Einbettung der Eingabegraphen. We study several problems related to the algorithmic analysis of movement data, in particular summarising and comparing these data. For all these problems we study their computational complexity and propose algorithms to solve them. First, we study segmentation and classification of trajectories based on parameterised movement models. Second, we propose flow diagrams, a method of summarising multiple trajectories based on principles from criteria-based segmentation. A flow diagram is a directed acyclic graph in which we require the criteria sequence of at least one segmentation to appear as a path. Third, we discuss the discrete Fréchet distance for uncertain trajectories, i.e. trajectories where the locations of the observations are not fixed, but given by a probability distribution. Finally, we propose two new similarity measures for embedded graphs which use ideas from the Fréchet distance. These measures consider both the structure and the embedding of the input graphs.

Aim of this talk is the analysis of the design parameter space, i.e. the amount of used parameters and their interdependencies observed during the SolmeX Concurrent Engineering (CE) study, a Sun observation satellite mission, which was conducted by the DLR Institute of Space Systems in Bremen. In total a number of 406 parameters have been detected including 9531 interconnections. By the help of the graph theory the structure of those parameters is elaborated counting their vertices and nodes. It builds the basis for the development of a generic design analysis and optimization tool for the CE data model.

This dissertation contains four research papers. The first two papers are about exponential domination in graphs, which is a variant of domination in graphs. In the first paper, we show results about the corresponding parameters using linear programming arguments. The second paper contains a characterization of a hereditary class of graphs by forbidden induced subgraphs. In the third paper, the concept of exponential independence is introduced and several results about the corresponding parameter are shown. The last paper deals with the so-called clustering coefficient - a prominent parameter in the study of social networks. We determine the maximum clustering coefficients among all connected regular and all connected subcubic graphs of a given order.

The thesis is divided into two parts. The first part deals with t-perfect graphs. A graph is called t-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We give characterisations of P5-free graphs, quadrangulations and triangulations of the projective plane concerning t-perfection. The second part is about cycle decomposition of graphs and Hajós’ conjecture. We verify the conjecture for Eulerian graphs of pathwidth at most 6.