I've been thinking about the following problem (in context of linear programming):
How can the number of basic solutions of the LP problem $$Ax \leq b$$ change upon adding one more constraint $ \hat a x \leq \hat b $
Obviously the number of solutions can decrease (to zero, for instance), stay the same, and increase. My question is now, how much can it increase? Is is possible for the number of solutions to increase by more than 100%?
I can think of examples when is happens in case of unbounded polyhedra (for instance $ x \leq 0 \to x \leq 0, y \leq 0) $, but what happens if we assume it's bounded?
I would appreciate some insight
It can go from $n+1$ to $2n$, which is close to 100%. Consider (in $\mathbb R^3$) a pyramid whose base is a convex $n$-gon. It has $n+1$ vertices, and a half-space which cuts off just the apex will give rise to frustum (how I've longed to use that word!) with $2n$ vertices. But this kind of construction by chopping off a single vertex does not look like it will yield more than 100% vertex growth, as the number of edges from the cut-off vertex to the other vertices is at most $V-1$, so $V$ gets replaced by at best $V-1+V-1 = 2V-2$.
But if one slices off a single edge of a simplex with $V$ vertices, I think the number of edges cut will be $2(V-2)$, so one loses $2$ vertices and gains $2(V-2)$, going from $V$ to $V-2+2(V-2) = 3V-6$.
My guess is that this is far from optimal. Consider the probability simplex in $\mathbb R^{2n}$, intersected with the half-space cut out by $\sum_{i=1}^n x_i \le \sum_{i=n+1}^{2n} x_i$. I think this loses $O(n)$ vertices and creates $O(n^2)$.