Mathematically prove why sparsity leads to model overfitting
I don't think sparsity in itself cause the model to over-fit, but it can increase the chance of it.
Overfitting is not a state in itself. What I meant is that if I say that my training accuracy is 92%. Can you predict if it's over-fit?
 It's a relative state i.e. you can only know it if I tell the accuracy on test/new data.
It means, farther the new data from the training data more is the chance that the model will Over-fit.
In a high dimension space, let's say a 10 features dataset -
To fill the space evenly you need 1010 record which is 10Bn. Normally you might have 1Mn.
So, it's almost 9999/10000 chance that you will get a new data outside the training data.
Definitely the model will have a very high chance to fail(Assuming no Regularization in place)(I am not saying that it will fail 9999 times)
But
 This is completely based on the assumption that every feature will have values spanning the full space.
 Let's say 6 out of 10 features have only 2 possible value. Then we will have only 6.4Mn datasets required to fill the space evenly. In this case, there is very less chance of the model to be over-fit compared to the last case.
Although the model will be very complex and wiggly(a lot of branches/leaves), but not a lot over-fitted