Abstract:
The study of trees as mathematical objects was initiated
in 1857 by Cayley who enumerated the isomers of the saturated
hydrocarbons CnH2n+2. For example, an
application of Cayley's formula shows that the number of isomers
of the paraffin C13H28 is 802. More recently,
the non linear geometry of finite metric trees has been under
intense scrutiny due to applications in seemingly diverse areas
such as evolutionary biology, linguistics and theoretical computer
science.
On the other hand, negative type inequalities and
metrics were isolated in the early 1900s by several mathematicians
including Moore, Menger and Schoenberg. The focus at the time was
on distance preserving embeddings and this indeed remains important
and central. However, negative type metrics also arise naturally
in theoretical computer science---for example, in relation to
semidefinite relaxations for Sparsest Cut and other graph
partitioning problems. A particular highlight in this direction
has been the disproof (by counterexample) of the Goemans-Linial
Conjecture in 2005 by Khot and Vishnoi.
In this talk I will illustrate some properties of
negative type inequalities---in the context of finite metric
trees---that lead to a new concept in non linear functional analysis:
Enhanced Negative Type. The talk will be self-contained and
presented from the ground up with virtually no mathematical
prerequisites in mind beyond a basic appreciation of numbers.