Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文869 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/869 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月7日 7:50 に公開します）。

@misc{yamagishi2026yoi869,
  author = {Yamagishi, Yuuki},
  title = {The Number of Orderings Is Set Neither by the Number of Edges Nor by the Number of Comparable Pairs},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/869},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

順序の制約が多いほど並べ方は減る、と思いやすい。本稿は、点 $6$ 個の有向非巡回グラフを全部数え、並べ方の数が制約の本数では決まらないことを数える。新しい定理も法則も主張しない。

第一に、並べ方の数は両端では決まっている。辺が無ければ $720$ 通り、一本道なら $1$ 通りで、どちらも数え上げと一致した（第2節）。

第二に、これが本稿の芯である。同じ辺の本数でも、並べ方の数は大きく散らばる。辺 $5$ 本のグラフ $3003$ 個で、並べ方は $1$ 通りから $120$ 通りまで、$39$ 通りの値をとる（第2節）。

第三に、比べられる組の数で揃えても決まらない。推移で決まる組まで数えて $8$ 組に揃えても、並べ方は $14$ 通りから $48$ 通りまで、$\mathbf{3.428571}$ 倍動く（第3節）。

第四に、推移で決まる辺は並べ方を減らさない。一本道 $0\to1\to\dots\to5$ に辺 $0\to5$ を足しても $1$ 通りのまま、辺の本数だけが増える（第3節）。

第五に、並べ方の数は二通りに数えて一致した。置ける点を一つずつ足す数え方と、$720$ 通りの並べ替えを全部試す数え方が、無作為に選んだ $400$ 個で一致した（第2節）。

第六に、分離子は、辺の本数を数えるか、辺が残す答えの通り数を数えるかである。残りを比べて決める回数の下界は $\log_2$（並べ方の数）で、辺 $5$ 本でも $0$ から $\mathbf{6.906891}$ まで動く（第4節）。

キーワード：トポロジカルソート、有向非巡回グラフ、線形拡大、推移閉包、比べる回数の下界

Abstract

It is easy to assume that more ordering constraints leave fewer orderings.This paper counts all directed acyclic graphs on $6$ vertices and finds that the number of orderings is not set by the number of constraints.No new theorem or law is claimed.

First, the number of orderings is fixed at the two ends: $720$ with no edges and $1$ for a single chain, both confirmed by enumeration (Section 2).

Second, and this is the core. With the same number of edges, the number of orderings scatters widely: over the $3003$ graphs with $5$ edges, it takes $39$ values from $1$ to $120$ (Section 2).

Third, fixing the number of comparable pairs does not set it either: fixing the pairs, counted through transitivity, at $8$ still leaves $14$ to $48$ orderings, a factor of $\mathbf{3.428571}$ (Section 3).

Fourth, edges implied by transitivity do not reduce the orderings: adding $0\to5$ to the chain $0\to1\to\dots\to5$ leaves $1$ ordering; only the edge count rises (Section 3).

Fifth, the counts were obtained two ways and agree: adding placeable vertices one at a time and trying all $720$ permutations agreed on $400$ randomly chosen graphs (Section 2).

Sixth, the separator is whether one counts the edges or the number of answers they leave: the lower bound on the comparisons still needed is $\log_2$ of the number of orderings, which ranges from $0$ to $\mathbf{6.906891}$ even with $5$ edges (Section 4).

Keywords: topological sort, directed acyclic graph, linear extension, transitive closure, lower bound on comparisons

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/869/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/869 はいつも最新の版を指します）。

YOI の一覧へ