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

MathOverflow Asked on January 1, 2022

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.

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

## Related Questions

### Does the following sum converge?

1  Asked on December 21, 2021 by ryan-chen

### Is a homotopy sphere with maximum Morse perfection actually diffeomorphic to a standard sphere?

0  Asked on December 21, 2021 by fredy

### Differential birational equivalence

0  Asked on December 20, 2021

### Calculating $n$-dimensional hypervolumes ($n sim 50$), for example

1  Asked on December 20, 2021 by luka-klini

### 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

### Is there a standard definition of weak form of a nonlinear PDE?

1  Asked on December 20, 2021

### Is there an algebraic version of Darboux’s theorem?

1  Asked on December 20, 2021

### The strength of “There are no $Pi^1_1$-pseudofinite sets”

1  Asked on December 20, 2021

### Are groups with the Haagerup property hyperlinear?

1  Asked on December 18, 2021 by maowao

### Proof of second incompleteness theorem for Set theory without Arithmetization of Syntax

0  Asked on December 18, 2021

### Characterization of effective descent morphism

0  Asked on December 18, 2021 by kind-bubble

### Analogue of decay of Fourier coefficients of a smooth function on $mathbb{S}^1$

2  Asked on December 18, 2021

### Strong Data Processing Inequality for capped channels

1  Asked on December 18, 2021 by thomas-dybdahl-ahle

### lattice suprema vs pointwise suprema

2  Asked on December 18, 2021 by giuliosky

### In infinite dimensions, is it possible that convergence of distances to a sequence always implies convergence of that sequence?

2  Asked on December 18, 2021

### Are those distributional solutions that are functions, the same as weak solutions?

0  Asked on December 18, 2021

### Ability to have function sequence converging to zero at some points

1  Asked on December 16, 2021 by mathcounterexamples-net

### Curious anti-commutative ring

1  Asked on December 16, 2021 by robert-bruner

### Minkowski (box-counting) dimension of generalized Cantor set

0  Asked on December 16, 2021