5
$\begingroup$

Question:
what upper bounds are known on the number of non-metric entries of finite dimensional square matrices $\boldsymbol{A}\in\mathbb{R}^{n\times 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 k\notin\lbrace i, j\rbrace\quad $ and non-metric otherwise.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In the other direction (i.e., forming a metric matrix), you may find doi.org/10.1137/060653391 interesting $\endgroup$
    – Steve Huntsman
    Commented Jun 23, 2020 at 21:20
  • 1
    $\begingroup$ @SteveHuntsman's reference: Brickell, Dhillon, Sra, and Tropp - The metric nearness problem. $\endgroup$
    – LSpice
    Commented Jul 24, 2020 at 17:45
  • $\begingroup$ I think the requirement $k\not\in\{i,j\}$ is slightly confusing: It competes with the quantifier $\forall$ in the attention of the reader. I think the question can be clarified by adding : "The requirements $k\not\in\{i,j\}$ is equivalent to the requirement that all diagonal entries are maximal (or something similar)". $\endgroup$
    – Roland Bacher
    Commented Aug 19, 2021 at 15:51

1 Answer 1

Reset to default
1
$\begingroup$

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 $\ n\cdot(2n-1)-n^2\ =\ n^2-n$ if the number of vertices is $2n$

Improve this answer
$\endgroup$
6
  • $\begingroup$ Nice. If you write up a proof sketch of optimality and include it here, that will turn this into a bona-fide answer. Gerhard "Always Willing To Upgrade Comments" Paseman, 2020.06.24. $\endgroup$
    – Gerhard Paseman
    Commented Jun 24, 2020 at 17:24
  • $\begingroup$ @GerhardPaseman I currently don't see how I can provide a proof. The reason being that things seem to be contradictory: adding edges to the densest triangle-free graph appears to allow for adding the least number of edges; on the contrary, not every edge that is added to a sparser graph will generate a triangle and thus need not increase the count of non-metric edges - I'm puzzled. $\endgroup$
    – Manfred Weis
    Commented Jun 26, 2020 at 16:11
  • 1
    $\begingroup$ If I understand your definition right, then the inequality $a_{ij}>a_{i1}+a_{1j}$ already makes $a_{ij}$ with $i,j>1$ non-metric, so in this case you can easily have only $2(n-1)$ metric elements in the whole $n\times n$ matrix: just those in the first row and the first column off the diagonal. However, judging from the discussion in this thread so far it looks like I misunderstand something, so, please, correct me if I'm wrong. $\endgroup$
    – fedja
    Commented Aug 19, 2021 at 14:29
  • $\begingroup$ @fedja: I think you got it right. Thanks for pointing out my error. (My answer, now hidden, gives only a bad lower bound!) $\endgroup$
    – Roland Bacher
    Commented Aug 19, 2021 at 15:42
  • 1
    $\begingroup$ It is almost settled. It is clear now that the minimal number of metric elements is $\ge n$ (every row/column contains at least one) and $\le 2(n-1)$ (my example), but there is still a 2-fold discrepancy between these bounds... $\endgroup$
    – fedja
    Commented Aug 21, 2021 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .