  We examine how sparse feasible solutions of integer programs are, on average.
Average case here means that we fix the constraint matrix and vary the
right-hand side vectors. For a problem in standard form with m equations, there
exist LP feasible solutions with at most m many nonzero entries. We show that
under relatively mild assumptions, integer programs in standard form have
feasible solutions with O(m) many nonzero entries, on average. Our proof uses
ideas from the theory of groups, lattices, and Ehrhart polynomials. From our
main theorem we obtain the best known upper bounds on the integer Caratheodory
number provided that the determinants in the data are small.
