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.

$\endgroup$
3
  • 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$ Feb 14, 2019 at 15:18
  • $\begingroup$ Or was the idea to lump together the three inequalities involving the same triangle? $\endgroup$ Feb 14, 2019 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, 2019 at 15:23

1 Answer 1

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.

$\endgroup$
1
  • 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, 2019 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .