Lower Bounds for Data Structures
There is a really nice talk on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):



See the paper for details. Some other papers by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "Lower Bound Techniques for Data Structures" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.