Graphic matroid embeddability and Sarkaria's Theorem

Abstract

In this paper, we intend to explore the consequences of Sarkaria's Theorem in the context of Graphic matroids. Sarkaria's Theorem states that if X is the chromatic number of the Kneser graph of a simplicial complex [Delta] and [Delta] has m vertices, then [Delta] cannot be embedded in Rd for d ? m ? X ? 2. This theorem provides a lower bound for embedding simplicial complexes. For example, it can be used to prove that K5 is non-planar. We start by covering important mathematical definitions related to the topic at hand, including matroids, graphic matroids, and the Kneser graph of a matroid. Then, we cover some examples to provide an understanding of Sarkaria's theorem and motivations for pursuing this topic. We show how Sarkaria's theorem is implemented and how it can tell us a matroid is non-embeddable in dimensions higher than the dimension of the matroid. After proving a special case with the embeddability of the graphic matroid of K5, we generalize the proof to include all complete graphs. This subsequently, can tell us information regarding the embeddability of any graphic matroid.