UC San Diego

In this dissertation we study juggling card sequences and edge flipping in graphs, as well as some related problems. Juggling patterns can be described by a sequence of cards which keep track of the relative order of the balls at each step. This interpretation has many algebraic and combinatorial properties, and we place particular focus on discovering connections between this model and other studied structures and sequences. We begin with the juggling card properties of traditional juggling patterns, and their enumerative connections to Stirling numbers. We then study the case where multiple balls are thrown at once, a problem with connections to arc-labeled digraphs and boson normal ordering. Next we examine crossings in juggling cards. The first such case connects neatly to Dyck paths and Narayana numbers, while the later cases require new approaches. Lastly we examine a randomized model of juggling.

Edge flipping in graphs is a randomized coloring process on a graph. In particular: fix a graph $G$ and repeatedly choose an edge from $E(G)$ (uniformly at random, with replacement). After each selection, with probability $p$ color the vertices of the edge blue; otherwise color these vertices red. This induces a well-behaved random walk on the state space of all red/blue colorings of the complete graph and so has a stationary distribution. We derive this stationary distribution for the complete graph. We then study more classes of graphs and asymptotics of some special cases. We conclude with two related problems. First we study graph builds, which is a graph construction interpretation of edge flipping which has recently garnered interest in its own right. We then introduce hyperedge flipping in $t$-uniform hypergraphs and discuss some future work.