MATH Seminar
| Title: Increasing paths in edge-ordered hypergraphs |
|---|
| Defense: Dissertation |
| Speaker: Bradley Elliott of Emory University |
| Contact: Bradley Elliott, bradley.elliott@emory.edu |
| Date: 2020-03-27 at 3:30PM |
| Venue: https://emory.zoom.us/j/345080312 |
| Download Flyer |
| Abstract: Abstract: In this defense, we will see many variations on a classic problem of ordering the vertices or edges of a graph and determining the 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 also provide upper bounds for the edge-ordering problem with respect to complete hypergraphs and Steiner triple systems. We also prove the hypergraph version of the vertex-ordering problem: every vertex-ordered hypergraph H has an increasing path of at least $chi(H)-1$ edges, where $chi(H)$ is the chromatic number of $H$.\\ \\ For countably infinite graphs, a similar problem is studied, asking which graphs contain an infinite increasing path regardless of how their vertices or edges are ordered. Here we answer such questions for hypergraphs. For example, we show that the condition that a hypergraph contains a subhypergraph with all infinite degrees is equivalent to the condition that any vertex-ordering permits an infinite increasing path. 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 all integers $Z$ (instead of just positive integers $N$). For example, we show that for every countable graph, there is an ordering of its edges by $Z$ that forbids infinite increasing paths. |
See All Seminars