Let $n>1$ be an integer. Given a simple graph $G$ on $n$ vertices $v_1, v_2, \dots, v_n$ we let $k(G)$ be the minimal value of $k$ for which there exist $n$ $k$-dimensional rectangular boxes $R_1, R_2, \dots, R_n$ in a $k$-dimensional coordinate system with edges parallel to the axes, so that for each $1\leq i<j\leq n$, $R_i$ and $R_j$ intersect if and only if there is an edge between $v_i$ and $v_j$ in $G$. Define $M$ to be the maximal value of $k(G)$ over all graphs on $n$ vertices. Calculate $M$ as a function of $n$.
Problem
Source: 2024 Israel TST Test 1 P2
Tags: TST, combinatorics, graph theory, analytic geometry
cadaeibf
29.08.2023 13:26
We will prove that the maximum is $M_n=\lfloor n/2\rfloor$. If $n=2k$, consider the graph $G_n$ with vertices $\{1,...,2n\}$, where $(i,j)$ is an edge iff $i+n\not\equiv j\pmod 2n$. Considering the boxes $R_n$ and $R_{2n}$, they don't intersect, and thus there is at least on direction (parallel to one of the axes) along which their projection doesn't intersect. Calling $\pi_j:\mathbb{R}^n\to \mathbb{R}$ the projection along this $j$-th direction and $\psi_j:\mathbb{R}^n\to \mathbb{R}^{n-1}$ the projection along the other coordinates, we have that $\pi_j(R_n)$ and $\pi_j(R_{2n})$ are two disjoint intervals (say $[a,b]$ and $[c,d]$ with $a<b<c<d$. Since all others boxes intersect these two boxes, it follows that for all other $i$s $[b,c]\subseteq\pi_j(R_i)$. So, of the other boxes, two of them intersect if and only if their projections $\psi_j$ intersect. Since $G_n$ without two nonadjacent vertices is isomorphic to $G_{n-1}$ it follows that $k(G_n)\geq k(G_{n-1})+1$ for $n\geq 1$. Therefore, since $k(G_1)$ is trivially $1$, it follows that $M_{2n+1}\geq M_{2n}\geq k(G_n)\geq n=\lfloor(2n+1)/2\rfloor=\lfloor (2n)/2\rfloor$. To prove that it can be done in $\lfloor n/2\rfloor$, we do something similar. If $G$ is a complete graph, just take every box to be equal. Otherwise, there exists at least a pair of non adjacent vertices, which we map to two disjoint boxes with a parallel face (of codimension $1$) for the other vertices the graph restricted to those $n-2$ vertices can be built in $\lfloor(n-2)/2\rfloor=\lfloor n/2\rfloor -1$ dimensions (and wlog those boxes are all bound by the face we're taking) so we will take the the product of this boxes with some intervals, in such a way that those intervals intersect the two new boxes if and only if there is an edge in the graph. It is easy to see that this can be done, and allows us to finish. Of course we also have to check the two base cases $n=2$ and $n=3$, which can be done in $1$ dimension [note that if we said $\mathbb{R}^0=\{0\}$ this could also have been done for $n=1$ and $n=0$].