##### Department of Mathematics,

University of California San Diego

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

### Math 269 - Combinatorics

## Penny Haxell

#### University of Waterloo

## Scarf's Lemma and the Stable Paths Problem

##### Abstract:

We address a question in graphs called the stable paths problem, which is an abstraction of a network routing problem concerning the Border Gateway Protocol (BGP). The main tool we use is Scarf's Lemma, an important result from game theory. This talk will describe Scarf's Lemma and how it is related to other results more familiar to combinatorialists, and then will explain its implications for the stable paths problem.

Host: Jacques Verstraete

### February 5, 2008

### 3:00 PM

### AP&M 7321

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