During my linear programming class we saw this theorem:
Theorem: Let $A \in \mathbb{R}^{m \times n}$ where $\operatorname{rank}{(A)} = m \leq n $ and let $b \in \mathbb{R}^m-\{\bar{0}\}.$ Then the vector $\hat{x} \in \Omega = \{x \in \mathbb{R}^n : Ax = b, x \geq 0 \}$ is a vertex of $\Omega$ if and only if the columns of $A$ corresponding to the positive components of $\hat{x}$ are linearly independent.
and the definition of vertex was given as follows:
Definition: Let $\Omega \subseteq \mathbb{R}^n$ be a convex subset. A point $\hat{x} \in \Omega$ is said to be a vertex of $\Omega$ if and only if there do not exist elements $x,y \in \Omega$ and $\lambda \in (0,1)$ such that $$\hat{x} = \lambda y + (1- \lambda)x$$ where $\hat{x} \neq x, \hat{x} \neq y.$
Everything is good up until here. But then we saw a Corollary:
Corollary: The number of vertices of $\Omega = \{x \in \mathbb{R}^n : Ax = b, x \geq 0 \}$ is finite and is bounded above by $$\alpha^* =\binom{n}{0} +\binom{n}{1}+ \ldots+ \binom{n}{m}.$$
This is the part I don't understand.
According to my intuition, since $\operatorname{rank}(A) = m$, then the maximum number of linearly independent columns of $A$ is $m$. But there are a total of $n$ columns, so we can pick these columns in $\binom{n}{m}$ possible ways. Where would the other terms come from?
If anyone could explain to me how to find the bound for the number of vertices of $\Omega$, I would greatly appreciate it.
You are right, actually $\binom{n}{m}$ is a tighter upper bound and you have mentioned the reason.
Here is the link to Michel Goemans note that mention that bound and in fact provided an even tighter bound.
The loose upper bound could possibly due to some result that have not been proven in the lecture linking BFS to definition of a vertex.