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.

matrices mg.metric geometry oc.optimization and control

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

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

One Answer

Add your own answers!

Related Questions

Does the following sum converge?

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

Differential birational equivalence

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

Definition of a system of recurrent events

Regularity of a conformal map

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

Is there an algebraic version of Darboux’s theorem?

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

Are groups with the Haagerup property hyperlinear?

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

Characterization of effective descent morphism

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

Strong Data Processing Inequality for capped channels

lattice suprema vs pointwise suprema

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

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

Ability to have function sequence converging to zero at some points

Curious anti-commutative ring

Minkowski (box-counting) dimension of generalized Cantor set

Ask a Question