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

MathOverflow Asked on January 1, 2022

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.

One 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$

Answered by Manfred Weis on January 1, 2022

Add your own answers!

Related Questions

Definition of a system of recurrent events

1  Asked on December 20, 2021 by rob-arthan


Regularity of a conformal map

2  Asked on December 20, 2021 by amorfati


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP