  In the 1970's, Lov\'asz built a bridge between graphs and alternating matrix
spaces, in the context of perfect matchings (FCT 1979). A similar connection
between bipartite graphs and matrix spaces plays a key role in the recent
resolutions of the non-commutative rank problem
(Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS
2017). In this paper, we lay the foundation for another bridge between graphs
and alternating matrix spaces, in the context of independent sets and vertex
colorings. The corresponding structures in alternating matrix spaces are
isotropic spaces and isotropic decompositions, both useful structures in group
theory and manifold theory.
  We first show that the maximum independent set problem and the vertex
c-coloring problem reduce to the maximum isotropic space problem and the
isotropic c-decomposition problem, respectively. Next, we show that several
topics and results about independent sets and vertex colorings have natural
correspondences for isotropic spaces and decompositions. These include
algorithmic problems, such as the maximum independent set problem for bipartite
graphs, and exact exponential-time algorithms for the chromatic number, as well
as mathematical questions, such as the number of maximal independent sets, and
the relation between the maximum degree and the chromatic number. These
connections lead to new interactions between graph theory and algebra. Some
results have concrete applications to group theory and manifold theory, and we
initiate a variant of these structures in the context of quantum information
theory. Finally, we propose several open questions for further exploration.
  This paper is dedicated to the memory of Ker-I Ko.
