We consider the number of irregular pairs in a Szemerédi regularity partition of a finite graph. Under the assumption of bounded Vapnik-Chervonenkis dimension, we obtain a better lower bound for this number than that known for the general case. The result extends to structures in arbitrary finite relational languages. This is joint work with N. Ackerman and C. Freer.