Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not exist. What is a good lower bound on the amount of vertices in $V_1$ which can be matched? I am not interested in algorithmic approaches.

$\begingroup$ 0. If you insist that your graph has edges then 1 (think $K_{1,n}$). Your question is not well formulated. $\endgroup$ – Chris Godsil Jan 16 '13 at 13:55
Let $d$ denote the deficiency of the graph, i.e., the maximum difference between the a size of a subset of $V_1$ and the number of its neighbors (#vertices $$ #neighbors).
If $d \leq 0$ then the condition holds and the graph has a matching. Otherwise, there is a matching of size $V_1  d$.
To see why, add to $V_2$ a set of $d$ "imaginary" nodes, connected to all vertices of $V_1$. Then the condition holds for the new graph, and there is a matching for all vertices in $V_1$. Ignoring the $d$ neighbors of imaginary vertices, the remaining $V_1  d$ vertices of $V_1$ are matched to "real" vertices in $V_2$.