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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.