An arXiv preprint says it has found a unique way to break every finite, connected, simple bipartite graph in its scope into induced atomic blocks. The blocks are arranged in block-triangular form, giving each graph a canonical internal map. The result is a theorem about mathematical objects, not an empirical finding: no observed sample is described.
The paper studies bipartite graphs, mathematical networks divided into two sides, through a grid model in which empty subrectangles called holes encode structure. Its central question is how that representation can support a canonical decomposition into m-atomic bricks, and what follows from the characteristic m.
The number at the centre
The paper defines the characteristic as m = b − αp(T0), and calls a brick excessive when m > 0. The value belongs to the formal setup: it is determined by the graph representation rather than estimated from observations. The paper uses the characteristic to distinguish the structures it studies.
That distinction matters because the work is not testing a hypothesis against data. It develops definitions and derives consequences from them. Its main results concern the existence and uniqueness of the decomposition, the arithmetic of m, and the relationship between excessiveness and m-extendability.
A decomposition built from independent sets
To construct the blocks, the paper uses what it calls a maximum proper independent set, shortened to MPIS. For a given brick, an MPIS calculation supplies the set used by the procedure to generate the excessive decomposition in block-triangular form.
The selected set is therefore part of the construction, not merely a label attached after the fact. The paper's procedure uses the MPIS result to determine how the grid model is divided into successive blocks.
The implementation claim is narrower than a performance claim. The paper says the MPIS oracle can be implemented through maximum matching and that the block-triangular decomposition is computable in polynomial time. It also says computational complexity is not analyzed in detail, so the practical cost of the construction remains unexamined.
The matching structure survives the split
The decomposition carries a precise statement about maximum matchings. Edges between atomic blocks from different regions may exist, but the paper says those cross-region edges cannot participate in a maximum matching. Every maximum matching is instead the union of maximum matchings from the individual atomic blocks.
A matching is a selection of graph edges made under the paper's structural constraints, while a maximum matching is the largest selection of that kind. On that basis, the theorem says the canonical blocks preserve the graph's maximum-matching structure even when links cross between regions.
The refinement is not uniform across all block labels. D and E blocks are split into connected components, while square C blocks are already atomic. Those refined pieces are the induced blocks that appear in the canonical decomposition.
What excessiveness says
One proposition addresses a disconnected vertical excessive brick. There, the paper states m = min{s1, …, sp}; it also gives an additive imbalance relation, imb(W1) + ··· + imb(Wp) = imb(T0) = b − a. In plain language, the characteristic follows the smallest component strip value, while the component imbalances add to the total.
Another result links that same characteristic to the completion of matchings. Every matching of size m in an excessive brick can be extended to a maximum matching. This is an existence statement inside the formal graph model, not evidence that a software routine will find the extension quickly.
Eleven classes, one framework
Beyond the canonical split, the paper gives an exact classification into eleven disjoint structural classes. The classes are based on the presence of D, C and E blocks, turning the decomposition into a catalogue of the forms allowed by the framework.
The classification complements the uniqueness theorem. The canonical decomposition says how the pieces are arranged; the eleven-class result describes the block patterns that can occur within the paper's setup.
A lattice hidden in the choices
The MPIS construction leads to another formal structure. Ordered by inclusion of their projections on the A side, maximum proper independent sets correspond to ideals of the C-block poset and form a distributive lattice.
The correspondence means that the maximum proper independent sets are not treated as an unstructured list. They have an order, and that order has the lattice properties stated in the paper. Because the MPIS procedure generates the block-triangular decomposition, the C-block ordering also helps relate the choices used in that construction.
The grid gives a geometric test
Under the paper's stated conditions, when both D and E regions are present, the intersection of all maximum holes is exactly row(E) × col(D). In the grid model, that identifies the rows and columns shared by every maximum hole in that configuration.
This is one of the framework's clearest geometric consequences: a statement about all maximum holes is translated into a fixed rectangle described by two block regions. The result remains conditional on the D-and-E setup; it is not presented as a claim about every possible graph configuration.
Paper data and sources
Original title: A Canonical m-Atomic Decomposition of Bipartite Graphs via a Grid Model
Authors: Béla Jónás
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text