We consider the problem of spectrum sharing in device-to-device communication systems. We define a new concept of information-theoretic independent sets (ITIS), which indicates the sets of users for which simultaneous communication and treating the interference from each other as noise is information-theoretically optimal (to within a constant gap). Based on this concept, we develop a new spectrum sharing mechanism, called information-theoretic link scheduling (ITLinQ), which at each time schedules those users that form an ITIS. We demonstrate that ITLinQ can outperform similar state-of-the-art spectrum sharing mechanisms, such as FlashLinQ, by more than a 100% of sum-rate gain, while keeping the complexity at the same level.