Friday, March 1 2019
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

Download as iCalendar