Fiber graphs [Ph.D. diss.]

A fiber graph is a graph on the integer points of a polytope whose edges come from a set of allowed moves. Fiber graphs are given implicitly which makes them a useful tool in many applications of statistics and discrete optimization whenever an exploration of vast discrete structures is needed. The first part of this thesis discusses the graph-theoretic structure of fiber graphs with a particular focus on their diameter and edge-expansion. We define the fiber dimension of a simple graph as the smallest dimension where it can be represented as a fiber graph and prove an upper bound on the fiber dimension that only depends on the chromatic number of the graph. In the second part, random walks on fiber graphs are studied and it is shown that, when a fixed set of moves is used, rapid mixing is impossible. In order to improve mixing rates for fiber walks in fixed dimension, we evaluate possible adaptions of the set of moves, one that adds a growing number of linear combinations of moves to the set of allowed moves and one that allows arbitrary lengths of single moves. We show that both methods lead to spectral expanders in fixed dimension. Finally, the parity binomial edge ideal of a graph is introduced. Unlike the binomial edge ideal, it does not have a square-free Gröbner bases and is radical if only if the graph is bipartite or the characteristic of the ground field is not two. We compute the universal Gröbner basis and the minimal primes and show that both encode combinatorics of even and odd walks.