You are here

Embedding dimensions of convex codes

Amzi Jeffs, University of Washington
Wednesday, February 12, 2020 - 3:30pm to 5:00pm
PDL C-401
Amzi Jeffs

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.

Share