# Combinatorics Seminar

When: Sunday, May 4, 10am

Where: Schreiber 309

Speaker: Deepak Rajendraprasad, U. of Haifa

Title: Separation dimension of hypergraphs

## Abstract:

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.
(http://arxiv.org/abs/1212.6756)

redesigned by barak soreq