|
|
REMINDER ***SFI Seminar Tuesday, March 4, 2003, 12:15-1:15pm***
Location: Medium Conference Room
Title: "Phase Transitions for Random Processes"
Speaker: Joel Spencer
Affiliation: Courant Institute
*** Abstract: ***
It has been forty years since the discovery by Paul Erdos and Alfred
Renyi that random graphs undergo a phase transition (they called it
the "double jump") when the average number of neighbors exceeds one,
in which many small components rapidly meld into a "giant component."
We now view this as a percolation transition, with classical
connections to MathematicalPhysics. In recent years a host of random
processes coming from the fecund intersection of Discrete Math,
Computer Science and Probability have shown phase transitions of this
type. One has been of particularrecent interest.
Suppose customers choose from amongst N products, selecting their
product in proportion to the square (say) of the number of previous
users of that product. This "preferential attachment" is a common
theme, both in models of the World Wide Web and as a model of
"increasing returns" in the marketplace. There is a phase transition
in which the top products are jockeying for position. Toward the end
of this transition, the leading product is still not receiving most
of the customers, but it almost certainly will achieve total
dominance over the market.
In this talk I will discuss this and other phase transitions of this
type, and the role that mathematically rigorous arguments can play in
understanding these models.
|
Locked
