Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Steve Butler

UCLA

Jumping Sequences

Abstract:

\indent Given the cost $w(i,j)$ of jumping from integer $j$ down to integer $i$ one can ask what is the minimal total sum cost of jumping from $n$ to $1$, and what can be said about the jumping pattern that achieves this minimal cost? The optimal jumping patterns can be encoded into a sequence $a(1),a(2),a(3),\ldots$ so that for any $n$ the optimal thing is to jump from $n$ to $a(n)$ to $a(a(n))$ and so on until $a(a(\cdots(a(n))\cdots))=1$, this sequence is called the jumping sequence for the given weight function. These sequences arise from a problem of secure network broadcasting. In this talk we will give some basic results about some sequences associated with various weights, including showing that for the weight function $w(i,j)=(i+j)/i^2$ that the only values which appear arbitrarily deep in jumping patterns are the Pell numbers. (Joint work with Ron Graham and Nan Zang)

Host: Jeff Remmel

October 14, 2008

4:00 PM

AP&M 7321

****************************