Crab Research
成果一覧へ戻る
組合せ論

占有数が有界なトークングラフのマッチングと独立数:独立に進められた開発

Matchings and Independence in Bounded-Occupancy Token Graphs: Concurrent Independent Development

ワーキングペーパー · Zenodo初回公開 改訂

研究概要

区別できない一定個数のトークンをグラフの頂点に配置し、一回の移動で一つのトークンを一辺に沿って動かす。本稿は Reyes、Dalfó、Fiol の予想3.6について独立に得た証明と、占有数が有界な場合の帰結を記録する。Patel が先に公開した完全解答は、占有数が無制限の場合を同じ基本構成で解いている。各マッチング辺のトークン総数を固定し、道の直積上でマッチングを構成する方法である。改訂稿は独立に進められた研究の解説として保存し、最初の解答としての優先権を主張しない。

元の公開問題

Reyes–Dalfó–Fiol 予想 3.6:スーパートークングラフの独立数

Mónica A. Reyes, Cristina Dalfó and Miquel Àngel Fiol: On supertoken graphs — arXiv 2604.06164v1: Conjecture 3.6, the independence-number equality for the unrestricted-occupancy supertoken graph, in which each move transfers one token along one base edge.

Shivam Patel: complete solution — Earlier public contribution; exact scope and chronology stated in the attribution correction.

原文要旨(英語)

A token configuration assigns nonnegative occupancies of total size k to the vertices of a graph; a move transfers one token along one edge. This article records concurrent independent development of a matching proof of the independence-number conjecture of Reyes, Dalfó and Fiol. An earlier public solution by Shivam Patel uses the same core construction for unrestricted occupancy. If a bipartite base graph has a matching saturating one part, the lifted matching saturates the odd-occupancy configurations, so the even configurations form a maximum independent set. We present this construction together with its bounded-occupancy consequences: even common capacities retain parity saturation, unequal capacities admit an explicit local classification, and odd common capacities allow counterexamples. Products of paths also give sharp general matching bounds, exact Shannon capacities in the saturated cases, and fixed-host asymptotic densities.

Concurrent development and prior work. The mathematical statements and proofs are unchanged, and comparison with prior work has identified no mathematical error. Patel's complete solution was publicly posted on 21 August 2026, before this article's first public version on 6 September 2026. Both proofs use the same matched-edge-total and product-of-paths construction. This corrected version preserves an independently developed exposition and capacity consequences, without a first-solution priority claim.

公開要旨の出典

token graphssupertoken graphsmatchingsindependence numberbounded occupancyShannon capacityconcurrent independent development

数学の検証

内部レビュー完了

Paper Close は、公開前に準備と内部レビューを終え、ワーキングペーパーとして公開したことを示します。通常の学術プレプリントとしてお読みいただき、議論してください。今後の検証や議論によって修正が必要になる場合があります。完全な形式化や外部査読を意味するものではありません。

検証基準
成果一覧へ戻る
戻る: 数学