Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.

  1. Has this notion been formalized and studied? If yes, what is it called?
  2. What is known about upper- or, more importantly for me, lower bounds on d in terms of some (any) characteristics of H.

I'll be grateful for any relevant reference.

(For ordinary graphs, it is known that $d\leq 3$, so the interesting analogue would rather be the boxicity of a graph introduced by Roberts (1968). Various upper bounds on the boxicity are known, but lower bounds are rarer -- one appears in this paper by Adiga, Chandran and Sivadasan.)

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.