Constant Distortion Embeddings of Symmetric Diversities

• Autorzy: David Bryant , Paul F. Tupper
• Języki publikacji: EN

Abstrakty

EN

Diversities are like metric spaces, except that every finite subset, instead of just every pair of points, is assigned a value. Just as there is a theory of minimal distortion embeddings of fiite metric spaces into L1, there is a similar, yet undeveloped, theory for embedding finite diversities into the diversity analogue of L1 spaces. In the metric case, it iswell known that an n-point metric space can be embedded into L1 withO(log n) distortion. For diversities, the optimal distortion is unknown. Here, we establish the surprising result that symmetric diversities, those in which the diversity (value) assigned to a set depends only on its cardinality, can be embedded in L1 with constant distortion.

Słowa kluczowe

EN

diversities; metric embedding; L1 embedding; hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Analysis and Geometry in Metric Spaces
• Rocznik: 2016
• Tom: 4
• Numer: 1

Daty

otrzymano

2016-05-11

zaakceptowano

2016-11-08

online

2016-12-05

Twórcy

autor

David Bryant

• Dept. of Mathematics, Simon Fraser University. 8888 University Drive, Burnaby, British Columbia V5A 1S6, Canada,

autor

Paul F. Tupper

• Dept. of Mathematics and Statistics, University of Otago, Dunedin 9054, New Zealand

Identyfikatory

DOI

10.1515/agms-2016-0016