My question concerns a hypothetical family of bipartite graphs, $G_i$.

Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of length $i$. Every edge in $G_i$ connects some red node to some blue node, and one fixed polynomial time algorithm (time polynomial in $i$) determines uniformly whether or not an edge connects a given red and blue node in any given $G_i$.

Now assume regularity for every $G_i$ --- every node in $G_i$ has the same degree as every other node in $G_i$. (The degree can vary with $i$.)

Matching theory says that every $G_i$ necessarily admits some matching (a.k.a. a factorization).

Must there exist (modulo standard conjectures, perhaps) an algorithm, time polynomial in $i$, that uniformly recognizes all the edges in some (uniform) family of matching?

My question concerns a hypothetical family of bipartite graphs, $G_i$.

Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of length $i$. Every edge in $G_i$ connects some red node to some blue node, and one fixed polynomial time algorithm (time polynomial in $i$) determines uniformly whether or not an edge connects a given red and blue node in any given $G_i$.

Now assume regularity for every $G_i$ --- every node in $G_i$ has the same degree as every other node in $G_i$. (The degree can vary with $i$.)

Matching theory says that every $G_i$ necessarily admits some matching (a.k.a. a factorization).

Must there exist (modulo standard conjectures, perhaps) an algorithm, time polynomial in $i$, that uniformly recognizes those edges present in some (uniform) family of matchings?

My question concerns a hypothetical family of bipartite graphs, $G_i$.

Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of length $i$. Every edge in $G_i$ connects some red node to some blue node, and one fixed polynomial time algorithm (time polynomial in $i$) determines uniformly whether or not an edge connects a given red and blue node in any given $G_i$.

Now assume regularity for every $G_i$ --- every node in $G_i$ has the same degree as every other node in $G_i$. (The degree can vary with $i$.)

Matching theory says that every $G_i$ necessarily admits some matching (a.k.a. a factorization).

Must there exist an algorithm, time polynomial in $i$, that uniformly recognizes all the edges in some (uniform) family of matching?

My question concerns a hypothetical family of bipartite graphs, $G_i$.

Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of length $i$. Every edge in $G_i$ connects some red node to some blue node, and one fixed polynomial time algorithm (time polynomial in $i$) determines uniformly whether or not an edge connects a given red and blue node in any given $G_i$.

Now assume regularity for every $G_i$ --- every node in $G_i$ has the same degree as every other node in $G_i$. (The degree can vary with $i$.)

Matching theory says that every $G_i$ necessarily admits some matching (a.k.a. a factorization).

Must there exist (modulo standard conjectures, perhaps) an algorithm, time polynomial in $i$, that uniformly recognizes all the edges in some (uniform) family of matching?