Title: Die Another Day
Speaker:  Rudolf Fleischer
Fudan University

Date: Tuesday, March 11, 2008
Time 3-4PM
Venue: Room 3530, HKUST


Abstract:
The Hydra was a many-headed monster from Greek mythology that would
immediately replace a head that was cut off by one or two new heads.
It was the second task of Hercules to kill this monster.
In an abstract sense, a Hydra can be modeled as a tree
where the leaves are the heads, and when a
head is cut off some subtrees get duplicated.
Different Hydra species differ by which subtress can be duplicated in
which multiplicity.
Using some deep mathematics, it had been shown that two
classes of Hydra species must always die,
independent of the order in which heads are cut off.
In this talk we identify three properties for a Hydra
that are necessary and sufficient to make it immortal or force it to die.
We also give a simple combinatorial proof for this classification.
Now, if Hercules had known this...