Talk:Tight span

Latest comment: 7 years ago by Yahya Abdal-Aziz in topic Tropical approach

Who Discovered It?

edit

John Isbell, in 1964. Vegasprof 09:58, 8 November 2006 (UTC)Reply

Notation

edit

I believe that in the T-theory literature, the tight span of   is normally called   or  . Vegasprof 20:27, 8 November 2006 (UTC)Reply

Finite?

edit

The tight span is defined for all metric spaces, not just finite metric spaces, although the applications that I have seen all seem to be for finite metric spaces. Vegasprof 19:05, 9 November 2006 (UTC)Reply

Right, that's why I moved the part about finiteness into the formal definitions section, and left the introductory sections talking about metric spaces more generally. I am not certain whether the definition here is correct for infinite spaces, whether perhaps the condition on existence of y s.t. f(x)+f(y)=d(x,y) should be replaced by inf f(x)+f(y)-d(x,y)=0, or whether something else is required in the infinite case, so I thought it best to stick to material I was more certain I understood. —David Eppstein 19:33, 9 November 2006 (UTC)Reply
Later: I found the right definition in Dress et al (it is the inf version) and added it as a footnote. —David Eppstein 22:43, 9 November 2006 (UTC)Reply
I see. For example, the tight span of the rationals is the reals, and you really need to say "inf." Vegasprof 10:04, 10 November 2006 (UTC)Reply

Manhattan Plane

edit

R2 is injective with the L1 metric but R3 is not. Vegasprof 10:04, 10 November 2006 (UTC)Reply

Yes, that's one of the reasons the connection to orthogonal hull is hard to generalize to higher dimensions. I suppose I should say more about how two-dimensional L1 and Linf are related somewhere in that example. —David Eppstein 16:07, 10 November 2006 (UTC)Reply

Applications to Online Algorithms

edit

Besides the k-server problem, what other published applications to online algorithms do you know of? I didn't find any when I was looking. Vegasprof 10:04, 10 November 2006 (UTC)Reply

I don't know of any, but I think that line is left over from Oravec's earlier version, so you could try asking him...—David Eppstein 16:07, 10 November 2006 (UTC)Reply
You're right. Vegasprof 21:50, 11 November 2006 (UTC)Reply
I fixed the ambiguity of the statement. Oravec 22:09, 11 November 2006 (UTC)Reply


Great Contribution

edit

Wow, you guys developed this article nicely in a short period of time. Congrats. Tparameter 20:10, 10 November 2006 (UTC)Reply

Thanks mostly to David. Vegasprof 21:50, 11 November 2006 (UTC)Reply

References

edit

Isn't

  • Holsztyński, Włodzimierz (1968). "Linearisation od isometric embeddings of Banach Spaces. Metric Envelopes.". Bull. Acad. Polon. Sci. 16: 189-193.

supposed to be

I imagine so. Done. —David Eppstein (talk) 05:26, 2 March 2008 (UTC)Reply

Tropical approach

edit

In the article it says

Develin & Sturmfels (2004) provide an alternative definition of the tight span of a finite metric space, as the tropical convex hull of the vectors of distances from each point to each other point in the space.

but the Erratum to their paper seems to retract the theorem that the tropical convex hull is the tight span. SimonWillerton (talk) 22:58, 30 November 2012 (UTC)Reply

Indeed it does! It says specifically that:

If D is a symmetric matrix which represents a finite metric, then the tropical polytope PD always contains Isbell’s injective hull of the metric, but in general these two polyhedral spaces are not equal.

That is, the tropical convex hull always contains the tight span, but may be larger. I've amended the article to show this mis-step and its correction, citing the Erratum article. Rather than expunging the error, it's reasonable to show that doing mathematics (or any other science) is an ongoing process, subject to correction when we err. yoyo (talk) 13:13, 30 March 2017 (UTC)Reply