Bounds on number of "non-metric" entries in matrices

Question

Question:
what upper bounds are known on the number of non-metric entries of finite dimensional square matrices $boldsymbol{A}inmathbb{R}^{ntimes n}$ with strictly positive off-diagonal elements $a_{ij}$?
In this context $a_{ij}$ is defined to metric iff $quad a_{ij}leqq a_{ik}+a_{kj},forall knotinlbrace i, jrbracequad $ and non-metric otherwise.

Manfred Weis · Answer

I had posted the problem because I couldn't see how to solve it for some time but for some strange reason I found a simple answer not long after I put it on MO, so it is rather to be seen as a comment:
The basic idea for constructing an extremal example is to take a densest triangle-free graph and set its edgeweights to $1$ and augment it to a complete graph by adding edges of weight $3$.
Densest triangle-free graphs are $K_{n,n}$ with $n^2$ edges, implying that the number of non-metric edges that augment it to $k_{2n}$ is $ ncdot(2n-1)-n^2 = n^2-n$ if the number of vertices is $2n$

Bounds on number of "non-metric" entries in matrices

One Answer

Add your own answers!

Ask a Question