Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

@misc{yamagishi2026yoi940,
  author = {Yamagishi, Yuuki},
  title = {Bisecting by the Eigenvector Hits the Minimum for a Thin Neck but Splits a Ladder with a Tail Top from Bottom},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/940},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

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

書誌

要旨

グラフの点を同じ数ずつ二つに分け、間を切る辺をなるべく少なくしたいとき、ラプラシアンの二番目の固有ベクトルの値の大小で分ける方法がよく使われる。本稿は、首の細いグラフ・格子・はしごの横木を後ろ半分だけにした「尾の付いたはしご」で、固有ベクトルの値の中央で分けた切る辺の数を、総当たりで探した最小の二等分と比べる。新しい定理も法則も主張しない。

第一に、首の細いグラフと格子では、固有ベクトルの分け方は最小に当たる。点 $8$ 個の完全グラフ二つを辺 $2$ 本でつないだグラフ（二番目の固有値 $0.417424$）では $2$ 本、$4\times4$ の格子（$0.585786$）では $4$ 本を切り、どちらも最小と同じだった（第2節）。

第二に、尾の付いたはしごでは、最小より多く切る。上下の道が $8$ 点ずつ（二番目の固有値 $0.103300$）なら $4$ 本、$10$ 点ずつ（$0.071278$）なら $5$ 本を切り、最小はどちらも $2$ 本で、比は $\mathbf{2.000000}$・$\mathbf{2.500000}$ だった（第2節）。

第三に、固有ベクトルの分け方は、上の道と下の道を分けていた。二つの大きさとも、中央で分けた二組はちょうど上の道と下の道で、切ったのは横木だった。最小の二等分は、二本の道を尾とはしごの境で左右に切る $2$ 本である（第3節）。

第四に、丸める前と後で、上下と左右の順が入れ替わる。値の差の二乗の和を値の二乗の和で割った量は、固有ベクトルそのもの（丸める前）で $0.103300$・$0.071278$ と最も小さいが、二つの値に丸めると上下の分け方は $1.000000$、左右の分け方は $0.500000$・$0.400000$ で、左右のほうが小さかった（第3節）。

第五に、分離子は、二つの値に丸める前の揺れで比べるか、丸めた後の本数で比べるかである。固有ベクトルは丸める前の量を最小にする。切る辺の本数は丸めた後の量で、二つの最小は同じ分け方を指すとは限らない（第4節）。

キーワード：スペクトル分割、フィードラーのベクトル、ラプラシアン、最小の二等分、レイリー商、グラフの分割

Abstract

When the vertices of a graph are to be divided into two equal halves while cutting as few edges between them as possible, a common method divides them by the values of the second eigenvector of the Laplacian.This paper takes a graph with a thin neck, a grid, and a “ladder with a tail” whose rungs cover only the back half, and compares the number of edges cut by splitting at the median of the eigenvector with the minimum bisection found by exhaustive search.No new theorem or law is claimed.

First, for the thin neck and the grid, the eigenvector split hits the minimum: for two complete graphs on $8$ vertices joined by $2$ edges (second eigenvalue $0.417424$) it cut $2$ edges, and for the $4\times4$ grid ($0.585786$) $4$ edges, both equal to the minimum (Section 2).

Second, for the ladder with a tail, it cuts more than the minimum: with top and bottom paths of $8$ vertices each (second eigenvalue $0.103300$) it cut $4$ edges, and with $10$ each ($0.071278$) $5$ edges, while the minimum was $2$ in both cases, ratios of $\mathbf{2.000000}$ and $\mathbf{2.500000}$ (Section 2).

Third, the eigenvector split separated the top path from the bottom path: for both sizes, the two halves split at the median were exactly the top path and the bottom path, and what was cut was the rungs. The minimum bisection cuts the two paths left from right at the boundary between tail and ladder, $2$ edges (Section 3).

Fourth, before and after rounding, top-bottom and left-right swap order: the sum of squared differences divided by the sum of squares was smallest for the eigenvector itself (before rounding), $0.103300$ and $0.071278$, but rounded to two levels the top-bottom split gave $1.000000$ and the left-right split $0.500000$ and $0.400000$, the left-right being smaller (Section 3).

Fifth, the separator is whether one compares the values before rounding to two levels or the edge counts after: the eigenvector minimizes the quantity before rounding. The number of edges cut is the quantity after rounding, and the two minima need not point to the same split (Section 4).

Keywords: spectral bisection, Fiedler vector, Laplacian, minimum bisection, Rayleigh quotient, graph partitioning

版の記録

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

YOI の一覧へ