MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.