A lower bound (usually crude but relatively easy to prove) on the amount of resources needed to solve a problem, based on the number of bits of information needed to uniquely specify the answer or some other structure related to the problem.
Example 1. Sorting a list using comparisons (is element at position P larger than the element at position Q) takes at least log_2(n!) operations because there are n! possible unsorted orderings.
Example 2. With probability approaching 1, a random (large, finite) graph has no automorphisms. This is because a graph with a nontrivial symmetry can be encoded in less space than writing down one bit per edge. OK, this is is an "information theoretic argument" rather than a lower bound on a computational problem, but the idea is the same.
Notice that example 2 fails for trees, which do generically have automorphisms. This can be seen because the number of bits of information to encode a tree is about log(n^n) = nlog(n), and while there would be a savings of data from having an automorphism, the additional number of bits needed to specify the automorphism is itself of order nlog(n) and the argument breaks down.