# How many of the triangle inequality constraints of a discrete metric space are redundant?

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.

• 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

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.
• This looks correct to me. Except the value of $k$ as $\binom{|X|}{3} - 1$ (refer to updated question). – Television Feb 14 '19 at 15:30