Increasing paths in edge-ordered hypergraphs Público

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	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Palavra-chave	monotone path hypergraph increasing path
Committee Chair / Thesis Advisor	Vojtech Rodl, Emory University
Committee Members	Dwight Duffus, Emory University Andrii Arman, Emory University Hao Huang, Emory University

Última modificação

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Increasing paths in edge-ordered hypergraphs ()	2020-04-14 14:22:33 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions