Generic bipartite reconstruction by low-order type constraints
Generic bipartite reconstruction by low-order type constraints
Let be a bipartite graph with and , and let denote its vertex-deletion deck. Assume that is 2-connected, not regular, and has minimum degree at least . For each vertex define its type by , where is its neighbor-degree profile, and let denote the resulting type-count constraints. Generic bipartite reconstruction conjecture. For generic such , the deck determines uniquely up to bipartite isomorphism, and can be reconstructed in polynomial time by recovering degrees and profiles, imposing the type-count constraints, and selecting the unique feasible adjacency using two-deletion compatibility. This is an experimentally motivated claim restricted to a generic, moderately dense regime; neither the genericity condition nor the asserted polynomial-time reconstruction is established in the supplied text.
Sources & referencesView supporting material
Primary source
Gergely Bérczi, “Evolving Local Corrections for Global Constructions in Combinatorics”, arXiv:2603.06692 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.