Lower bounds on the minimal fill-in when factorizing a positive symmetric matrix. Any help out there?

When computing a Cholesky factorization of a positive definite
symmetric matrix A, then it is well-known that a suitable symmetric
reordering helps keeping the the number of fill-ins and the total
number flops down.

Finding the optimal ordering is NP-hard but good orderings can be
obtained with the minimum degree, nested dissection (aka graph
partitioning based) algorithms.  Those algorithms provides an upper
bound on the minimal amount of fill-in. However, I wonder is there any
way to compute a nontrivial lower bound on the minimal amount of
fill-in?

I have been searching the literature but have not found a any good
reference.  Do you have any suggestions? The problem sounds hard I
know.

Why is a lower bound important? Well, it would help evaluate the
quality of the ordering algorithms that we have implemented in MOSEK
(www.mosek.com).  Moreover, the minimum degree ordering is usually
computational cheap whereas nested dissection is expensive. A lower
bound could help me determine when the minimum degree ordering
potentially could be improved by using nested dissection.