Spaces with a quasi triangle inequality - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:49:19Z http://mathoverflow.net/feeds/question/56118 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56118/spaces-with-a-quasi-triangle-inequality Spaces with a quasi triangle inequality John H 2011-02-20T23:17:56Z 2011-02-21T09:17:31Z <p>How do you call a space with a function which is symmetric, non negative, positive definite and which satisfies a quasi-triangle inequality:</p> <p>$d(x,z) \leq C( d(x,y)+d(y,z) )$</p> <p>for all $x,y,z$ and some $C > 1$?</p> <p>That is, it satisfies all the axioms of a metric space except for the triangle inequality, which is replaced by the one above.</p> <p>Can anyone provide any reference on these spaces?</p> <p>Thanks.</p> http://mathoverflow.net/questions/56118/spaces-with-a-quasi-triangle-inequality/56119#56119 Answer by ex falso quodlibet for Spaces with a quasi triangle inequality ex falso quodlibet 2011-02-20T23:50:12Z 2011-02-21T02:04:41Z <p>Your construction is a special case of semimetric spaces with relaxed triangle inequality: <a href="http://en.wikipedia.org/wiki/Semimetric_space#Semimetrics" rel="nofollow">http://en.wikipedia.org/wiki/Semimetric_space#Semimetrics</a>. This type of metric is sometimes also called non-Archimedian metric. There is a classical paper of W.A.Wilson "On semi-metric spaces", Amer. J. Math. 53 (1931) 361–373, on the subject. Also, I have seen this type of construction mostly used in fixed-point theory, so this would be an additional keyword to look for.</p> <p><strong>EDIT:</strong> To answer your second question about whether Banach fixed-point theorem would be applicable to semimetric spaces: In general one needs $(X,d)$ to be bounded, otherwise there are counter-examples. Consider $X=\mathbb{N}$, $d(n,m):=\frac{|n-m|}{2^{\min(n,m)}}$ and $f(n):=n+1$. Then $(X,d)$ is $d$-Cauchy complete semimetric space (!), but $f$ has no fixed points, even though it is a contraction w.r.t. $d$ with contraction constant $1/2$. This example is taken from the paper "Nonlinear Contractions on Semimetric Spaces" by J. Jachymski, J. Matkowski, T. Swiatkowski, Journal of Applied Analysis Vol. 1, No. 2 (1995), pp. 125–134, where you can also find the proof of the Banach Fixed-Point Theorem for bounded semimetric spaces and some more related results.</p> http://mathoverflow.net/questions/56118/spaces-with-a-quasi-triangle-inequality/56120#56120 Answer by Mark Sapir for Spaces with a quasi triangle inequality Mark Sapir 2011-02-20T23:58:07Z 2011-02-20T23:58:07Z <p>This is called "C-relaxed triangular inequality". See, for example, <a href="http://portal.acm.org/citation.cfm?id=305984" rel="nofollow">this </a> paper by Fagin and Stockmeyer. </p> http://mathoverflow.net/questions/56118/spaces-with-a-quasi-triangle-inequality/56155#56155 Answer by Gideon Schechtman for Spaces with a quasi triangle inequality Gideon Schechtman 2011-02-21T09:12:06Z 2011-02-21T09:17:31Z <p>Here is a negative answer for your additional remark concerning Banach's fixed point theorem: Consider $d(x,y)=(\int_0^1|x-y|^p)^{1/p},$ <code>$0&lt;p&lt;1$</code> which satisfies the quasi-triangle inequality. Look at the set of all (measurable real) functions on $[0,1]$ boundaed between 0 and 2 and of integral 1. Look at the Baker transformation on this set: first map $x$ to $y(t)=2x(2t)$, $0\le t\le 1/2$ then trancate at hight 2 and shift what remains ($(y-1)^{+}$) by $1/2$ to the right and $2$ down. I think I checked that it is a contraction (with constant $2^{p-1}$). This map is known not to have a fixed point, see the following paper of Dale Alspach: <a href="http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf" rel="nofollow">http://www.claremontmckenna.edu/math/moneill/Math%20138/papers138/Alspach.pdf</a></p>