Increasing paths in edge-ordered hypergraphs Open Access
Elliott, Bradley (Spring 2020)
Abstract
In this thesis, we study many variations on a classic problem of ordering the vertices or edges of a graph and determining the maximal possible length of “increasing” paths in the graph. For finite graphs, the vertex-ordering problem is completely solved, and there has been recent progress on the edge-ordering problem. Here, we prove the hypergraph version of the vertex-ordering problem: every vertex-ordered hypergraph H has an increasing path of at least χ(H)−1 edges. We also provide upper bounds for the edge-ordering problem with respect to complete hypergraphs and Steiner triple systems.
For countably infinite graphs, a similar problem is studied. A result of M¨uller, Reiterman, and R¨odl [12, 14] states that a countable graph has a subgraph with all infinite degrees if and only if any ordering of the vertices (or edges) of this graph permits an infinite increasing path. Here we study corresponding questions for hypergraphs and directed graphs. For example we show that the condition that any vertex-ordering of a simple hypergraph permits an infinite increasing path is equivalent to the condition that the hypergraph contains a subhypergraph with all infinite degrees. We prove a similar result for edge-orderings. In addition we find an equivalent condition for a graph to have the property that any vertex-ordering permits a path of arbitrary finite length. Finally we study related problems for orderings by Z (instead of N). For example, we show that for every countable graph, there is an ordering of its edges by Z that forbids infinite increasing paths.
Table of Contents
1 Introduction 1
1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Finite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Countable graphs . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Finite hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Countable graphs, hypergraphs, and digraphs . . . . . . . . . 8
2 Finite Hypergraphs 16
2.1 Tight Paths in Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Loose Paths in Steiner Triple Systems . . . . . . . . . . . . . . . . . . 21
2.3 Vertex-orderings in Hypergraphs . . . . . . . . . . . . . . . . . . . . . 26
3 Countable Graphs, Hypergraphs, and Digraphs 29
3.1 Countable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Countable Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Vertex-ordering . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Edge-ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Countable Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Arbitrary Finite Paths in Countable Graphs . . . . . . . . . . . . . . 50
3.4.1 Paths of Arbitrary Finite Length . . . . . . . . . . . . . . . . 50
3.4.2 A Counterexample . . . . . . . . . . . . . . . . . . . . . . . . 52
A Alternative Proof of Theorem 2.1.1 . . . . . . . . . . . . . . . . . . . 56
Bibliography 62
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Increasing paths in edge-ordered hypergraphs () | 2020-04-14 14:22:33 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|