Boxicity and Separation Dimension

Abstract

A family $\mathcal {F}$ of permutations of the vertices of a hypergraph $H$ is called pairwise suitable for $H$ if, for every pair of disjoint edges in $H$, there exists a permutation in $\mathcal {F}$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $H$ is called the separation dimension of $H$ and is denoted by $\pi (H)$. Equivalently, $\pi (H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded in $\mathbb {R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $H$ is equal to the boxicity of the line graph of $H$. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.

Manu Basavaraju: Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013)/ERC Grant Agreement n. 267959.

Rogers Mathew and Deepak Rajendraprasad: Supported by VATAT Postdoctoral Fellowship, Council of Higher Education, Israel.

1 Introduction

Let $\sigma :U \rightarrow [n]$ be a permutation of elements of an $n$-set $U$. For two disjoint subsets $A,B$ of $U$, we say $A \prec _{\sigma } B$ when every element of $A$ precedes every element of $B$ in $\sigma$, i.e., $\sigma (a) < \sigma (b), \forall (a,b) \in A \times B$. Otherwise, we say $A \nprec _{\sigma } B$. We say that $\sigma$ separates $A$ and $B$ if either $A \prec _{\sigma } B$ or $B \prec _{\sigma } A$. We use $a \prec _{\sigma } b$ to denote $\{a\} \prec _{\sigma } \{b\}$. For two subsets $A, B$ of $U$, we say $A \preceq _{\sigma } B$ when $A \setminus B \prec _{\sigma } A\cap B \prec _{\sigma } B \setminus A$.

In this paper, we introduce and study a notion called pairwise suitable family of permutations for a hypergraph $H$ and the separation dimension of $H$.

Definition 1

A family $\mathcal {F}$ of permutations of $V(H)$ is pairwise suitable for a hypergraph $H$ if, for every two disjoint edges $e,f \in E(H)$, there exists a permutation $\sigma \in \mathcal {F}$ which separates $e$ and $f$. The cardinality of a smallest family of permutations that is pairwise suitable for $H$ is called the separation dimension of $H$ and is denoted by $\pi (H)$.

A family $\mathcal {F}= \{\sigma _1, \ldots , \sigma _k\}$ of permutations of a set $V$ can be seen as an embedding of $V$ into $\mathbb {R}^k$ with the $i$-th coordinate of $v \in V$ being the rank of $v$ in the $\sigma _i$. Similarly, given any embedding of $V$ in $\mathbb {R}^k$, we can construct $k$ permutations by projecting the points onto each of the $k$ axes and then reading them along the axis, breaking the ties arbitrarily. From this, it is easy to see that $\pi (H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded into $\mathbb {R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. This motivates us to call such an embedding a separating embedding of $H$ and $\pi (H)$ the separation dimension of $H$.

The notion of separation dimension introduced here seems so natural but, to the best of our knowledge, has not been studied in this generality before. The authors of [15] provide suggested applications motivating the study of permutation covering and separation problems on event sequencing of tasks. Apart from that, a major motivation for us to study this notion of separation is its interesting connection with a certain well studied geometric representation of graphs. In fact, we show that $\pi (H)$ is same as the boxicity of the intersection graph of the edge set of $H$, i.e., the line graph of $H$.

An axis-parallel $k$-dimensional box or a $k$ -box is a Cartesian product $R_1 \times \cdots \times R_k$, where each $R_i$ is a closed interval on the real line. For example, a line segment lying parallel to the $X$ axis is a $1$-box, a rectangle with its sides parallel to the $X$ and $Y$ axes is a $2$-box, a rectangular cuboid with its sides parallel to the $X$, $Y$, and $Z$ axes is a $3$-box and so on. A box representation of a graph $G$ is a geometric representation of $G$ using axis-parallel boxes as follows.

Definition 2

The $k$ -box representation of a graph $G$ is a function $f$ that maps each vertex in $G$ to a $k$-box in $\mathbb {R}^k$ such that, for all vertices $u,v$ in $G$, the pair $\{u,v\}$ is an edge if and only if $f(u)$ intersects $f(v)$. The boxicity of a graph $G$, denoted by $\mathrm{boxicity}(G)$, is the minimum positive integer $k$ such that $G$ has a $k$-box representation.

The concept of boxicity was introduced by F.S. Roberts in 1969 [20]. He showed that every graph on $n$ vertices has an $\left\lfloor n/2 \right\rfloor$-box representation. The $n$-vertex graph whose complement is a perfect matching is an example of a graph whose boxicity is equal to $n/2$. Upper bounds for boxicity in terms of other graph parameters like maximum degree, treewidth, minimum vertex cover, degeneracy etc. are available in literature. Studies on box representations of special graph classes too are available in abundance. Scheinerman showed that every outerplanar graph has a $2$-box representation [21] while Thomassen showed that every planar graph has a $3$-box representation [23]. Results on boxicity of series-parallel graphs [8], Halin graphs [12], chordal graphs, AT-free graphs, permutation graphs [14], circular arc graphs [7], chordal bipartite graphs [11] etc. can be found in literature. Here we are interested in boxicity of the line graph of hypergraphs. The line graph of a hypergraph $H$, denoted by $L(H)$, is the graph with vertex set $V(L(H)) = E(H)$ and edge set $E(L(H)) = \{\{e,f\} : e, f \in E(H), e \cap f \ne \emptyset \}$.

For the line graph of a graph $G$ with maximum degree $\varDelta$, it was shown by Chandran, Mathew and Sivadasan that its boxicity is in $O\left( \varDelta \log \log \varDelta \right)$ [13]. It was in their attempt to improve this result that the authors stumbled upon pairwise suitable family of permutations and its relation with the boxicity of the line graph of $G$. In an arXiv preprint version of this paper available at [6], we improve the upper bound for boxicity of the line graph of $G$ to $2^{9 \mathrm{log}^{\star }\varDelta } \varDelta$, where $\mathrm{log}^{\star }\varDelta$ denotes the iterated logarithm of $\varDelta$ to the base $2$, i.e. the number of times the logarithm function (to the base $2$) has to be applied so that the result is less than or equal to $1$. In a recent joint work with Noga Alon, we have shown that there exist graphs of maximum degree $\varDelta$ whose line graphs have boxicity in $\varOmega (\varDelta )$. Bounds for separation dimension of a graph based on its treewidth, degeneracy etc. are also established in the arXiv version.

1.1 Outline of the Paper

The remainder of this paper¹ is organised as follows. A brief note on some standard terms and notations used throughout this paper is given in Sect. 1.2. Section 2 demonstrates the equivalence of separation dimension of a hypergraph $H$ and boxicity of the line graph of $H$. In Sect. 3.1, we characterize graphs of separation dimension $1$. Using a probabilistic argument, in Sect. 3.2, we prove a tight (up to constants) upper bound for separation dimension of a graph based on its size. Section 3.3 relates separation dimension with acyclic chromatic number. In Sect. 3.4, using Schnyder’s celebrated result on planar drawing, we show that the separation dimension of a planar graph is at most $3$. This bound is the best possible as we know of series-parallel graphs (that are subclasses of planar graphs) of separation dimension $3$. In Sect. 3.5, we prove the theorem that yields a non-trivial lower bound to the separation dimension of a graph. This theorem and its corollaries are used in establishing the tightness of the upper bounds proved. Moreover, the theorem is used to prove a lower bound for the separation dimension of a random graph in Sect. 3.6.

Once again, in Sect. 4.1, we use a probabilistic argument to show an upper bound on the separation dimension of a rank-$r$ hypergraph based on its size. This is followed by an upper bound based on maximum degree in Sect. 4.2. We get this upper bound as a consequence of a non-trivial result in the area of boxicity. In Sect. 4.3, we prove a lower bound on the separation dimension of a complete $r$-uniform hypergraph by extending the lower bounding technique used in the context of graphs. Finally, in Sect. 5, we conclude with a discussion of a few open problems that we find interesting.

1.2 Notational Note

A hypergraph $H$ is a pair $(V, E)$ where $V$, called the vertex set, is any set and $E$, called the edge set, is a collection of subsets of $V$. The vertex set and edge set of a hypergraph $H$ are denoted respectively by $V(H)$ and $E(H)$. The rank of a hypergraph $H$ is $\max _{e \in E(H)}|e|$ and $H$ is called $k$ -uniform if $|e| = k, \forall e \in E(H)$. The degree of a vertex $v$ in $H$ is the number of edges of $H$ which contain $v$. The maximum degree of $H$, denoted as $\varDelta (H)$ is the maximum degree over all vertices of $H$. All the hypergraphs considered in this paper are finite.

A graph is a $2$-uniform hypergraph. For a graph $G$ and any $S \subseteq V(G)$, the subgraph of $G$ induced by the vertex set $S$ is denoted by $G[S]$. For any $v \in V(G)$, we use $N_G(v)$ to denote the neighbourhood of $v$ in $G$, i.e., $N_G(v) = \{u \in V(G) : \{v,u\} \in E(G)\}$.

A closed interval on the real line, denoted as $[i,j]$ where $i,j \in \mathbb {R}$ and $i\le j$, is the set $\{x\in \mathbb {R}: i\le x\le j\}$. Given an interval $X=[i,j]$, define $l(X)=i$ and $r(X)=j$. We say that the closed interval $X$ has left end-point $l(X)$ and right end-point $r(X)$. For any two intervals $[i_1, j_1], [i_2,j_2]$ on the real line, we say that $[i_1, j_1] < [i_2,j_2]$ if $j_1 < i_2$.

For any finite positive integer $n$, we shall use $[n]$ to denote the set $\{1,\ldots , n\}$. A permutation of a finite set $V$ is a bijection from $V$ to $[|V|]$. The logarithm of any positive real number $x$ to the base $2$ and $e$ are respectively denoted by $\log (x)$ and $\ln (x)$.

2 Pairwise Suitable Family of Permutations and a Box Representation

In this section we show that a family of permutations of cardinality $k$ is pairwise suitable for a hypergraph $H$ (Definition 1) if and only if the line graph of $H$ has a $k$-box representation (Definition 2). Before we proceed to prove it, let us state an equivalent but more combinatorial definition for boxicity.

Lemma 3

(Roberts [20]). For every graph $G$, $\mathrm{boxicity}(G) \le k$ if and only if there exist $k$ interval graphs $I_1, \ldots , I_k$, with $V(I_1) = \cdots = V(I_k) = V(G)$ such that $G = I_1 \cap \cdots \cap I_k$.

From the above lemma, we get an equivalent definition of boxicity.

Definition 4

The boxicity of a graph $G$ is the minimum positive integer $k$ for which there exist $k$ interval graphs $I_1,\ldots , I_k$ such that $G = I_1 \cap \cdots \cap I_k$.

Note that if $G = I_1 \cap \cdots \cap I_k$, then each $I_i$ is a supergraph of $G$. Moreover, for every pair of vertices $u,v \in V(G)$ with $\{u,v\} \notin E(G)$, there exists some $i \in [k]$ such that $\{u,v\} \notin E(I_i)$. Now we are ready to prove the main theorem of this section.

Theorem 5

For a hypergraph $H$, $\pi (H) = \mathrm{boxicity}(L(H))$.

Proof

First we show that $\pi (H) \le \mathrm{boxicity}(L(H))$. Let $\mathrm{boxicity}(L(H)) = b$. Then, by Lemma 3, there exists a collection of $b$ interval graphs, say $\mathcal {I} = \{I_1, \ldots , I_b\}$, whose intersection is $L(H)$. For each $i \in [b]$, let $f_i$ be an interval representation of $I_i$. For each $u \in V(H)$, let $E_H(u) = \{e \in E(H) : u \in e\}$ be the set of edges of $H$ containing $u$. Consider an $i \in [b]$ and a vertex $u \in V(H)$. The closed interval $C_i(u) = \bigcap _{e \in E_H(u)} f_i(e)$ is called the clique region of $u$ in $f_i$. Since any two edges in $E_H(u)$ are adjacent in $L(H)$, the corresponding intervals have non-empty intersection in $f_i$. By the Helly property of intervals, $C_i(u)$ is non-empty. We define a permutation $\sigma _i$ of $V(H)$ from $f_i$ such that $\forall u,v \in V(H)$, $C_i(u) < C_i(v) \implies u \prec _{\sigma _i} v$. It suffices to prove that $\{\sigma _1, \ldots , \sigma _b\}$ is a family of permutations that is pairwise suitable for $H$.

Consider two disjoint edges $e, e'$ in $H$. Hence $\{e, e' \} \notin E(L(H))$ and since $L(H) = \bigcap _{i=1}^b I_i$, there exists an interval graph, say $I_i \in \mathcal {I}$, such that $\{e, e'\} \notin E(I_i)$, i.e., $f_i(e) \cap f_i(e') = \emptyset$. Without loss of generality, assume $f_i(e) < f_i(e')$. For any $v \in e$ and any $v' \in e'$, since $C_i(v) \subseteq f_i(e)$ and $C_i(v') \subseteq f(e')$, we have $C_i(v) < C_i(v')$, i.e. $v \prec _{\sigma _i} v'$. Hence $e \prec _{\sigma _i} e'$. Thus the family $\{ \sigma _1, \ldots , \sigma _b \}$ of permutations is pairwise suitable for $H$.

Next we show that $\mathrm{boxicity}(L(H)) \le \pi (H)$. Let $\pi (H) = p$ and let $\mathcal {F}= \{\sigma _1, \ldots , \sigma _p\}$ be a pairwise suitable family of permutations for $H$. From each permutation $\sigma _i$, we shall construct an interval graph $I_i$ such that $L(H) = \bigcap _{i=1}^{p}I_i$. Then by Lemma 3, $\mathrm{boxicity}(L(H)) \le \pi (H)$.

For a given $i \in [p]$, to each edge $e \in E(H)$, we associate the closed interval

$$f_i(e) = \left[ \min _{v \in e}\sigma _i(v) ~,~ \max _{v \in e}\sigma _i(v) \right] ,$$

and let $I_i$ be the intersection graph of the intervals $f_i(e), e \in E(H)$. Let $e, e' \in V(L(H))$. If $e$ and $e'$ are adjacent in $L(H)$, let $v \in e \cap e'$. Then $\sigma _i(v) \in f_i(e) \cap f_i(e'),~\forall i \in [p]$. Hence $e$ and $e'$ are adjacent in $I_i$ for every $i \in [p]$. If $e$ and $e'$ are not adjacent in $L(H)$, then there is a permutation $\sigma _i \in \mathcal {F}$ such that either $e \prec _{\sigma _i} e'$ or $e' \prec _{\sigma _i} e$. Hence by construction $f_i(e) \cap f_i(e') = \emptyset$ and so $e$ and $e'$ are not adjacent in $I_i$. This completes the proof.    $\square$

3 Separation Dimension of Graphs

3.1 Characterizing Graphs of Separation Dimension $1$

“When is $\pi (G)=0$?” Clearly, if $\pi (G) = 0$, then $G$ may have at most one non-trivial connected component and every pair of edges must share an endpoint. The following is a simple exercise answering the question:

Proposition 6

For a graph $G$, $\pi (G)=0$ if and only if $G$ has at most one connected component of size greater than one and this component is either a clique of size at most 3 or a star.

A caterpillar is a tree consisting of a chordless path $[v_1,v_2,\ldots ,v_k]$ called the spine, plus an unlimited number of pendant vertices. A caterpillar with single humps is formed from a caterpillar by adding at most one new vertex $x_i$ adjacent to $v_i$ and $v_{i+1}$ for every $i=1,\ldots , k-1$. Without loss of generality, we may assume that the first and last vertex of the spine have no pendent vertices (i.e., the spine is longest possible.) The diamond, denoted here by $D$, is the graph with 4 vertices and 5 edges; the 3-net $N_3$ consists of a triangle with a pendant vertex attached to each of its vertices; the graph $T_2$ is the tree with 6 edges $\{cx,cy,cz,xx',yy',zz'\}$; and the graph $C_k$ ($k\ge 4$) denotes the cycle of size $k$.

Theorem 7

Let $G$ be a graph. The following conditions are equivalent:

• (i) $\pi (G) \le 1$,

• (ii) $G$ is a disjoint union of caterpillars with single humps,

• (iii) $G$ has no partial subgraph $C_k$ ($k\ge 4$), $N_3$ or $T_2$,

• (iv) $G$ is a chordal graph with no induced subgraph $D$, $K_4$, $T_2$, $N_3$, $G_1$, $G_2$ or $G_3$, where $G_1 = T_2 \cup \{cx'\}$, $G_2 = G_1 \cup \{cy'\}$ and $G_3 = G_2 \cup \{cz'\}$,

• (v) The line graph $L(G)$ is an interval graph.

The proof of Theorem 7 suggests a linear time algorithm for recognizing whether a graph $G$ has separation dimension 1 and constructing its representation as a caterpillar with single humps: (1) Using either Lexicographic Breadth First Search or Maximum Cardinality Search, obtain an ordering of the vertices $a_1, a_2,\ldots ,a_n$ (but do not bother to test whether it is a perfect elimination ordering²; (2) Starting with $a_n$ and proceeding in reverse order, follow the rules in the proof of $(iii)\Rightarrow (ii)$ to construct the spine, pendant vertices and the humps. If either (1) or (2) fails, then $\pi (G) > 1$.

3.2 Separation Dimension and the Size of a Graph

For graphs, sometimes we work with a notion of suitability that is stronger than the pairwise suitability of Definition 1. This will come in handy in proving certain results later in this article.

Definition 8

For a graph $G$, a family $\mathcal {F}$ of permutations of $G$ is $3$ -mixing if, for every two adjacent edges $\{a,b\}, \{a,c\} \in E(G)$, there exists a permutation $\sigma \in \mathcal {F}$ such that either $b \prec _{\sigma } a \prec _{\sigma } c$ or $c \prec _{\sigma } a \prec _{\sigma } b$.

Notice that a family of permutations $\mathcal {F}$ of $V(G)$ is pairwise suitable and $3$-mixing for $G$ if, for every two edges $e,f \in E(G)$, there exists a permutation $\sigma \in \mathcal {F}$ such that either $e \preceq _{\sigma } f$ or $f \preceq _{\sigma } e$. Let $\pi ^{\star }(G)$ denote the cardinality of a smallest family of permutations that is pairwise suitable and $3$-mixing for $G$. From their definitions, $\pi (G) \le \pi ^{\star }(G)$.

Observation 9

$\pi (G)$ and $\pi ^{\star }(G)$ are monotone increasing properties.

The following theorem is the special case of Theorem 25 when the rank-$r$ hypergraph under consideration is a graph. Theorem 25 yields a bound of $\pi (G) \le 9.596 \log n$.

Theorem 10

For a graph $G$ on $n$ vertices, $\pi (G) \le \pi ^{\star }(G) \le 6.84 \log n$.

Proof

From the definitions of $\pi (G)$ and $\pi ^{\star }(G)$ and Observation 9, we have $\pi (G) \le \pi ^{\star }(G) \le \pi ^{\star }(K_n)$, where $K_n$ denotes the complete graph on $n$ vertices. Here we prove that $\pi ^{\star }(K_n) \le 6.84 \log n$.

Choose $r$ permutations, $\sigma _1, \ldots , \sigma _r$, independently and uniformly at random from the $n!$ distinct permutations of $[n]$. Let $e$, $f$ be two distinct edges of $K_n$. The probability that $e \preceq _{\sigma _i} f$ is $1/6$, for each $i \in [r]$. ($4$ out of $4!$ outcomes are favourable when $e$ and $f$ are non-adjacent and $1$ out of $3!$ outcomes is favourable otherwise.) Therefore, the probability that $e \preceq _{\sigma _i} f$ or $f \preceq _{\sigma _i} e$ is $1/3$. Let $B(e,f)$ denote the “bad” event of $e \npreceq _{\sigma _i} f$ and $f \npreceq _{\sigma _i} e$ for all $i \in [r]$. Then, $Pr[B(e,f)] = (2/3)^r$. Taking union bound over all distinct pairs of edges $e$ and $f$, we get

$$\begin{aligned} Pr[\bigcup _{\forall \text{ pairs } \text{ of } \text{ distinct } \text{ edges } e,f}B(e,f)] < n^4 \left( \frac{2}{3}\right) ^r \end{aligned}$$

When $r = 6.84\log n$, the left hand side of the above inequality is a quantity less than $1$. That is, there exists a family of permutations of $V(K_n)$ of cardinality at most $6.84\log n$ which is pairwise suitable and $3$ mixing for $K_n$.    $\square$

Tightness of Theorem 10 . Let $K_n$ denote a complete graph on $n$ vertices. Since $\omega (K_n) = n$, it follows from Corollary 21 that $\pi (K_n) \ge \log \left\lfloor n/2 \right\rfloor$. Hence the bound proved in Theorem 10 is tight up to a constant factor.

3.3 Acyclic and Star Chromatic Number

Definition 11

The acyclic chromatic number of a graph $G$, denoted by $\chi _a(G)$, is the minimum number of colours needed to do a proper colouring of the vertices of $G$ such that the graph induced on the vertices of every pair of colour classes is acyclic. The star chromatic number of a graph $G$, denoted by $\chi _s(G)$, is the minimum number of colours needed to do a proper colouring of the vertices of $G$ such that the graph induced on the vertices of every pair of colour classes is a star forest.

We know that that a star forest is a disjoint union of stars. Therefore, $\chi _s(G) \ge \chi _a(G) \ge \chi (G)$, where $\chi (G)$ denotes the chromatic number of $G$. In order to bound $\pi (G)$ in terms of $\chi _a(G)$ and $\chi _s(G)$, we first bound $\pi (G)$ for forests and star forests. Then the required result follows from an application of Lemma 14.

Since forests are outerplanar graphs, the following lemma follows directly from the discussion on outerplanar graphs in Sect. 3.4.

Lemma 12

For a forest $G$, $\pi (G) \le 2$.

Lemma 13

For a star forest $G$, $\pi (G) = 1$.

Proof

Follows directly from Theorem 7.    $\square$

Lemma 14

Let $P_G=\{V_1, \ldots , V_r\}$ be a partitioning of the vertices of a graph $G$, i.e., $V(G) = V_1 \uplus \cdots \uplus V_r$. Let $\hat{\pi }(P_G) = \max _{i,j \in [r]} \pi (G[V_i \cup V_j])$. Then, $\pi (G) \le 13.68 \log r + \hat{\pi }(P_G) r$.

Theorem 15

For a graph $G$, $\pi (G) \le 2\chi _a(G) + 13.68\log (\chi _a(G))$. Further, $\pi (G) \le \chi _s(G) + 13.68\log (\chi _s(G))$.

Proof

The theorem follows directly from Lemmas 12, 13, and 14.    $\square$

This, together with some existing results from literature, gives us a few easy corollaries. Alon, Mohar, and Sanders have showed that a graph embeddable in a surface of Euler genus $g$ has an acyclic chromatic number in $O(g^{4/7})$ [5]. It is noted by Esperet and Joret in [17], using results of Nesetril, Ossona de Mendez, Kostochka, and Thomassen, that graphs with no $K_t$ minor have an acyclic chromatic number in $O\left( t^2 \log t \right)$. Hence the following corollary.

Corollary 16

• (i) For a graph $G$ with Euler genus $g$, $\pi (G) \in O(g^{4/7})$; and

• (ii) for a graph $G$ with no $K_t$ minor, $\pi (G) \in O(t^2 \log t)$.

3.4 Planar Graphs

Since planar graphs have acyclic chromatic number at most $5$ [9], it follows from Theorem 15 that, for every planar graph $G$, $\pi (G) \le 42$. Using Schnyder’s celebrated result on non-crossing straight line plane drawings of planar graphs we improve this bound to the best possible.

Theorem 17

(Schnyder, Theorem 1.1 in [22]). Let $\lambda _1$, $\lambda _2$, $\lambda _3$ be three pairwise non-parallel straight lines in the plane. Then, each plane graph has a straight line embedding in which any two disjoint edges are separated by a straight line parallel to $\lambda _1$, $\lambda _2$ or $\lambda _3$.

This immediately gives us the following tight bound for planar graphs.

Theorem 18

Separation dimension of a planar graph is at most $3$. Moreover there exist planar graphs with separation dimension $3$.

Outerplanar and Series-Parallel Graphs. We know that outerplanar graphs form a subclass of series-parallel graphs which in turn form a subclass of planar graphs. It is not difficult to see that the separation dimension of outerplanar graphs is at most $2$. The idea is to take one permutation by reading the vertices from left to right along the spine in a one page embedding of the graph and the second permutation in the order in which we see the vertices when we recursively peel off the outermost edge till every vertex is enlisted. As for series-parallel graphs, we know of series-parallel graphs that require separation dimension $3$.

3.5 Lower Bounds

The tightness of many of the upper bounds we showed in the previous section relies on the lower bounds we derive in this section. First, we show that if a graph contains a uniform bipartite subgraph, then it needs a large separation dimension. This immediately gives a lower bound on separation dimension for complete bipartite graphs and hence a lower bound for every graph $G$ in terms $\omega (G)$. The same is used to obtain a lower bound on the separation dimension for random graphs of all density. Finally, it is used as a critical ingredient in proving a lower bound on the separation dimension for complete $r$-uniform hypergraphs.

Theorem 19

For a graph $G$, let $V_1, V_2 \subsetneq V(G)$ such that $V_1 \cap V_2 = \emptyset$. If there exists an edge between every $s_1$-subset of $V_1$ and every $s_2$-subset of $V_2$, then $\pi (G) \ge \min \left\{ \log \frac{|V_1|}{s_1}, \log \frac{|V_2|}{s_2} \right\}$.

The next two corollaries are immediate.

Corollary 20

For a complete bipartite graph $K_{m,n}$ with $m \le n$, $\pi (K_{m,n}) \ge \log (m)$.

Corollary 21

For a graph $G$, $\pi (G) \ge \log \left\lfloor \frac{\omega (G)}{2} \right\rfloor ,$ where $\omega (G)$ is the size of a largest clique in $G$.

3.6 Random Graphs

Definition 22

(Erdős-Rényi model). $\mathcal {G}(n,p)$, $n \in \mathbb {N}$ and $0 \le p \le 1$, is the discrete probability space of all simple undirected graphs $G$ on $n$ vertices with each pair of vertices of $G$ being joined by an edge with a probability $p$ independent of the choice for every other pair of vertices.

Definition 23

A property $P$ is said to hold for $\mathcal {G}(n,p)$ asymptotically almost surely (a.a.s) if the probability that $P$ holds for $G \in \mathcal {G}(n,p)$ tends to $1$ as $n$ tends to $\infty$.

Theorem 24

For $G \in \mathcal {G}(n,p(n))$

$$\pi (G) \ge \log (np(n)) - \log \log (np(n)) - 2.5 \text{ a.a.s }.$$

Note that the expected average degree of a graph in $\mathcal {G}(n,p)$ is $\mathbb {E}_p[\bar{d}] = (n-1)p$. And hence the above bound can be written as $\log \mathbb {E}_p[\bar{d}] - \log \log \mathbb {E}_p[\bar{d}] - 2.5$.

4 Separation Dimension of Hypergraphs

4.1 Separation Dimension and Size of a Hypergraph

Using a direct probabilistic argument similar to the one used in Theorem 10 we obtain the following theorem.

Theorem 25

For any rank-$r$ hypergraph $H$ on $n$ vertices

$$ \pi (H) \le \frac{e \ln 2}{\pi \sqrt{2}} 4^r \sqrt{r} \log n.$$

Tightness of Theorem 25 . Let $K_n^r$ denote a complete $r$-uniform graph on $n$ vertices. Then by Theorem 27, $\pi (K_n^r) \ge \frac{1}{2^7} \frac{4^r}{\sqrt{r-2}} \log n$ for $n$ sufficiently larger than $r$. Hence the bound in Theorem 25 is tight by factor of $64 r$.

4.2 Maximum Degree

Theorem 26

For any rank-$r$ hypergraph $H$ of maximum degree $D$, $\pi (H) \le O\left( rD \log ^2(rD) \right)$.

Proof

This is a direct consequence of the nontrivial fact that $\mathrm{boxicity}(G) \in O\left( \varDelta \log ^2 \varDelta \right)$ for any graph $G$ of maximum degree $\varDelta$ [1].    $\square$

It is known that there exist graphs of maximum degree $\varDelta$ whose boxicity can be as high as $c \varDelta \log \varDelta$ [1], where $c$ is a small positive constant. Let $G$ be one such graph. Consider the following hypergraph $H$ constructed from $G$. Let $V(H) = E(G)$ and $E(H) = \{E_v : v \in V(G)\}$ where $E_v$ is the set of edges incident on the vertex $v$ in $G$. It is clear that $G = L(H)$. Hence $\pi (H) = \mathrm{boxicity}(G) \ge c \varDelta (G) \log \varDelta (G)$. Note that the rank of $H$ is $r = \varDelta (G)$ and the maximum degree of $H$ is $2$. Thus $\pi (H) \ge c r \log (r)$ and hence the dependence on $r$ in the upper bound cannot be considerably brought down in general.

4.3 Lower Bound

Now we illustrate one method of extending the above lower bounding technique from graphs to hypergraphs. Let $K_n^r$ denote the complete $r$-uniform hypergraph on $n$ vertices. We show that the upper bound of $O\left( 4^r \sqrt{r} \log n \right)$ obtained for $K_n^r$ from Theorem 25 is tight up to a factor of $r$. The lower bound argument below is motivated by an argument used by Radhakrishnan to prove a lower bound on the size of a family of scrambling permutations [19]. From Corollary 21 we know that the separation dimension of $K_n$, the complete graph on $n$ vertices, is in $\varOmega \left( \log n \right)$. Below we show that given any separating embedding of $K_n^r$ in $\mathbb {R}^d$, the space $\mathbb {R}^d$ contains ${2r-4 \atopwithdelims ()r-2}$ orthogonal subspaces such that the projection of the given embedding on to these subspaces gives a separating embedding of a $K_{n-2r+4}$.

Theorem 27

Let $K_n^r$ denote the complete $r$-uniform hypergraph on $n$ vertices with $r > 2$. Then

$$ c_1 \frac{4^r}{\sqrt{r-2}} \log n \le \pi (K_n^r) \le c_2 4^r \sqrt{r} \log n,$$

for $n$ sufficiently larger than $r$ and where $c_1 = \frac{1}{2^7}$ and $c_2 = \frac{e\ln 2}{\pi \sqrt{2}} < \frac{1}{2}$.

5 Discussion and Open Problems

Since $\pi (G)$ is the boxicity of the line graph of $G$, it is interesting to see how it is related to boxicity of $G$ itself. But unlike separation dimension, boxicity is not a monotone parameter. For example the boxicity of $K_n$ is $1$, but deleting a perfect matching from $K_n$, if $n$ is even, blows up its boxicity to $n/2$. Yet we couldn’t find any graph $G$ such that $\mathrm{boxicity}(G) > 2^{\pi (G)}$. Hence we are curious about the following question: Does there exist a function $f : \mathbb {N} \rightarrow \mathbb {N}$ such that $\mathrm{boxicity}(G) \le f(\pi (G))$? Note that the analogous question for $\pi ^{\star }(G)$ has an affirmative answer. If there exists a vertex $v$ of degree $d$ in $G$, then any $3$-mixing family of permutations of $V(G)$ should contain at least $\log d$ different permutations because any single permutation will leave $\left\lceil d/2 \right\rceil$ neighbours of $v$ on the same side of $v$. Hence $\log \varDelta (G) \le \pi ^{\star }(G)$. From [1], we know that $\mathrm{boxicity}(G) \in O\left( \varDelta (G) \log ^2 \varDelta (G) \right)$ and hence $\mathrm{boxicity}(G) \in O\left( 2^{\pi ^{\star }(G)} (\pi ^{\star }(G))^2 \right)$.

Another interesting direction of enquiry is to find out the maximum number of hyperedges (edges) possible in a hypergraph (graph) $H$ on $n$ vertices with $\pi (H) \le k$. Such an extremal hypergraph $H$, with $\pi (H) \le 0$, is seen to be a maximum sized intersecting family of subsets of $[n]$. A similar question for order dimension of a graph has been studied [3, 4] and has found applications in ring theory. We can also ask a three dimensional analogue of the question answered by Schnyder’s theorem in two dimensions. Given a collection $P$ of non-parallel planes in $\mathbb {R}^3$, can we embed a graph $G$ in $\mathbb {R}^3$ so that every pair of disjoint edges is separated by a plane parallel to one in $P$. Then $|P|$ has to be at least $\pi (G)$ for this to be possible. This is because the permutations induced by projecting such an embedding onto the normals to the planes in $P$ gives a pairwise suitable family of permutations of $G$ of size $|P|$. Can $|P|$ be upper bounded by a function of $\pi (G)$?

We know that Theorem 7 yields a linear time algorithm for recognizing graphs of separation dimension at most $1$. This gives rise to a very natural question. Is it possible to recognize graphs of separation dimension at most $2$ in polynomial time?