1

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.

Television
  • 560
  • 1
    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. – Jyrki Lahtonen Feb 14 '19 at 15:18
  • Or was the idea to lump together the three inequalities involving the same triangle? – Jyrki Lahtonen Feb 14 '19 at 15:19
  • @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. – Television Feb 14 '19 at 15:23

1 Answers1

1

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.

Marwan Mizuri
  • 182