KIT | KIT-Bibliothek | Impressum | Datenschutz

On the structure of graphs with forbidden induced substructures

Weber, Lea

Abstract:

One of the central goals in extremal combinatorics is to understand how the global structure of a combinatorial object, e.g. a graph, hypergraph or set system, is affected by local constraints.
In this thesis we are concerned with structural properties of graphs and hypergraphs which locally do not look like some type of forbidden induced pattern. Patterns can be single subgraphs, families of subgraphs, or in the multicolour version colourings or families of colourings of subgraphs.

Erdős and Szekeres's quantitative version of Ramsey's theorem asserts that in every $2$-edge-colouring of the complete graph on $n$ vertices there is a monochromatic clique on at least $\frac{1}{2}\log n$ vertices. The famous Erdős-Hajnal conjecture asserts that forbidding fixed colourings on subgraphs ensures much larger monochromatic cliques. The conjecture is open in general, though a few partial results are known. The first part of this thesis will be concerned with different variants of this conjecture: A bipartite variant, a multicolour variant, and an order-size variant for hypergraphs.

In the second part of this thesis we focus more on order-size pairs; an order-size pair $(n,e)$ is the family consisting of all graphs of order $n$ and size $e$, i.e. ... mehr


Volltext §
DOI: 10.5445/IR/1000161448
Veröffentlicht am 21.08.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG)
Publikationstyp Hochschulschrift
Publikationsdatum 21.08.2023
Sprache Englisch
Identifikator KITopen-ID: 1000161448
Verlag Karlsruher Institut für Technologie (KIT)
Umfang x, 180 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Mathematik (MATH)
Institut Institut für Algebra und Geometrie (IAG)
Prüfungsdatum 12.07.2023
Referent/Betreuer Axenovich, Maria
Ueckerdt, Torsten
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page