Premium
Combinatorial theorems about embedding trees on the real line
Author(s) -
Chakrabarti Amit,
Khot Subhash
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20608
Subject(s) - embedding , mathematics , metric space , metric (unit) , line (geometry) , distortion (music) , mathematical proof , discrete mathematics , binary tree , combinatorics , upper and lower bounds , focus (optics) , real line , graph , computer science , geometry , artificial intelligence , amplifier , computer network , mathematical analysis , operations management , physics , bandwidth (computing) , optics , economics
We consider the combinatorial problem of embedding the metric defined by an unweighted graph into the real line, so as to minimize the distortion of the embedding. This problem is inspired by connections to Banach space theory and to computer science. After establishing a framework in which to study line embeddings, we focus on metrics defined by three specific families of trees: complete binary trees, fans, and combs. We construct asymptotically optimal (i.e., distortion‐minimizing) line embeddings for these metrics and prove their optimality via suitable lower bound arguments. It appears that even such specialized metrics require nontrivial constructions and proofs of optimality require sophisticated combinatorial arguments. The combinatorial techniques from our work might prove useful in further algorithmic research on low distortion metric embeddings. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 153–168, 2011