Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Oriented matroids and combinatorial neural codes

Published Web Location Commons 'BY' version 4.0 license

A combinatorial neural code \({\mathscr C}\subseteq 2^{[n]}\) is called convex if it arises as the intersection pattern of convex open subsets of \(\mathbb{R}^d\). We relate the emerging theory of convex neural codes to the established theory of oriented matroids, both with respect to geometry and computational complexity and categorically. For geometry and computational complexity, we show that a code has a realization with convex polytopes if and only if it lies below the code of a representable oriented matroid in the partial order of codes introduced by Jeffs. We show that previously published examples of non-convex codes do not lie below any oriented matroids, and we construct examples of non-convex codes lying below non-representable oriented matroids. By way of this construction, we can apply Mnëv-Sturmfels universality to show that deciding whether a combinatorial code is convex is NP-hard.

On the categorical side, we show that the map taking an acyclic oriented matroid to the code of positive parts of its topes is a faithful functor. We adapt the oriented matroid ideal introduced by Novik, Postnikov, and Sturmfels into a functor from the category of oriented matroids to the category of rings; then, we show that the resulting ring maps naturally to the neural ring of the matroid's neural code.

Mathematics Subject Classifications: 52C40, 13P25

Keywords: Oriented matroids, convex neural codes, hyperplane arrangements

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View