Increasing paths in edge-ordered hypergraphs Open Access

Elliott, Bradley (Spring 2020)

Permanent URL: https://etd.library.emory.edu/concern/etds/qn59q510p?locale=en
Published

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

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files