Generic bipartite reconstruction by low-order type constraints

Let G=(U,V,E)G=(U,V,E) be a bipartite graph with U=u|U|=u and V=v|V|=v, and let D(G)\mathcal{D}(G) denote its vertex-deletion deck. Assume that GG is 2-connected, not regular, and has minimum degree at least 66. For each vertex define its type by τ=(deg,P)\tau=(\deg,P), where PP is its neighbor-degree profile, and let R(,)R(\cdot,\cdot) denote the resulting type-count constraints. Generic bipartite reconstruction conjecture. For generic such GG, the deck determines GG uniquely up to bipartite isomorphism, and GG 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.