The seminar is usually on Thursdays at 11:00 AM
The seminar will be followed by the Thursday Lunch Expedition.
Thursday February 12, 2009
Umang Bhaskar (CS at Dartmouth)
Title: On the Uniqueness of Equilibria in Atomic Flow Games
Kemeny 120 and TIME: 11:00 AM
Abstract: In routing games with atomic players, it is known that the equilibrium
exists. The uniqueness of the equilibrium, however, has been demonstrated
only in limited cases, and the existence of multiple equilibria is an open
question. In our work, we give a complete characterization of the class of
network topologies for which unique equilibria exist. We show via two
specific examples that there may be multiple equilibria in atomic routing
games. Our results are based on a novel characterization of these
topologies in terms of circulations.
This is joint work done with Lisa Fleischer, Darrell Hoy and Chien-Chung
Huang.
Thursday February 5, 2009
Vincent Vatter (Dartmouth)
Title: Simple permutations and indecomposable graphs
Kemeny 120 and TIME: 11:00 AM
Abstract: An interval in a permutation (thought of in one-line notation, rather
than cycle notation) is a set of consecutive entries with consecutive
values, for example, 32 is an interval in 1324. Every permutation of
length n has n trivial intervals (each contains one element) and one
trivial interval containing all the elements. Permutations that have
only these trivial intervals are said to be simple. I will discuss the
enumeration and structure of simple permutations, which is joint work
with Brignall, Huczynska, and Ruskuc. I will then describe the
analogous notion for graphs, and discuss some of the problems inherent
with translating our work to this context.
Thursday January 22, 2009
Sergi Elizalde (Dartmouth)
Title: Sorting by placement and shift
Kemeny 120 and TIME: 11:00 AM
Abstract: In sorting situations where the final destination of each item is known,
it is natural to repeatedly choose items and place them where they belong,
allowing the intervening items to shift by one to make room. However, it
is not obvious that this algorithm necessarily terminates.
We show that in fact the algorithm terminates after at most $2^{n-1}-1$
steps in the worst case, and that there are super-exponentially many
permutations for which this exact bound can be achieved. The proof
involves a curious symmetrical binary representation.
This is joint work with Peter Winkler.
Thursday January 15, 2009
Elizabeth A. Gillaspy (Dartmouth)
Title: How to eat 4/9 of a Pizza
Kemeny 120 and TIME: 11:00 AM
Abstract: Suppose Alice and Bob are sharing a pizza that has been arbitrarily cut into an
odd number of slices, and suppose that they alternate eating a piece of pizza,
where they are limited at each turn to the slices of pizza that are adjacent to
a slice that has already been eaten. If Alice eats the first piece,
surprisingly, she can't guarantee that she'll eat more than 4/9 of the pizza!
However, she can always guarantee eating at least 4/9. In this talk I'll
present a paper written by Knauer, Micek, and Ueckerdt in which they prove this
result. This talk will build on one given by Peter Winkler last term in which
he introduced the Pizza Problem (though it should be comprehensible even if you
didn't attend Pete's talk).
Previous Terms:
Fall 2004.
Spring 2006.
Fall 2008
If you are interested in speaking please email Rosa.C.Orellana "at" Dartmouth "dot" edu
or Sergi Elizalde
This
page is maintained by Rosa
Orellana