Petrov's balls conjecture for biregular labeled multigraphs

From papers

Let a bipartite labeled multigraph be a tuple (L,R,E,u,v)(L,R,E,u,v), where u:ELu:E\to L and v:ERv:E\to R. Let An,kA_{n,k} be the set of biregular bipartite labeled multigraphs with L=[n]L=[n], R=[k]R=[k], and E=[n]×[k]E=[n]\times[k]; let II be the set of involutions in the permutation group of [n]×[k][n]\times[k]. For functions u,vu,v with common domain EE, let [u,v][u,v] denote the weighted L×RL\times R matrix whose (x,y)(x,y) entry counts edges ee with u(e)=xu(e)=x and v(e)=yv(e)=y, and let W[n],[k]W_{[n],[k]} be the all-ones matrix. Petrov's balls conjecture. For every (u,v)An,k(u,v)\in A_{n,k}, there exists an involution ιI\iota\in I such that

[uι,v]=W[n],[k].[u\circ\iota,v]=W_{[n],[k]}.

In the balls-and-colors interpretation, this asserts that the balls can be paired or left fixed so that every girl ends with exactly one ball of each color, with every ball involved in at most one swap. The conjecture implies the weak balls conjecture, but the general statement remains unproved; special cases are established in the paper.

Progress summary

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

Sources & referencesView supporting material

Primary source

Ilya I. Bogdanov, Fedor Petrov, Anton Sadovnichiy and Fedor Ushakov, “Biregular bipartite labeled multigraphs and perfect matchings in bipartite tensor products”, arXiv:2603.18253 (2026).

Solutions 0

No solutions have been posted yet.