1
$\begingroup$

Consider a discrete set of points $X$ and a distance function $d : X \times X \to \mathbb{R}_+$. $d(\cdot,\cdot)$ is said to be a metric over $X$ if the following three constraints are satisfied:

  1. $\forall x,y \in X,\ d(x,y) = 0 \Leftrightarrow x = y$.
  2. $\forall x,y \in X,\ d (x,y) = d (y,x)$ [symmetry].
  3. $\forall x,y,z \in X,\ d(x,y) + d(y,z) \ge d (x,z)$ [triangle inequality].

A $k$-metric space is $X$ equipped with a distance function that always satisfies the first two constraints, and $k$ of the $\binom{|X|}{2} (|\mathcal{X}| - 2)$ non-trivial$^*$ triangle inequality constraints.

What is the maximum $k$ such that there exists a $k$-metric space that is not a metric space?


$*$ A set of triangle inequalities is non-trivial if each is composed of distinct $x,y,z$ and inequalities remain distinct upon all possible symmetry transformations.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ Where does $\binom {|X|}3$ come from? The roles of $x$ and $z$ can be swapped (by the symmetry axiom), but $y$ is in a different role. I would think that there are essentially $(|X|-2)\binom{|X|}2$ non-trivial triangle inequalities. $\endgroup$ – Jyrki Lahtonen Feb 14 '19 at 15:18
  • $\begingroup$ Or was the idea to lump together the three inequalities involving the same triangle? $\endgroup$ – Jyrki Lahtonen Feb 14 '19 at 15:19
  • $\begingroup$ @JyrkiLahtonen You are right. My intention was to look at all triangle inequalities composed of different points, that remain distinct from each other upon all possible symmetry transformations. $\endgroup$ – Television Feb 14 '19 at 15:23
1
$\begingroup$

From what I understand, if we let $\text{d}(x,y)=1$ when $x\neq y$, except for the distance between $a$ to $b$ and $a$ to $c$ for some fixed $a,b, \text{ and } c \in X$; where we have $\text{d}(a,b)=0.1$ and $\text{d}(a,c)=0.1$, we will have $X$ as a $[\binom{|X|}{2}(|X|-2)-1]$-metric space.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ This looks correct to me. Except the value of $k$ as $\binom{|X|}{3} - 1$ (refer to updated question). $\endgroup$ – Television Feb 14 '19 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.