A Combinatorics Problem

A bit over four years ago I was given what remains one of my favorite combinatorics problems. It goes like this:

Define A_n,k to be the set consisting of all k-element subsets of the set [n] (the integers 1 to n). For instance, we have A_4,2 = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}. (Thus, |A_n,k| is equal to the binomial coefficient.) For each n > k ≥ 0, we define a (possibly partial) function f : A_n,k → A_n,k+1 by the following "greedy inclusion algorithm".

First, order the sets in both A_n,k and A_n,k+1 in lexicographic order (in increasing order of smallest element, then, in increasing order of second-smallest element, etc., so that they are in an order as in the example of A_4,2 above). Initially mark each element of A_n,k+1 as unused. For each set x ∈ A_n,k, in lexicographic order, do the following. Find out if there is some y ∈ A_n,k+1 such that x ⊆ y and y is marked as unused. If there is not, f(x) is undefined. If there is, take the earliest such y (in lexicographic order), define f(x) = y, and then mark that y as used. In either case, continue on to the next element of A_n,k.

This algorithm gives a partial function f which is defined on some (possibly all) elements of A_n,k. The question is this:
(a) Find the pairs (n, k) where f is defined on all of A_n,k.
(b) Find a simple, fast (linear time in n is good; if you are pedantic about integer comparisons not actually taking constant time this might be instead O(n log n)) method for taking an element x of A_n,k and determining whether f(x) is defined and, if so, its value.

As it's been four years since I solved the problem, I don't remember the details of the solution. Thus, I'll put the solution in a later post when I figure them out again.