MATH Seminar
| Title: Distances in Permutations |
|---|
| Seminar: SIAM Student Chapter |
| Speaker: David Gunderson of University of Manitoba |
| Contact: Votjech Rodl, rodl@mathcs.emory.edu |
| Date: 2010-03-22 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Given a permutation $S$ on $\{1,2,\ldots,n\}$, define its distance set to be $\{|S(i+1)-S(i)|: i=1,\ldots,n-1\}$. For example, when $n=5$, the permutation $(S(1),\ldots,S(5))=(5,1,4,2,3)$ has distance set $\{1,2,3,4\}$, however the permutation $(1,2,3,4,5)$ has distance set $\{1\}$. On average, how large is a distance set of a random permutation? If this expected number of distances is denoted $E_n$, the ratio $E_n/(n-1)$ approaches a limit. What is it? \\ \\ The questions above were loosely motivated by random considerations regarding the graceful tree conjecture and graceful colourings of paths. |
See All Seminars