Convex union representability and convex codes

DOI10.1093/IMRN/RNZ055MaRDI QIDQ3382664zbMATH OpenOpenAlexWikidataFDO

Authors R. Amzi Jeffs, Isabella Novik

Publication date 21 September 2021

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.03992

zbMATH Keywords

collapsible simplicial complexneural code

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Abstract: We introduce and investigate $d$-convex union representable complexes: the complexes that arise as the nerve of a finite collection of convex open sets in $mathbb{R}^d$ whose union is also convex. Chen, Frick, and Shiu recently proved that such complexes are collapsible and asked if all collapsible complexes are convex union representable. We disprove this by showing that there exist shellable and collapsible complexes that are not convex union representable; there also exist non-evasive complexes that are not convex union representable. In the process we establish several necessary conditions for a complex to be convex union representable such as: that such a complex $Delta$ collapses onto the star of any face of $Delta$, that the Alexander dual of $Delta$ must also be collapsible, and that if $k$ facets of $Delta$ contain all free faces of $Delta$, then $Delta$ is $(k-1)$-representable. We also discuss some sufficient conditions for a complex to be convex union representable. The notion of convex union representability is intimately related to the study of convex neural codes. In particular, our results provide new families of examples of non-convex neural codes.

Recommendations

• On open and closed convex codes
• What makes a neural code convex?
• Neural codes with three maximal codewords: convexity and minimal embedding dimension
• Oriented matroids and combinatorial neural codes
• Dimension gaps between representability and collapsibility

Cited in

(13)

• Every binary code can be realized by convex sets
• Embedding dimension phenomena in intersection complete codes
• Non-monotonicity of closed convexity in neural codes
• Neural codes with three maximal codewords: convexity and minimal embedding dimension
• Neural codes and the factor complex
• Sunflowers of convex open sets
• Neural codes, decidability, and a new local obstruction to convexity
• Nondegenerate Neural Codes and Obstructions to Closed-Convexity
• Oriented matroids and combinatorial neural codes
• Open, closed, and non-degenerate embedding dimensions of neural codes
• Realizing convex codes with axis-parallel boxes
• Order-forcing in neural codes
• On the limitations of ROBDDs in deciding the evasiveness of Boolean functions

This page was built for publication: Convex union representability and convex codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3382664)