Timeline for Bounds on number of "non-metric" entries in matrices
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 21, 2021 at 1:19 | comment | added | fedja | 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... | |
| Aug 19, 2021 at 15:47 | comment | added | Manfred Weis | @fedja I can only confirm that you are right; things become clearer to me now... could you please formulate your solution as an answer so I can indicate the question as settled? | |
| Aug 19, 2021 at 15:42 | comment | added | Roland Bacher | @fedja: I think you got it right. Thanks for pointing out my error. (My answer, now hidden, gives only a bad lower bound!) | |
| Aug 19, 2021 at 14:29 | comment | added | fedja | 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. | |
| Jun 26, 2020 at 16:11 | comment | added | Manfred Weis | @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. | |
| Jun 24, 2020 at 17:24 | comment | added | Gerhard Paseman | 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. | |
| Jun 24, 2020 at 16:43 | history | edited | Manfred Weis | CC BY-SA 4.0 |
deleted 33 characters in body
|
| Jun 24, 2020 at 16:13 | history | answered | Manfred Weis | CC BY-SA 4.0 |