Embedding dimension phenomena in intersection complete codes

Abstract

Two tantalizing invariants of a combinatorial code ${\mathcal {C}}\subseteq 2^{[n]}$ are ${{\,\mathrm{cdim}\,}}({\mathcal {C}})$ and ${{\,\mathrm{odim}\,}}({\mathcal {C}})$, the smallest dimension in which ${\mathcal {C}}$ can be realized by convex closed or open sets, respectively. Cruz, Giusti, Itskov, and Kronholm showed that for intersection complete codes ${\mathcal {C}}$ with $m+1$ maximal codewords, ${{\,\mathrm{odim}\,}}({\mathcal {C}})$ and ${{\,\mathrm{cdim}\,}}({\mathcal {C}})$ are both bounded above by $\max \{2,m\}$. Results of Lienkaemper, Shiu, and Woodstock imply that ${{\,\mathrm{odim}\,}}$ and ${{\,\mathrm{cdim}\,}}$ may differ, even for intersection complete codes. We add to the literature on open and closed embedding dimensions of intersection complete codes with the following results:

• If ${\mathcal {C}}$ is a simplicial complex, then ${{\,\mathrm{cdim}\,}}({\mathcal {C}}) = {{\,\mathrm{odim}\,}}({\mathcal {C}})$,

• If ${\mathcal {C}}$ is intersection complete, then ${{\,\mathrm{cdim}\,}}({\mathcal {C}})\le {{\,\mathrm{odim}\,}}({\mathcal {C}})$,

• If ${\mathcal {C}}\subseteq 2^{[n]}$ is intersection complete with $n\ge 2$, then ${{\,\mathrm{cdim}\,}}({\mathcal {C}}) \le \min \{2d+1, n-1\}$, where d is the dimension of the simplicial complex of ${\mathcal {C}}$, and

• For each simplicial complex $\Delta \subseteq 2^{[n]}$ with $m\ge 2$ facets, the code ${\mathcal {S}}_\Delta$ $:=(\Delta *(n+1)) \cup \{[n]\}$ $\subseteq 2^{[n+1]}$ is intersection complete, has $m+1$ maximal codewords, and satisfies ${{\,\mathrm{odim}\,}}({\mathcal {S}}_\Delta )=m$. In particular, for each $n\ge 3$ there exists an intersection complete code ${\mathcal {C}}\subseteq 2^{[n]}$ with ${{\,\mathrm{odim}\,}}({\mathcal {C}}) = \left( {\begin{array}{c}n-1\\ \lfloor (n-1)/2\rfloor \end{array}}\right)$.

A key tool in our work is the study of sunflowers: arrangements of convex open sets in which the sets simultaneously meet in a central region, and nowhere else. We use Tverberg’s theorem to study the structure of “k-flexible" sunflowers, and consequently obtain new lower bounds on ${{\,\mathrm{odim}\,}}({\mathcal {C}})$ for intersection complete codes ${\mathcal {C}}$.