有限DAGの進行的埋め込み定理

有限有向グラフGに関して、次は同値である。

1. Gにサイクルがない。
2. G上の傾向関数（trend function）が存在する。
3. Gのユークリッド空間Rⁿ⁺¹への進行的埋め込み（progressive embedding）が存在する。

傾向関数の定義は、Gの2頂点a, bがこの順序で有向隣接するとき a◁b と書くことにして、

• h:Vertex(G)→R が傾向関数だとは、a◁b ならば h(a)＜h(b) のこと。

Gを幾何複体として幾何的埋め込みを考えて、g:G→Rⁿ⁺¹が進行的埋め込みだとは、最後の座標関数が傾向関数になっていること。

傾向関数を作るには、有限DAGの次の性質を利用する。

• a, bを頂点として、Path(a, b)を有向パスの集合とすると、任意の2頂点に対するPath(a, b)は有限集合（空集合かもしれない）である。

逆も成立して、パス集合が有限であることは、アサイクリック性を特徴付ける。

傾向関数h（の事例）は、

• h(a) := maxlength(Path(∂ⁱⁿG, a))

で定義される。∂ⁱⁿG は、一般に入次数が0の頂点として定義される。空集合に関するmaxlengthは0と定義する。

この傾向関数で進行性埋め込みを作ると、入次数が0の頂点は、x_n+1 = 0 の超平面内に配置される。