Friday, March 1 2019

1:00pm - 2:00pm

1:00pm - 2:00pm

Discrete Mathematics Seminar

Routing numbers of dense and expanding graphs

Abstract: Consider a connected graph G, with a pebble placed on each vertex of G. The routing number of G is the minimum number of steps needed to route any permutation on the vertices of G, where a step consists of selecting a matching on the graph and swapping the pebbles on the endpoints of each edge. Alon, Chung, and Graham introduced this parameter and, among other results, gave a bound based on the spectral gap for general graphs. The bound they obtain is polylogarithmic for graphs with sufficiently strong spectral gap. This talk will discuss a result that we gave that improves this upper bound to a constant depending on the gap and vertex degrees. This is based on joint work with Paul Horn.

Speaker: | Adam Purcilly |

Affiliation: | Denver University |

Location: | SCB 4017 |

Done