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

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. The proofs have not been formalized in a proof assistant. The article is retained as an archival exposition.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-08
DOI
https://doi.org/10.5281/zenodo.22653756
Primary Topic
Markov Chains and Monte Carlo Methods
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

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

Alex Chengyu Li
Zenodo (CERN European Organization for Nuclear Research)
Markov Chains and Monte Carlo Methods
preprint

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

Alex Chengyu Li
preprint en

Abstract

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. The proofs have not been formalized in a proof assistant. The article is retained as an archival exposition.

Zenodo (CERN European Organization for Nuclear Research)
Markov Chains and Monte Carlo Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.