Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum of all edge labels on that path (or $0$ for a trivial path), and define the "distance" $d(a, b)$ from node $a$ to $b$ to be the minimum weight of all paths from $a$ to $b$ (or $\infty$ if $b$ is not reachable from $a$).

Define a triple $a, b, c$ of nodes to be defective if $d(a, c) < d(a, b) < \infty$ and $d(b, c) < d(a, b)$.

I have two questions:

A) What is the maximum number of defective triples possible?

B) What is the average number of defective triples if edge labels are assigned at random?

Unfortunately, I haven't been able to make much progress on either one, so I was hoping other people might have insight into the problem.


For A), here is a construction that gives $2\binom{n}{3}$ defective triples, which is almost best possible. Let $D$ be a digraph with vertex set $[n]$ and arcs $(i,i+1)$ and $(i+1, i)$ for all $i \in [n-1]$. Let the label of the arc $(i,i+1)$ be $n-1+i$, and the label of the arc $(i+1, i)$ be $i$.

For all $i<j<k$, I claim that $(i,k,j)$ is a defective triple. To see this, note that $d(i,j)=n+j-2 < n+k-2=d(i,k)$ and $d(k,j)=k-1 < n+k-2=d(i,k)$.
Similarly, $(j,k,i)$ is also a defective triple.

Thus, this example contains $2\binom{n}{3}$ defective triples.

In general, note that if $(a,b,c)$ is a defective triple, then $(a,c,b)$ cannot be a defective triple. Thus, every digraph on $n$ vertices contains at most $3 \binom{n}{3}$ defective triples, so our bound is tight up to a factor of $\frac{3}{2}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.