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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- 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?

Recent Answers

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

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