Hypergraphs, existential closure, and related problems

Luther, Robert D. (2024) Hypergraphs, existential closure, and related problems. Doctoral (PhD) thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (412kB)

Abstract

In this thesis, we present results from multiple projects with the theme of extending results from graphs to hypergraphs. We first discuss the existential closure property in graphs, a property that is known to hold for most graphs but in practice, examples of these graphs are hard to find. Specifically, we focus on finding necessary conditions for the existence of existentially closed line graphs and line graphs of hypergraphs. We then present constructions for generating infinite families of existentially closed line graphs. Interestingly, when restricting ourselves to existentially closed planar line graphs, we find that there are only finitely many such graphs. Next, we consider the notion of an existentially closed hypergraph, a novel concept that retains many of the necessary properties of an existentially closed graph. Again, we present constructions for generating infinitely many existentially closed hypergraphs. These constructions use combinatorial designs as the key ingredients, adding to the expansive list of applications of combinatorial designs. Finally, we extend a classical result of Mader concerning the edge-connectivity of vertextransitive graphs to linear uniform vertex-transitive hypergraphs. Additionally, we show that if either the linear or uniform properties are absent, then we can generate infinite families of vertex-transitive hypergraphs that do not satisfy the conclusion of the generalised theorem.

Actions (login required)

View Item