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

1 Asked on December 21, 2021 by ryan-chen

ca classical analysis and odes limits and convergence sequences and series

0 Asked on December 21, 2021 by fredy

0 Asked on December 20, 2021

ag algebraic geometry differential operators noncommutative algebra ra rings and algebras

1 Asked on December 20, 2021 by luka-klini

1 Asked on December 20, 2021 by rob-arthan

2 Asked on December 20, 2021 by amorfati

1 Asked on December 20, 2021

1 Asked on December 20, 2021

1 Asked on December 20, 2021

1 Asked on December 18, 2021 by maowao

free groups geometric group theory oa operator algebras von neumann algebras

0 Asked on December 18, 2021

0 Asked on December 18, 2021 by kind-bubble

ag algebraic geometry ct category theory descent galois descent

2 Asked on December 18, 2021

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

coding theory it information theory markov chains pr probability stochastic processes

2 Asked on December 18, 2021 by giuliosky

banach lattices fa functional analysis lattice theory lattices

2 Asked on December 18, 2021

banach spaces fa functional analysis limits and convergence metric spaces norms

0 Asked on December 18, 2021

1 Asked on December 16, 2021 by mathcounterexamples-net

1 Asked on December 16, 2021 by robert-bruner

ac commutative algebra noncommutative rings ra rings and algebras reference request

0 Asked on December 16, 2021

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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