Combinatorics Seminar

When: Sunday, May 4, 10am

Where: Schreiber 309

Speaker: Deepak Rajendraprasad, U. of Haifa

Title: Separation dimension of hypergraphs


The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in the k-dimensional Euclidean space R^k such that any pair of disjoint edges in H can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of permutations of the vertices of H such that for any two disjoint edges of H, there exists at least one permutation in F in which all the vertices in one edge precede those in the other.

The study of similar families of permutations dates back to the work of Ben Dushnik in 1940s where he introduced the notion of k-suitability while studying the dimenension of partially ordered sets. But the notion of separation dimension defined above is new and some of the initial results on the same can be found in [1]. The talk will focus on one of the partial results and the corresponding open question in [1], namely how large can the separation dimension of a bounded degree graph be?

1. Manu Basavaraju, L Sunil Chandran, Rogers Mathew, and Deepak Rajendraprasad. Pairwise suitable family of permutations and boxicity. arXiv preprint arXiv:1212.6756, 2012. (

w3c valid   accessible website
redesigned by barak soreq