Georgia Institute of Technology College of Sciences

We consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path. Joint work with Colin Cooper and Wesley Pegden.

The Birman-Hilden theorem relates the mapping class groups of two orientable surfaces S and X, given a regular branched covering map p from S to X. Explicitly, it provides an isomorphism between the group of mapping classes of S that have p-equivariant representatives (mod the deck group of the covering map), and the group of mapping classes of X that have representatives that lift to homeomorphisms of S. We will translate these notions into the realm of automorphisms of free group, and prove that an obvious analogue of the Birman-Hilden theorem holds there. To indicate the proof of this, we shall explore in detail several key examples, and we shall describe some group-theoretic applications of the theorem. This is joint work with Rebecca Winarski, John Calabrese, and Tyrone Ghaswala

In the Rendezvous problem on the complete graph, two parties are trying to meet at some vertex at the same time, despite starting out with independent random labelings of the vertices. It is well known that the optimal strategy is for one player to wait at any vertex, while the other visits all n vertices in consecutive steps, which guarantees a rendezvous within n steps and takes (n + 1)/2 steps on average. This strategy is very far from being symmetric, however. E. Anderson and R. Weber presented a symmetric algorithm that achieves an expected meeting time of 0.829n, which has been conjectured to be optimal in the symmetric setting. We change perspective slightly: instead of trying to minimize the expected meeting time, we try to maximize the probability of successfully meeting within a specified number of timesteps. In this setting, for all time horizons that are linear in n, the Anderson-Weber strategy has a constant probability of failure. Surprisingly, we show that this is not optimal: there exists a different symmetric strategy that almost surely guarantees meeting within 4n timesteps. This bound is tight, in that the factor 4 cannot be replaced by any smaller constant. Our strategy depends on the construction of a new kind of combinatorial object that we dub”rendezvous code.”On the positive side, for T < n, we show that the probability of meeting within T steps is indeed (approximately) maximized by the Anderson-Weber strategy. Our results imply new lower bounds on the expected meeting time for any symmetric strategy, which establishes an asymptotic difference between the best symmetric and asymmetric strategies. Finally, we examine the symmetric rendezvous problem on other vertex-transitive graphs.