1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.