咨询：一类特殊随机图的直径期望长度是多少？

First, let's break down what this graph really is:

• Start with an undirected random graph (G=(n,p)), where each pair of vertices has an edge with probability (p), independently.
• Assign each vertex a unique random real ID (equivalent to a random permutation of vertices).
• Orient every edge from the vertex with the smaller ID to the larger one. This results in a directed acyclic graph (DAG) where all edges flow "forward" in the random ID order.

The diameter of this directed graph refers to the maximum shortest path length between any pair of vertices where a path exists (since cycles are impossible, strong connectivity isn't a consideration here). The expected diameter depends heavily on the edge probability (p):

1. When (p) is a constant (e.g., (p=0.5)) #

For large (n), here's what happens:

• For any pair of vertices (u) (lower ID) and (v) (higher ID):
  • If there's a direct edge, the shortest path length is 1.
  • If there's no direct edge, the chance that none of the intermediate vertices (between (u) and (v) in the ID order) connect both (u) and (v) is exponentially small (roughly (e^{-p2(n-2)})). This means almost all such pairs have a path of length 2.
• Expected Diameter: Tends to a value ≤ 2 as (n) grows. With high probability, the diameter is exactly 2 (since there will always be some pairs without a direct edge, but nearly all have a 2-step path).

2. When (p = \frac{c}{n}) (connectivity threshold, (c>1)) #

This is the regime where the original undirected graph becomes connected with high probability:

• Each vertex has an average of (c) neighbors. Since edges only flow forward in the ID order, reaching a faraway vertex requires building a path where each step jumps to a new set of vertices.
• Each step in the path roughly multiplies the number of reachable vertices by (c). To traverse from one end of the random ID order to the other, you need about (\log_c n) steps.
• Expected Diameter: Θ((\log n))—grows logarithmically with (n).

3. When (p \leq \frac{1}{n}) (below connectivity threshold) #

The original undirected graph is disconnected with high probability. Many pairs of vertices have no directed path between them (so diameter is often considered undefined for these pairs). For pairs that do have a path, the expected diameter is much larger, but this regime is less practical since the graph is fragmented.

Key Side Note on Root Vertices #

A root vertex (all edges are outgoing) is any vertex whose ID is smaller than all its neighbors. The vertex with the smallest overall ID is always a root; other roots exist only if a vertex is isolated or all its neighbors have higher IDs.

内容的提问来源于stack exchange，提问作者Hasan Heydari