The problem of ranking, in which the goal is to learn a real-valued ranking function that induces a ranking or ordering over an instance space, has recently gained attention in mahine learning. We define a model of learnability for ranking functions in a particular setting of the ranking problem known as the bipartite ranking problem, and derive a number of results in this model. Our first main result provides a sufficient condition for the learnability of a class of ranking functions F we show that F in learnable in its bipartite rank-shatter coefficients, which measure the richness of a ranking function class in the same as do the standard VC-dimension related shatter coefficients (growth function) for classes of classification functions, d not grow too quickly. Our second main result gives a necessary condition for learnability: we define a new combinatorial parameter for a class of ranking functions F that we term the rank dimension of F, and show that F is learnable only if its rank dimersion in finite. Finally, we investigate questions of the computational complexity of learning ranking functions.