Embedding dimensions of convex codes

Amzi Jeffs, University of Washington
-
PDL C-401

Every code \$\mathcal C\subseteq 2^{[n]}\$ has an open embedding dimension \$\text{odim}(\mathcal C)\$, the smallest dimension in which it is realized as the intersection pattern of a collection of convex open sets (or \$\infty\$ if no realization exists). The closed embedding dimension \$\text{odim}(\mathcal C)\$ is defined similarly, but using closed convex sets. The relationship between \$\text{odim}(\mathcal C)\$ and \$\text{cdim}(\mathcal C)\$—as well as upper and lower bounds for each—has proven somewhat mysterious in general. We'll show that, surprisingly, \$\text{odim}(\mathcal C)\$ may be exponential in \$n\$, while \$\text{cdim}(\mathcal C) < n\$ in all known examples. We'll contextualize these results using a partial order on all codes, in analogy to graph minors.