Asymptotic negative type properties of finite ultrametric spaces

详细信息    查看全文

• 作者：Ian Doust^a ; ^{i.doust@unsw.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Stephen Sá ; nchez^a ; ^{stephen.sanchez@unsw.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Anthony Weston^b ; ^c ; ^{westona@canisius.edu" class="auth_mail" title="E-mail the corresponding author} ; ^{westoar@unisa.ac.za" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Ultrametric space ; (Enhanced) negative type ; Proximity dendrogram
• 刊名：Journal of Mathematical Analysis and Applications
• 出版年：2017
• 出版时间：15 February 2017
• 年：2017
• 卷：446
• 期：2
• 页码：1776-1793
• 全文大小：538 K

文摘

Negative type inequalities arise in the study of embedding properties of metric spaces, but they often reduce to intractable combinatorial problems. In this paper we study more quantitative versions of these inequalities involving the so-called p  -negative type gap. In particular, we focus our attention on the class of finite ultrametric spaces which are important in areas such as phylogenetics and data mining. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si1.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=2c619669fd7d5cb26a068936bb1f487c" title="Click to view the MathML source">(X,d)class="mathContainer hidden">class="mathCode">$(X,d)$ be a given finite ultrametric space with minimum non-zero distance α. Then the p  -negative type gap class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si2.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=a89a72507b75dac00e2e758d997e59ea" title="Click to view the MathML source">Γ_X(p)class="mathContainer hidden">class="mathCode">${\mathrm{\Gamma }}_X(p)$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si1.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=2c619669fd7d5cb26a068936bb1f487c" title="Click to view the MathML source">(X,d)class="mathContainer hidden">class="mathCode">$(X,d)$ is positive for all class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si3.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=f930879dd72285404df7e00e42badcc0" title="Click to view the MathML source">p≥0class="mathContainer hidden">class="mathCode">$p\ge 0$. In this paper we compute the value of the limit It turns out that this value is positive and it may be given explicitly by an elegant combinatorial formula. This formula allows us to characterize when the ratio class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si5.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=e4808912dc368c5cfb5c361ec1205a75" title="Click to view the MathML source">Γ_X(p)/α^pclass="mathContainer hidden">class="mathCode">${\mathrm{\Gamma }}_X(p)/{\alpha }^p$ is a constant independent of p  . The determination of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si321.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=0e9ef2006b2509bac73a4ca6738f064e" title="Click to view the MathML source">Γ_X(∞)class="mathContainer hidden">class="mathCode">${\mathrm{\Gamma }}_X(\infty )$ also leads to new, asymptotically sharp, families of enhanced p  -negative type inequalities for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si1.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=2c619669fd7d5cb26a068936bb1f487c" title="Click to view the MathML source">(X,d)class="mathContainer hidden">class="mathCode">$(X,d)$. Indeed, suppose that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si66.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=35b8bc05e92e30d66e0be2cbe3d617fc" title="Click to view the MathML source">G∈(0,Γ_X(∞))class="mathContainer hidden">class="mathCode">$G\in (0,{\mathrm{\Gamma }}_X(\infty ))$. Then, for all sufficiently large p, the inequality holds for each finite subset class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si68.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=324e2c53a3652686fa30fcc6056a8f21" title="Click to view the MathML source">{z₁,…,z_n}⊆Xclass="mathContainer hidden">class="mathCode">$\{z_1,\dots ,z_n\}\subseteq X$, and each scalar n  -tuple class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si10.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=7f1eb2b2fdb15313d6129848871ba4b5" title="Click to view the MathML source">ζ=(ζ₁,…,ζ_n)∈Rⁿclass="mathContainer hidden">class="mathCode">$\mathit{\zeta }=({\zeta }_1,\dots ,{\zeta }_n)\in {\mathbb{R}}^n$ that satisfies class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022247X16305856&_mathId=si11.gif&_user=111111111&_pii=S0022247X16305856&_rdoc=1&_issn=0022247X&md5=1c195f8e4e472e777093e796833384d2" title="Click to view the MathML source">ζ₁+⋯+ζ_n=0class="mathContainer hidden">class="mathCode">${\zeta }_1+\cdots +{\zeta }_n=0$. Notably, these results do not extend to general finite metric spaces.