We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures escape the “curse of dimensionality”: they can be embedded in a bounded-dimensional space, or they have small VC-dimension or a short algebraic description.
What are the advantages of low dimensionality? (a) With the help of suitable topological and algebraic separator theorems, large families of geometric objects embedded in a fixed-dimensional space can be split into subfamilies of roughly the same size, and then the smaller families can be analyzed recursively. (b) Geometric objects in space can be compared by a number of naturally defined partial orders, so that one can utilize the theory of partially ordered sets. (c) Graphs and hypergraphs of bounded VC-dimension admit very small epsilon-nets and can be particularly well approximated by random sampling. (d) If the description complexity of a family of geometric objects is small, then the “combinatorial complexity” (number of various dimensional faces) of their arrangements is also small. This typically guarantees the existence of efficient algorithms to visualize, describe, control, and manipulate these arrangements..
