text:
\section{Eigenvalue Behavior}
\label{sec:Results}

\subsection{Prior results on DPSS eigenvalues}
\label{sec:PrevDPSSBounds}
Showing that the DPSS eigenvalues are strictly between $0$ and $1$ is a trivial consequence of the facts that $\lambda_k = \left(\int_{-W}^{W}|\widehat{s}_k(f)|^2\,df\right)/\left(\int_{-1/2}^{1/2}|\widehat{s}_k(f)|^2\,df\right)$ and that $\widehat{\vs}_k(f)$ is a non-zero analytic function. It is also easy to check that the sum of all the DPSS eigenvalues is $\sum_{k = 0}^{N-1}\lambda_k = \trace(\mB) = 2NW$. What is perhaps more interesting is that the DPSS eigenvalues obey a particular clustering behavior. For any $\eps \in (0,\tfrac{1}{2})$, slightly fewer than $2NW$ eigenvalues lie in $[1-\eps,1)$, slightly fewer than $N-2NW$ eigenvalues lie in $(0,\eps]$, and very few eigenvalues lie in the transition region $(\eps,1-\eps)$. In Figure 1, we demonstrate this phenomenon by plotting the DPSS eigenvalues for $N = 1000$ and $W = \tfrac{1}{8}$ (so $2NW = 250$). The first $244$ eigenvalues lie in $[0.999,1)$ and the last $744$ eigenvalues lie in $(0,0.001]$. Only $12$ eigenvalues lie between $0.001$ and $0.999$.

\begin{figure}
\label{fig:EigenvaluePlot}
\centering
\includegraphics[scale=0.35]{EigenvaluePlot_V2.png}
\caption{A plot of the DPSS Eigenvalues $\{\lambda_k\}_{k = 0}^{N-1}$ for $N = 1000$ and $W = \tfrac{1}{8}$. These eigenvalues satisfy $\lambda_{243} \approx 0.9997$ and $\lambda_{256} \approx 0.0003$. Only $12$ of the $1000$ DPSS eigenvalues lie in $(0.001,0.999)$.}
\end{figure}

Experimentally, we can see that the width of this transition region behaves like $\#\{k : \eps < \lambda_k < 1-\eps\} = O(\log(NW) \log(\tfrac{1}{\eps}))$. This can be seen in Figures~\ref{fig:GapsizeVsN} and \ref{fig:GapsizeVsW} in Section~\ref{sec:NumericalResults}. Our main contribution will be to demonstrate this analytically, but before we do, we will briefly review some of the prior results along these lines.

We begin with the original results from Slepian \cite{SlepianV}. For any fixed $W \in (0,\tfrac{1}{2})$ and $b \in \R$, $$\lambda_{\floor{2NW+(b/\pi)\log N}} \sim \dfrac{1}{1+e^{b\pi}} \quad \text{as} \quad N \to \infty.$$ From this result, it is easy to show that for any fixed $W \in (0,\tfrac{1}{2})$ and $\eps \in (0,\tfrac{1}{2})$, $$\#\{k : \eps < \lambda_k < 1-\eps\} \sim \dfrac{2}{\pi^2}\log N \log\left(\dfrac{1}{\eps}-1\right) \quad \text{as} \quad N \to \infty.$$ This asymptotic bound on the width of the transition region correctly captures the logarithmic dependence on both $N$ and $\eps$, but not the dependence on $W$. Slepian also stated that if $0.2 < \lambda_k < 0.8$, then $$\lambda_k \approx \left[1+\exp\left(-\dfrac{\pi^2(2NW-k-\tfrac{1}{2})}{\log[8N\sin(2\pi W)]+\gamma}\right)\right]^{-1}$$ is a good approximation to $\lambda_k$ where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant. This would suggest that $$\#\{k : \eps < \lambda_k < 1-\eps\} \approx \dfrac{2}{\pi^2}\log\left[8e^{\gamma}N\sin(2\pi W)\right]\log\left(\dfrac{1}{\eps}-1\right)$$ for $\eps \in (0.2,0.5)$. This correctly captures the logarithmic dependence on $N$, $W$, and $\eps$, but only holds for large values of $\eps$.

Very few papers provide non-asymptotic bounds regarding the width of the transition region $\#\{k : \eps < \lambda_k < 1-\eps\}$. Zhu and Wakin \cite{ZhuWakin15} showed that
\begin{equation}
\#\{k : \eps \le \lambda_k \le 1-\eps\} \le \dfrac{\tfrac{2}{\pi^2}\log(N-1) + \tfrac{2}{\pi^2}\tfrac{2N-1}{N-1}}{\eps(1-\eps)}
\label{eq:ZhuWakin}
\end{equation}
for all integers $N \ge 2$, $W \in (0,\tfrac{1}{2})$, and $\eps \in (0,\tfrac{1}{2})$. This non-asymptotic bound correctly highlights the logarithmic dependence on $N$, but fails to capture the dependence on $W$. Also, the dependence on $\eps$ is $O(\tfrac{1}{\eps})$ as opposed to $O(\log \tfrac{1}{\eps})$. When $\eps$ is small, this bound is considerably worse than a $O(\log \tfrac{1}{\eps})$ bound. For example, when $N = 1000$, $W = \tfrac{1}{8}$, and $\eps = 10^{-3}$, this result becomes $\#\{k : \eps < \lambda_k < 1-\eps\} \le 1806$. More generally, when $\eps < \tfrac{2\log(N-1)}{\pi^2N}$, this bound is worse than the trivial bound of $\#\{k : \eps < \lambda_k < 1-\eps\} \le N$.

Recently, Boulsane, Bourguiba, and Karoui \cite{Boulsane20} improved this bound to
\begin{equation}
\#\{k : \eps \le \lambda_k \le 1-\eps\} \le \dfrac{\tfrac{1}{\pi^2}\log(2NW) + 0.45 - \tfrac{2}{3}W^2 + \tfrac{\sin^2(2\pi NW)}{6\pi^2N^2}}{\eps(1-\eps)}
\label{eq:Boulsane}
\end{equation}
for all integers $N \ge 1$, $W \in (0,\tfrac{1}{2})$, and $\eps \in (0,\tfrac{1}{2})$. For a fixed $W \in (0,\tfrac{1}{2})$ and large $N$, this bound is roughly half of (\ref{eq:ZhuWakin}). Also, this bound correctly captures the logarithmic dependence on $2NW$ as opposed to just $N$. However, this bound still has a dependence on $\eps$ that is $O(\tfrac{1}{\eps})$. Again, when $N = 1000$, $W = \tfrac{1}{8}$, and $\eps = 10^{-3}$, this result becomes $\#\{k : \eps < \lambda_k < 1-\eps\} \le 1000$. More generally, when $\eps < \tfrac{\log(2NW)}{\pi^2N}$, this bound is worse than the trivial bound of $\#\{k : \eps < \lambda_k < 1-\eps\} \le N$. Boulsane et. al. also used to a result on PSWF eigenvalues by Bonami, Jamming, and Karoui \cite{Bonami18} to prove that the DPSS eigenvalues satisfy
\begin{equation}
\lambda_k \le 2\exp\left[-\eta\dfrac{k-2NW}{\log(\pi NW)+5}\right] \quad \text{for} \quad 2NW+\log(\pi NW)+6 \le k \le \pi NW,
\label{eq:Boulsane1}
\end{equation}
where $\eta = 0.069$, and
\begin{equation}
\lambda_k \le 2\exp\left[-(2k+1)\log\left(\dfrac{2k+2}{e\pi NW}\right)\right] \quad \text{for} \quad 2 \le \dfrac{e\pi}{2}NW \le k \le N-1.
\label{eq:Boulsane2}
\end{equation}
However, with no similar lower bounds on the DPSS eigenvalues $\lambda_k$ for $k < 2NW$, they were unable to obtain a bound on $\#\{k : \eps < \lambda_k < 1-\eps\}$ which has a logarithmic dependence on $\eps$.

In \cite{KarnikFST}, the authors of this paper along with Zhu and Wakin proved that
\begin{equation}
\#\{k : \eps < \lambda_k < 1-\eps\} \le \left(\dfrac{8}{\pi^2}\log(8N)+12\right)\log\left(\dfrac{15}{\eps}\right)
\label{eq:FST}
\end{equation}
for all $N \in \N$, $W \in (0,\tfrac{1}{2})$, and $\eps \in (0,\tfrac{1}{2})$.  This bound correctly captures the logarithmic dependence on both $N$ and $\eps$, but not the dependence on $W$. Also, the leading constant $\tfrac{8}{\pi^2}$ is four times larger than that of the asymptotic results by Slepian. For comparison with the previous two non-asymptotic bounds, when $N = 1000$, $W = \tfrac{1}{8}$, and $\eps = 10^{-3}$, then this result becomes $\#\{k : \eps < \lambda_k < 1-\eps\} \le 185$, which is still much larger than the actual value of $\#\{k : \eps < \lambda_k < 1-\eps\} = 12$.

\subsection{Prior results on PSWF eigenvalues}
\label{sec:PrevPSWFBounds}
The PSWF eigenvalues $\widetilde{\lambda}_k$ have a similar behavior as the DPSS eigenvalues. The PSWF eigenvalues are also all strictly between $0$ and $1$, and they have a sum of $\sum_{k = 0}^{\infty}\widetilde{\lambda}_k = \tfrac{2c}{\pi}$, which is the analogous time-bandwidth product in the continuous case. Furthermore, for any $\eps \in (0,\tfrac{1}{2})$, slightly fewer than $\tfrac{2c}{\pi}$ eigenvalues lie in $[1-\eps,1)$, very few eigenvalues lie in $(\eps,1-\eps)$, and the rest lie in $(0,\eps]$.

Landau and Widom \cite{LandauWidom80} showed that for any fixed $\eps \in (0,\tfrac{1}{2})$, $$\#\left\{k : \eps < \widetilde{\lambda}_k < 1-\eps\right\} = \dfrac{2}{\pi^2}\log(c)\log\left(\dfrac{1}{\eps}-1\right)+o(\log(c)) \quad \text{as} \quad c \to \infty.$$ This asymptotic result is similar in form to Slepian's result from \cite{SlepianV}, except the first logarithm contains the time-bandwidth product instead of the time duration. Also, this result specifies that the error term scales like $o(\log(c))$.

Osipov \cite{Osipov13} showed that for any numbers $c > 22$ and $3 < \delta < \tfrac{\pi c}{16}$, the PSWF eigenvalues satisfy $$\widetilde{\lambda}_k < \dfrac{7056^2c^3}{2\pi}\exp\left[-2\delta\left(1-\dfrac{\delta}{2\pi c}\right)\right] \quad \text{for all} \quad k \ge \dfrac{2c}{\pi}+\dfrac{2}{\pi^2}\delta\log\left(\dfrac{4\pi ec}{\delta}\right).$$ With an appropriate choice of $\delta$, this result implies that $$\#\left\{k : \widetilde{\lambda}_k > \eps\right\} \le \dfrac{2c}{\pi}+\dfrac{32}{31\pi^2}\log\left(\dfrac{7056^2c^3}{2\pi \eps}\right)\log\left(\dfrac{31\pi ec}{4\log\left(\tfrac{7056^2c^3}{2\pi \eps}\right)}\right) \quad \text{for} \quad \dfrac{7056^2c^3}{2\pi}\exp\left(-\dfrac{31\pi c}{256}\right) < \eps < \dfrac{1}{2}.$$ Since Landau \cite{Landau93} showed that $\widetilde{\lambda}_{\floor{2c/\pi}-1} \ge \tfrac{1}{2}$, the above result by Osipov shows that $\#\left\{k : \eps < \widetilde{\lambda}_k \le \tfrac{1}{2}\right\} \le O(\log^2(c)+\log(c)\log(\tfrac{1}{\eps}))$. This only bounds roughly half of the transition region. Also, the bound has a suboptimal dependence on $c$, and the constants are rather large.

Israel \cite{Israel15} showed that for any $\alpha \in (0,\tfrac{1}{2}]$, there exists a constant $C_{\alpha} \ge 1$ such that $$\#\left\{k : \eps < \widetilde{\lambda}_k < 1-\eps\right\} \le C_{\alpha}\log^{1+\alpha}\left(\dfrac{\log\left(\tfrac{2c}{\pi}\right)}{\eps}\right)\log\left(\dfrac{2c}{\pi\eps}\right)$$ for all $c \ge \pi$ and $\eps \in (0,\tfrac{1}{2})$. When compared to the bound by Osipov, this bound has an improved dependence on $c$, but a worse dependence on $\eps$. Also, the constant $C_{\alpha}$ is not explicitly given.

Bonami, Jamming, and Karoui \cite{Bonami18} established the following bounds on PSWF eigenvalues
\\
$$\widetilde{\lambda}_k \ge 1-\dfrac{7}{\sqrt{c}}\dfrac{(2c)^k}{k!}e^{-c} \quad \text{for} \quad c > 0 \ \text{and} \ 0 \le k < \dfrac{2c}{2.7}$$

$$\widetilde{\lambda}_k \le \dfrac{1}{2}\exp\left[-\eta\dfrac{k-\tfrac{2c}{\pi}}{\log(c)+5}\right] \quad \text{for} \quad c \ge 22 \ \text{and} \ \dfrac{2c}{\pi}+\log(c)+6 \le k \le c$$

$$\widetilde{\lambda}_k \le \exp\left[-(2k+1)\log\left(\dfrac{2k+2}{ec}\right)\right] \quad \text{for} \quad c > 0 \ \text{and} \ k \ge \max\left(\dfrac{ec}{2},2\right),$$
\\
where $\eta = 0.069$. The first bound shows that $\widetilde{\lambda}_k$ approaches $1$ as $k$ decreases at a faster than exponential rate.  The second bound shows that $\widetilde{\lambda}_k$ decreases exponentially over a bounded range of values of $k$ that are slightly greater than the time-bandwidth product $\tfrac{2c}{\pi}$. The third bound shows that $\widetilde{\lambda}_k$ approaches $0$ a faster than exponential rate once $k > \max(\tfrac{ec}{2},2)$. Unfortunately, one can check that for any $c > 0$ and any integer $0.43c \le k < \tfrac{2c}{2.7}$, the first bound is negative, and thus, uninformative. Thus, these bounds give no information about $\widetilde{\lambda}_k$ for $k \in [0.43c,\tfrac{2c}{\pi}+\log(c)+6) \cup (c,\tfrac{ec}{2})$, which is a total of $O(c)$ values of $k$.

\subsection{New results}
\label{sec:NewResults}
In this paper, we will establish the following two non-asymptotic bounds on the number of DPSS eigenvalues in the transition region $(\eps,1-\eps)$.

\begin{theorem}
\label{thm:BoundWithoutW}
For any $N \in \N$, $W \in (0,\tfrac{1}{2})$, and $\eps \in (0,\tfrac{1}{2})$,  $$\#\{k : \eps < \lambda_k < 1-\eps \} \le 2\ceil{\dfrac{1}{\pi^2}\log(4N)\log\left(\dfrac{4}{\eps(1-\eps)}\right)}.$$
\end{theorem}

\begin{theorem}
\label{thm:BoundWithW}
For any $N \in \N$, $W \in (0,\tfrac{1}{2})$, and $\eps \in (0,\tfrac{1}{2})$,  $$\#\{k : \eps < \lambda_k < 1-\eps\} \le \dfrac{2}{\pi^2}\log(100NW+25)\log\left(\dfrac{5}{\eps(1-\eps)}\right) + 7.$$
\end{theorem}

Both Theorem~\ref{thm:BoundWithoutW} and Theorem~\ref{thm:BoundWithW} capture the logarithmic dependence of the width of the transition region on $N$ and $\eps$. Also, both bounds have a leading constant of $\tfrac{2}{\pi^2}$, which is consistent with the asymptotic result by Slepian. Furthermore, Theorem~\ref{thm:BoundWithW} also captures the logarithmic dependence on $W$. We choose to include Theorem~\ref{thm:BoundWithoutW} since the proof is much simpler and since the bound in Theorem~\ref{thm:BoundWithoutW} is better than the bound in Theorem~\ref{thm:BoundWithW} when $W \ge \tfrac{1}{25}$. Again for comparison with the existing non-asymptotic bounds, when $N = 1000$, $W = \tfrac{1}{8}$, and $\eps = 10^{-3}$, the bound in Theorem~\ref{thm:BoundWithoutW} becomes $\#\{k : \eps < \lambda_k < 1-\eps\} \le 14$ and the bound in Theorem~\ref{thm:BoundWithW} becomes $\#\{k : \eps < \lambda_k < 1-\eps\} \le 23$. Both of these bounds are much closer to the actual value $\#\{k : \eps < \lambda_k < 1-\eps\} = 12$ than any of the existing non-asymptotic bounds.

With the non-asymptotic bounds in Theorem~\ref{thm:BoundWithoutW} and Theorem~\ref{thm:BoundWithW}, the following bounds on the eigenvalues themselves are almost immediate.
\begin{cor}
\label{cor:DPSSEigBounds}
For any $N \in \N$, $W \in (0,\tfrac{1}{2})$, we have
$$\lambda_k \ge 1-\min\left\{8\exp\left[-\dfrac{\floor{2NW}-k-2}{\tfrac{2}{\pi^2}\log(4N)}\right],10\exp\left[-\dfrac{\floor{2NW}-k-7}{\tfrac{2}{\pi^2}\log(100NW+25)}\right]\right\} \quad \text{for} \quad 0 \le k \le \floor{2NW}-1$$
and
$$\lambda_k \le \min\left\{8\exp\left[-\dfrac{k-\ceil{2NW}-1}{\tfrac{2}{\pi^2}\log(4N)}\right],10\exp\left[-\dfrac{k-\ceil{2NW}-6}{\tfrac{2}{\pi^2}\log(100NW+25)}\right]\right\} \quad \text{for} \quad \ceil{2NW} \le k \le N-1.$$
\end{cor}

To the best of our knowledge, the first bound in Corollary~\ref{cor:DPSSEigBounds} represents the first non-asymptotic lower bound on the DPSS eigenvalues $\lambda_k$ for $k \le \floor{2NW}-1$.

The second bound in Corollary~\ref{cor:DPSSEigBounds} is similar in form to (\ref{eq:Boulsane1}), except this result has an exponential decay rate of $\tfrac{\pi^2}{2\log(100 NW+25)}$ instead of $\tfrac{0.069}{\log(\pi NW)+5}$. It is not hard to check that when $NW \ge 0.07$, the exponential decay rate from the second bound is at least $71$ times larger than the exponential decay rate in (\ref{eq:Boulsane1}).

The second bound in Corollary~\ref{cor:DPSSEigBounds} does not capture the faster than exponential decay rate of $\lambda_k$ for $k \ge \tfrac{e\pi}{2}NW$ that is demonstrated by (\ref{eq:Boulsane2}). However, we note that for $NW \ge 15$, the second bound in Corollary~\ref{cor:DPSSEigBounds} will yield an upper bound for $\lambda_{\ceil{e\pi NW/2}}$ that is less than the single precision machine epsilon of $2^{-23} \approx 1.2\times 10^{-7}$. Also, for $NW \ge 31$, the second bound in Corollary~\ref{cor:DPSSEigBounds} will yield an upper bound for $\lambda_{\ceil{e\pi NW/2}}$ that is below the double precision machine epsilon of $2^{-52} \approx 2.2\times 10^{-16}$. So these bounds are still useful.

From the eigenvalue bounds in Corollary~\ref{cor:DPSSEigBounds}, we can obtain the following bounds on the sums of the leading and trailing DPSS eigenvalues.
\begin{cor}
\label{cor:DPSSEigSumBounds}
For any $N \in \N$, $W \in (0,\tfrac{1}{2})$, we have
$$\sum_{k = 0}^{K-1}(1-\lambda_k) \le \min\left\{\dfrac{16}{\pi^2}\log(4N)\exp\left[-\dfrac{\floor{2NW}-K-2}{\tfrac{2}{\pi^2}\log(4N)}\right], \dfrac{20}{\pi^2}\log(100NW+25)\exp\left[-\dfrac{\floor{2NW}-K-7}{\tfrac{2}{\pi^2}\log(100NW+25)}\right]\right\}$$ for $1 \le K \le \floor{2NW}$, and
$$\sum_{k = K}^{N-1}\lambda_k \le \min\left\{\dfrac{16}{\pi^2}\log(4N)\exp\left[-\dfrac{K-\ceil{2NW}-2}{\tfrac{2}{\pi^2}\log(4N)}\right], \dfrac{20}{\pi^2}\log(100NW+25)\exp\left[-\dfrac{K-\ceil{2NW}-7}{\tfrac{2}{\pi^2}\log(100NW+25)}\right]\right\}$$ for $\ceil{2NW} \le K \le N-1$.
\end{cor}

Abreu and Romero \cite{Abreu17} have shown that bias of Thomson's multitaper spectral estimate \cite{Thomson82} (using $K$ tapers) is bounded by the sum of two terms, one which is $\lesssim W^2$ and another which is $\lesssim \tfrac{1}{K}\sum_{k = 0}^{K-1}(1-\lambda_k)$. The variance of this estimate is $\lesssim \tfrac{1}{K}$. By choosing the number of tapers to be $K = 2NW - O(\log(NW)\log(\tfrac{\log(NW)}{\delta}))$ for some small $\delta > 0$ instead of the typically used $\floor{2NW}-1$, one can significantly reduce the bias while only moderately increasing the variance.

Davenport and Wakin \cite{DavenportWakin12} have shown that sampled sinusoids with frequency $|f| \le W$ can be represented by a linear combination of the first $K$ Slepian basis vectors with an average representation error of $\tfrac{1}{2W}\sum_{k = K}^{N-1}\lambda_k$. They present asymptotic bounds on this error which hold when $K = 2NW(1+\rho)$ Slepian basis vectors are used for some fixed constant $\rho > 0$. The second part of Corollary~\ref{cor:DPSSEigSumBounds} shows that we can obtain a small average representation error by using only $K = 2NW + O(\log(NW)\log(\tfrac{\log(NW)}{\delta}))$ Slepian basis vectors for some small $\delta > 0$.

Note that all of the above bounds which depend on $W$ can be easily refined if $W$ is close to $\tfrac{1}{2}$. Let $\mB' \in \R^{N \times N}$ be the prolate matrix with bandwidth parameter $\tfrac{1}{2}-W$, i.e. $\mB'[m,n] = \tfrac{\sin[2\pi(1/2-W)(m-n)]}{\pi(m-n)}$. One can check that $\mB' = \mD(\mId-\mB)\mD^*$ where $\mD \in \R^{N \times N}$ is a unitary diagonal matrix with entries $\mD[n,n] = (-1)^n$. Hence, the eigenvalues of $\mB'$ and $\mB$ are related by $\lambda_k(N,\tfrac{1}{2}-W) = 1-\lambda_{N-1-k}(N,W)$ for $k = 0,\ldots,N-1$. Therefore, for any $N \in \N$ and $\eps \in (0,\tfrac{1}{2})$, the width of the transition region is the same for bandwidths of $W$ and $\tfrac{1}{2}-W$. In particular, when $W \in (\tfrac{1}{4},\tfrac{1}{2})$, we can obtain stronger bounds on both $\#\{k : \eps < \lambda_k(N,W) < 1-\eps\}$ and $\lambda_k(N,W)$ by instead considering the bounds on $\#\{k : \eps < \lambda_k(N,\tfrac{1}{2}-W) < 1-\eps\}$ and $\lambda_k(N,\tfrac{1}{2}-W)$.

Finally, we note that a result by Boulsane, Bourguiba, and Karoui \cite{Boulsane20} shows that the DPSS eigenvalues and the PSWF eigenvalues satisfy $\lambda_k(N,W) \to \widetilde{\lambda}_k(\pi NW)$ as $N \to \infty$ and $W \to 0^+$ with $NW$ held constant. Intuitively, this means that the continuous energy concentration problem is the limit of the discrete energy concentration problem as the discritization gets arbitrarily fine. With this result, the above non-asymptotic results on the DPSS eigenvalues which depend on $NW$ (and not just $N$) can be used to obtain the following non-asymptotic results on the PSWF eigenvalues.

\begin{theorem}
\label{thm:PSWFEigGap}
For any $c > 0$ and $\eps \in (0,\tfrac{1}{2})$, $$\#\left\{k : \eps < \widetilde{\lambda}_k < 1-\eps\right\} \le \dfrac{2}{\pi^2}\log\left(\dfrac{100c}{\pi}+25\right)\log\left(\dfrac{5}{\eps(1-\eps)}\right)+7.$$
\end{theorem}

\begin{cor}
\label{cor:PSWFEigBounds}
For any $c > 0$ and $\eps \in (0,\tfrac{1}{2})$, $$\widetilde{\lambda}_k \ge 1-10\exp\left[-\dfrac{\floor{\tfrac{2c}{\pi}}-k-7}{\tfrac{2}{\pi^2}\log\left(\tfrac{100c}{\pi}+25\right)}\right] \quad \text{for} \quad 0 \le k \le \floor{\dfrac{2c}{\pi}}-1,$$ and $$\widetilde{\lambda}_k \le 10\exp\left[-\dfrac{k-\ceil{\tfrac{2c}{\pi}}-6}{\tfrac{2}{\pi^2}\log\left(\tfrac{100c}{\pi}+25\right)}\right] \quad \text{for} \quad k \ge \ceil{\dfrac{2c}{\pi}}.$$
\end{cor}

\begin{cor}
\label{cor:PSWFEigSumBounds}
For any $c > 0$, we have
$$\sum_{k = 0}^{K-1}\left(1-\widetilde{\lambda}_k\right) \le \dfrac{20}{\pi^2}\log\left(\dfrac{100c}{\pi}+25\right)\exp\left[-\dfrac{\floor{\tfrac{2c}{\pi}}-K-7}{\tfrac{2}{\pi^2}\log(\tfrac{100c}{\pi}+25)}\right] \quad \text{for} \quad 1 \le K \le \floor{\dfrac{2c}{\pi}},$$ and
$$\sum_{k = K}^{\infty}\widetilde{\lambda}_k \le \dfrac{20}{\pi^2}\log\left(\dfrac{100c}{\pi}+25\right)\exp\left[-\dfrac{K-\ceil{\tfrac{2c}{\pi}}-7}{\tfrac{2}{\pi^2}\log(\tfrac{100c}{\pi}+25)}\right] \quad \text{for} \quad K \ge \ceil{\dfrac{2c}{\pi}}.$$
\end{cor}

We note that the non-asymptotic bound in Theorem~\ref{thm:PSWFEigGap} is similar in form to the asymptotic bound by Landau and Widom \cite{LandauWidom80} in that it scales like $O(\log(c) \log(\tfrac{1}{\eps}))$ and has the correct leading constant $\tfrac{2}{\pi^2}$. Furthermore, the constants in this bound are all specified and are mild. As such, this is a substantial improvement over the existing non-asymptotic bounds.

The bounds in Corollary~\ref{cor:PSWFEigBounds} show that the PSWF eigenvalues $\widetilde{\lambda}_k$ approach $1$ and $0$ exponentially as $k$ moves away from the time-bandwidth product $\tfrac{2c}{\pi}$. Also, these bounds are useful (i.e. something stronger than $0 < \widetilde{\lambda}_k < 1$) for all but $O(\log(c))$ values of $k$.

config: arxiv


TITLE: Calculation with Khatri rao product and moore penrose pseudoinverse
QUESTION [0 upvotes]: It is given:
$ \left [(A\diamond B\diamond C)^T  \right ]^\dagger$
$\diamond$ is Kharti -rao product
$\dagger$ -moore penrose pseudoinverse
I have started:
$ \left [(A\diamond B\diamond C)^T  \right ]^\dagger =\left [(A\diamond (B\diamond C))^T  \right ]^\dagger = \left [(A^T \diamond (B\diamond C))^T  \right ]^\dagger=  ((A^T)^\dagger \diamond ((B\diamond C)(C^TC*B^TB) ^\dagger)$
What Can i do with $(A^T)^\dagger $?
the second question is if i have done correctly?
Edit 1:
A: MxN
B: NxN
C: CxN

REPLY [0 votes]: Some hints:

Transpose and pseudo inverse are interchangeable. Therefore, you can ignore the transpose, compute the pseudo inverse first, and then transpose the result.
If a matrix has full column rank, you can expand the pseuso-inverse via $X^\dagger = (X^T X)^{-1} X^T $.
The Khatri-Rao product satisfies $(A \diamond B)^T(A \diamond B) = (A^TA * B^TB)$. Applying this rule twice gives $(A \diamond B \diamond C)^T(A \diamond B\diamond C) = (A^TA * B^TB * C^TC)$.
Overall, this could give something like $(A \diamond B \diamond C) \cdot (A^TA * B^TB * C^TC)^{-1}$ but whether or not this works depends on the dimensions of the matrices and on the rank of the Khatri-Rao product...
*edit: For the dimensions you posted, a necessary condition would be $M \cdot C \geq N^2$.


TITLE: Random variable and independence on unit interval
QUESTION [0 upvotes]: I have a simple probability question that has been confusing me.
Lets say I generate a random variable $X$ drawn from the uniform distribution on $[0,1]$. Now, lets define two real (nonrandom) numbers $p,q\in[0,1]$.
Define event $A$ to be the event that $X\leq p$.
Define event $B$ to be the event that $X \geq (1-q)$.
My question is, for what values of p and q are A and B independent?
My idea is that these two events will be dependent when there is a nonempty intersection between $X\leq p$ and $X \geq (1-q)$ and independent if this intersection is empty. So my answer is that $A$ and $B$ are independent when $p-(1-q)\leq 0$. I was hoping someone could help me know if I am correct and if this equality in my inequality answer relating $p$ and $q$ should be strictly less than? My confusion with this arises because of this boundary when $p=1-q$.

REPLY [1 votes]: By definition, $A$ and $B$ are independent if and only if $\mathbb P(A \cap B) = \mathbb P(A) \mathbb P(B)$.  In this case, $\mathbb P(A) = p$, $\mathbb P(B) = q$, $\mathbb P(A \cap B) = p - (1-q) = p+q-1$ if $p \ge 1-q$, $0$ otherwise.  So for independence you need $p q = p+q-1$ or $p q = 0$.  But $pq - (p+q-1) = (p-1)(q-1)$.  Thus the condition is that $p=0$ or $p=1$ or $q=0$ or $q=1$.


TITLE: $\gcd (ca, cb) = \gcd (a, b)c$ if $c > 0$
QUESTION [5 upvotes]: Let $\gcd (a, b) = d$. So, $ax + by = d$ for some $x, y$. Then $(ca)x + (cb)y = cd$. Thus, $\gcd (ca, cb) = cd = \gcd(a, b)c$.
Does it work?

REPLY [0 votes]: You can use prime factorization if you don't want to work through cumbersome axioms about what properties GCDs satisfy, or work with formulas expressing GCDs of different integers using linear combinations. If you accept prime factorization, your statement is basically trivial. Maybe that means you're not supposed to solve it that way though ;)


TITLE: If $\int_0^\infty |f(x)|^2dx<\infty$ then $F(z)=\int_0^\infty f(t)e^{itz}dt$ is well-defined and continuous
QUESTION [1 upvotes]: Suppose $f$ is a complex valued function defined on $(0,\infty)$ such that $\int_0^\infty |f(x)|^2dx<\infty$.  Then for $z\in \Bbb C$ with $\text{Im}(z)>0$, define $F(z)=\int_0^\infty f(t)e^{itz}dt$. I am trying to show that $F$ is continuous, but I can't even see why that the integral is well-defined. How can we show that $F$ is well-defined?

REPLY [0 votes]: $\newcommand{\Im}{\operatorname{Im}}\newcommand{\Re}{\operatorname{Re}}$
If $f\in L^2(0,\infty)$, then since $x^2$ is convex on $[k,k+1]$, Jensen's Inequality says
$$
\begin{align}
\|f\|_{L^1(k,k+1)}
&\le\|f\|_{L^2(k,k+1)}\tag{1a}\\
&\le\|f\|_{L^2(0,\infty)}\tag{1b}
\end{align}
$$
Furthermore,
$$
\left\|t^ne^{-t\Im(z)}\right\|_{L^\infty(k,k+1)}\le (k+1)^ne^{-k\Im(z)}\tag2
$$
Thus,
$$
\begin{align}
\left\|f(t)\,t^ne^{-t\Im(z)}\right\|_{L^1(0,\infty)}
&\le\sum_{k=0}^\infty\left\|f(t)\,t^ne^{-t\Im(z)}\right\|_{L^1(k,k+1)}\tag{3a}\\
&\le\sum_{k=0}^\infty\|f\|_{L^1(k,k+1)}\left\|t^ne^{-t\Im(z)}\right\|_{L^\infty(k,k+1)}\tag{3b}\\
&\le\sum_{k=0}^\infty\|f\|_{L^2(0,\infty)}(k+1)^ne^{-k\Im(z)}\tag{3c}\\
&\le\|f\|_{L^2(0,\infty)}e^{2\Im(z)}\int_0^\infty x^ne^{-x\Im(z)}\mathrm{d}x\tag{3d}\\[3pt]
&=\|f\|_{L^2(0,\infty)}\frac{e^{2\Im(z)}n!}{\Im(z)^{n+1}}\tag{3e}
\end{align}
$$
Explanation:
$\text{(3a)}$: Minkowski's Inequality
$\text{(3b)}$: Hölder's Inequality
$\text{(3c)}$: apply $(1)$ and $(2)$
$\text{(3d)}$: $(k+1)^ne^{-k\Im(z)}\le e^{2\Im(z)}\int_{k+1}^{k+2}x^ne^{-x\Im(z)}\mathrm{d}x$
$\text{(3e)}$: evaluate integral
Therefore,
$$
\begin{align}
\left|\,\frac{\mathrm{d}^n}{\mathrm{d}z^n}F(z)\,\right|
&=\left|\int_0^\infty f(t)\,t^ne^{-t\Im(z)}e^{it\Re(z)}\,\mathrm{d}t\right|\tag{4a}\\
&\le\|f\|_{L^2(0,\infty)}\frac{e^{2\Im(z)}n!}{\Im(z)^{n+1}}\tag{4b}
\end{align}
$$
which says that for $\Im(z)\gt0$, $F(z)$ is not only well-defined, but also $C^\infty$.


TITLE: Gamma function proof of gamma $\;Γ(1/2) = \sqrt \pi\;$
QUESTION [7 upvotes]: So our teacher doesnt use the same demonstration as most other sites use for proving that gamma of a half is the square root of pi.
I dont understand the demonstration from the first step because he uses the Wallis product but first he represents $Γ(1/2)$ as :
$$Γ(n + 1/2) = 2^{-n}Γ(1/2)\prod_{k=1..n}(2k-1)$$
This is just the first step and i dont undderstand how they get that..
I understand the gamme function and that when you integrate it you get $Γ(x+1) = xΓ(x)$ and i know i need to somehow use this identity but i dunno how.

REPLY [2 votes]: We use Euler's Reflection Formula $\Gamma(1-z)\Gamma(z)=  \frac\pi{\sin(\pi z)}$ with $z=\frac12$.
We then have $\Gamma(1/2)^2=\frac\pi{\sin( \frac\pi2)}$.
Since $\sin( \frac\pi2)=1$ we now have $\Gamma(1/2)^2=\pi$. Finally therefore $\Gamma(1/2)=\sqrt\pi$. Not $-\sqrt\pi$ because we know $\Gamma( 1/2) > 0$.


TITLE: Convergence of $\sum_{\alpha\in \Bbb N^n} \frac{z^\alpha}{\xi(\alpha)}$ on $\operatorname{int} U$ where $U \subset\Bbb C^n$ is bounded
QUESTION [0 upvotes]: Problem. Let $U\subset \Bbb C^n$ be bounded. For $\alpha\in \Bbb N^n$ and $z\in \Bbb C^n$, let $z^\alpha:= z_1^{\alpha_1} z_2^{\alpha_2} \ldots z_n^{\alpha_n} \in \Bbb C$. Prove that $$\sum_{\alpha\in \Bbb N^n} \frac{z^\alpha}{\xi(\alpha)}$$ converges for every $z\in \operatorname{int} U$, where $\xi(\alpha) := \sup_{z\in U} |z^\alpha|$.

The convergence of power series in several complex variables is defined in the following way:

Let $\{c_\alpha\}_{\alpha\in\Bbb N^n} \subset\Bbb C$. The power series $\sum_{\alpha\in \Bbb N^n}c_\alpha (z-a)^\alpha = \sum_{\alpha\in \Bbb N^n} c_\alpha (z_1-a_1)^{\alpha_1} \ldots (z_n-a_n)^{\alpha_n}$ in $n$ variables $z:= (z_1,z_2,\ldots,z_n)$ centered at $a\in \Bbb C^n$ converges at $w\in \Bbb C^n$ if there exists $M> 0$ such that $$\sum_{\alpha\in F} |c_\alpha| |(w-a)^\alpha| \le M$$ for all finite subsets $F\subset\Bbb N^n$.

My work. Since $z\in \operatorname{int} U$ (an open set), there exists $w \in \operatorname{int} U$ such that $|w_j| > |z_j|$ for all $1\le j\le n$. Does this help? Also, if we are able to uniformly bound (in $z$) the summands by $q^{|\alpha|}$ for some $0 < q < 1$, we should be able to repeat the strategy in this answer.
Please give me hints on how to proceed. Thanks!

REPLY [1 votes]: Just wanted to add my solution.
For any $z$ in the interior of $U$, fixing $z_k$, $k\neq i$ while varying $z_i$, $\partial U$ defines a boundary for $z_i$ and it is clear that we can always find $z_i'\in \mathbb{C}$ at the boundary of larger modulus which will increase $|z^\alpha|$. Hence we have
$$\xi(\alpha):=\sup_{z\in U} |z^\alpha| = \sup_{z\in \partial U} |z^\alpha| \,,$$
i.e. the supremum is attained at the boundary.
Using CS
$$\left|\sum_{\alpha\in \Bbb N^n} \frac{z^\alpha}{\xi(\alpha)}\right| \leq \sum_{\alpha\in \Bbb N^n} \frac{|z^\alpha|}{\xi(\alpha)} = \sum_{k=1}^\infty \sum_{\substack{\alpha\in \Bbb N^n \\ \alpha_1+...+\alpha_n=k}} \left(\frac{|z^{\alpha/k}|}{[\xi(\alpha)]^{1/k}}\right)^k \tag{1}$$
and the fact that $[\xi(\alpha)]^{1/k}$ is also the supremum for $|z^{\alpha/k}|$, we can easily check that for fixed $z$ in the interior $$\frac{|z^{\alpha/k}|}{[\xi(\alpha)]^{1/k}} = \frac{|z_1|^{\frac{\alpha_1}{\alpha_1+...+\alpha_n}}\cdots |z_n|^{\frac{\alpha_n}{\alpha_1+...+\alpha_n}}}{[\xi(\alpha)]^{\frac{1}{\alpha_1+...+\alpha_n}}}=c_\alpha(z)<1$$
which holds true for $k\rightarrow \infty$.
Of all of these $c_\alpha$ there is a maximal $c_\alpha=c<1$ and we can continue with (1)
$$\leq \sum_{k=1}^\infty c^k \sum_{\substack{\alpha\in \Bbb N^n \\ \alpha_1+...+\alpha_n=k}} 1 \leq \sum_{k=1}^\infty c^k \sum_{\substack{\alpha\in \Bbb Z_{\geq 0}^n \\ \alpha_1+...+\alpha_n=k}} 1 = \sum_{k=1}^\infty c^k \binom{k+n-1}{k}$$
which implies convergence.


TITLE: Book for Undergrad Differential Geometry
QUESTION [10 upvotes]: I am soon going to start learning differential geometry on my own (I'm trying to learn the math behind General Relativity before I take it next year).  I got the sense that a good, standard 1st book on the subject was do Carmo's Differential Geometry of Curves and Surfaces and so that was the book I planned on reading.  However I just read this question on mathoverflow, and both answers to it suggested that the professor NOT teach a class from a book like do Carmo's because it doesn't cover differential forms.
Would you guys agree that I should find a book that introduces differential forms (and tensors?) given that I am an undergrad physics major who plans to study relativity theory?  If so, what books would you recommend?

REPLY [7 votes]: In my opinion the best Differential geometry book is John M. Lee - Introduction to Smooth Manifolds followed by Loring W. Tu - Introduction to manifolds and Jeffrey M. Lee - Manifolds and Differential Geometry.
For connections and Riemannian Geometry look also John M. Lee - Riemannian Manifolds: An introduction to curvature.

REPLY [3 votes]: I'm going to agree with Bryant in the mentioned link and recommend O'Neill's Elementary Differential Geometry. It is a gentle enough introduction to differential geometry, uses the common language and will prepare you for the usual problems in $\Bbb R^3$ while giving you a hint of what comes next.
It may be profitably followed by his second book and/or John Lee's Introduction to Smooth Manifolds and Riemannian Manifolds.


TITLE: If $X=PX'$, then P is invertible?
QUESTION [2 upvotes]: Let V be a set of all $n \times 1$ column vectors and $X,X'$ is in V. If there exist $n\times n$ matrix P such that $$X=PX'$$
  then can we say P is invertible?

I guess that $X=0 \Leftrightarrow X'=0$ but don't know how to show it.
> I edited that there is a relation between $X,X'$ for certain matrix P such that $$X=PX'$$

REPLY [3 votes]: This is not true.
For example, Take $X=0_{n\times 1}$, $X'$ can be anything, and $P=0_{n\times n}$.
Obviously $X=PX'$, but $P=0$ and therefore not invertible.


TITLE: continuity and convergence
QUESTION [1 upvotes]: Let $f: \mathbb {R}\to \mathbb {R}$ be such a function such that $f'$ is continuous on $\mathbb {R}$. Show that the series $$\sum_{n=1}^{\infty}\{f(\frac{x}{2n})-f(\frac{x}{2n+1})\}$$ converges uniformly on $[0,1]$.
Here $$\sum_{n=1}^{\infty}\frac{\{f(\frac{x}{2n})-f(\frac{x}{2n+1})\}}{\frac{x}{2n}-\frac{x}{2n+1}}(\frac{x}{2n}-\frac{x}{2n+1})$$
Since $f$ is differentiable there exists $c\in (\frac{x}{2n+1},\frac{x}{2n})$, such that $$\sum_{n=1}^{\infty}\frac{\{f(\frac{x}{2n})-f(\frac{x}{2n+1})\}}{\frac{x}{2n}-\frac{x}{2n+1}}=f'(c)$$
Now given $f'$ is continuous on $\mathbb {R}$, $f'$ is continuous on $[0,1]$ and hence bounded say $M$. Hence  $$\sum_{n=1}^{\infty}\frac{\{f(\frac{x}{2n})-f(\frac{x}{2n+1})\}}{\frac{x}{2n}-\frac{x}{2n+1}}\lt \sum_{n=1}^{\infty} M(\frac{x}{2n}-\frac{x}{2n+1})=M\sum_{n=1}^{\infty}\frac{x}{(2n)(2n+1)}$$
$$\lt M\sum_{n=1}^{\infty}\frac{1}{(2n)(2n+1)}$$. Since the R.H.S converges by weistrass M test so does the given series
Is this alright?

REPLY [2 votes]: Yes, this is fine. You have a typo when you use the Mean Value Theorem (the series should not be there). Also, you need to use absolute value in your first inequality (which shows that in fact you show that convergence is absolute).


TITLE: Change the integral into polar coordinates
QUESTION [0 upvotes]: Convert the integral $\int_{-2}^{2} \int_0^{\sqrt{4-x^2}} e^{-(x^2+y^2)} dy\,dx$ into polar coordinates don't need to solve.
my solution is currently $\int_0^2 \int_0^\pi re^{-r^2} d\theta\, dr$
not sure if this is correct, I have subbed in $r\cos\theta$ and $r\sin\theta$ and multiplied by the jacobian, not sure if limits are correct, keep getting confused as to which way around they go, thanks in advance.

REPLY [0 votes]: Your answer is correct. I would have changed the order of integration but there is nothing wrong with your integral.


TITLE: What exactly is background in terms of data analysis in particle physics?
QUESTION [0 upvotes]: I often come across the term "background" in particle physics. Could someone explain what it exactly means?

REPLY [5 votes]: Any general definition is bound to be abstract. I usually go with something like

Everything in a subset of your data where you have (or expect) a signal of some physics that isn't that signal is a background.

What that might consist of depends on the particular case. It is also worth noting that many data sets are subject to multiple analyses, and data that is signal in one may be background in another and vice versa.
Nor is this definition in any way special to particle physics, it's nearly ubiquitous in experimental work.


text:
\section{{\rLCproblems{1}} in bounded treewidth graphs}
\label{sec:boundedTreewidth}

In this section we give a polynomial-time algorithm to solve {\rLCproblems{1}} in bounded treewidth graphs, under mild conditions.
In Section \ref{sec:boundedDegree} we show that these results can be extended to {\rLCproblems{r}} (for any fixed $r \geq 1$) in bounded treewidth and bounded degree graphs.
In Section \ref{sec:globalProp} we will explain how to modify the algorithm in order to add some global properties.

We will solve the problem in a dynamic programming fashion, traversing an easy tree decomposition (see Definition \ref{def:easytreedec}) of the input graph and describing how to proceed with each type of node of the tree decomposition, as it is usual with this kind of problems, but with an abstraction of the ``extra'' parameters involved in ad-hoc solutions of locally checkable problems. In order to describe this abstraction, and hence the algorithm, we first need to introduce the concept of \emph{partial neighborhoods}.

\subsection{Partial neighborhoods}\label{sec:partialNeighborhoods}
\input{5-BoundedTreeWidth-0-PartialNeighborhoods.tex}

\subsection{Notation and definitions}
\input{5-BoundedTreeWidth-1-Notation.tex}

\subsection{Algorithm}
\label{subsec:alg}
\input{5-BoundedTreeWidth-2-Lambda.tex}

\subsection{Time complexity}
\input{5-BoundedTreeWidth-3-Complexity.tex}

\subsection{Special cases}
\input{5-BoundedTreeWidth-4-SpecialCases.tex}

\subsection{{\LCVP} problems}
\input{5-BoundedTreeWidth-5-LCVP.tex}


text:
\begin{document}

\maketitle

\begin{abstract}
In this paper, we study the competition graphs of $d$-partial orders
and obtain their characterization which extends results given
by Cho and Kim [H.~H.~Cho and S.~-R.~Kim:
A class of acyclic digraphs with interval competition graphs,
\emph{Discrete Applied Mathematics}
\textbf{148} (2005) 171--180].
We also show that any graph can be made into the competition graph of a $d$-partial order
for some positive integer $d$
as long as adding isolated vertices is allowed.
We then study graphs whose partial order competition dimensions are at most three,
where the partial order competition dimension of a graph $G$
is the smallest nonnegative integer $d$ such that $G$ together with some isolated vertices
is the competition graph of a $d$-partial order.
\end{abstract}

\noindent
{\bf Keywords:}
competition graph,
$d$-partial order,
homothetic regular $(d-1)$-simplices,
intersection graph,
partial order competition dimension

\noindent
{\bf 2010 Mathematics Subject Classification:} 05C20, 05C75

\section{Introduction}

The \emph{competition graph} of a digraph $D$, which is denoted by $C(D)$,
has the same vertex set as $D$ and has an edge $xy$
between two distinct vertices $x$ and $y$
if for some vertex $z \in V$,
the arcs $(x,z)$ and $(y,z)$ are in $D$.
The competition graph has been extensively studied over the last 40 years
(see the survey articles by Kim~\cite{Kim93} and Lundgren~\cite{Lundgren89}).

Let $d$ be a positive integer.
For $\mathbf{x} = (x_1,x_2,\ldots, x_d)$,
$\mathbf{y} = (y_1,y_2,\ldots, y_d) \in \mathbb{R}^d$,
we write
$\mathbf{x} \prec \mathbf{y}$
if $x_i<y_i$ for each $i=1, \ldots, d$.
For a finite subset $S$ of $\mathbb{R}^d$,
let $D_S$ be the digraph defined by $V(D_S) = S$ and
$A(D_S) = \{(\mathbf{x},\mathbf{v}) \mid \mathbf{v}, \mathbf{x} \in S,
\mathbf{v} \prec \mathbf{x} \}$.
A digraph $D$ is called a \emph{$d$-partial order}
if there exists a finite subset $S$ of $\mathbb{R}^d$
such that $D$ is isomorphic to the digraph $D_S$.
By convention, the zero-dimensional Euclidean space $\mathbb{R}^0$
consists of a single point $0$.
In this context, we define a digraph with exactly one vertex as a \emph{$0$-partial order}.
A $2$-partial order is also called \emph{doubly partial order}
(see Figure~\ref{egofdpo} for an example).

\begin{figure}
\psfrag{D}{\small $D$}
\psfrag{u(1,6)}{\small $(1,6)$} \psfrag{h(4,0)}{\small $(4,0)$}
\psfrag{v(2,5)}{\small $(2,5)$} \psfrag{w(4,4)}{\small $(4,4)$}
\psfrag{p(3,3)}{\small $(3,3)$} \psfrag{q(3,1)}{\small $(3,1)$}
\psfrag{s(1,2)}{\small $(1,2)$} \psfrag{t(0,4)}{\small $(0,4)$}
\psfrag{x(4,3)}{\small $(4,3)$} \psfrag{y(5,2)}{\small $(5,2)$}
\psfrag{z(5,1)}{\small $(5,1)$}
\begin{center}
\includegraphics[height=5cm]{EGofDPO.eps}
\end{center}
\caption{A doubly partial order $D$}
\label{egofdpo}
\end{figure}

Cho and Kim~\cite{chokim} studied the competition graphs of doubly partial orders
and showed that the competition graphs of these digraphs are interval graphs
and any interval graph can be made into the competition graph of a doubly partial order
by adding sufficiently many isolated vertices.

\begin{Thm}[\cite{chokim}]\label{dpo}
The competition graph of a doubly partial order is an interval graph.
\end{Thm}

\begin{Thm}[\cite{chokim}]\label{interval}
Every interval graph can be made into the competition graph of
a doubly partial order by adding sufficiently many isolated vertices.
\end{Thm}

\noindent
Several variants of competition graphs of doubly partial orders
also have been studied
(see \cite{SJkim, Niche2009, hypergraph, LuWu, PLK:mStepDPO, Phylogeny}).

In this paper, we study the competition graphs of $d$-partial orders.
We obtain their characterization which nicely extends results given by Cho and Kim~\cite{chokim}.
We also show that any graph can be made into the competition graph of a $d$-partial order
for some positive integer $d$
as long as adding isolated vertices is allowed.
We then introduce the notion of the partial order competition dimension of a graph.
Especially, we study graphs whose partial order competition dimensions
are at most three.

\section{The competition graphs of $d$-partial orders}

In this section, we use the following notation.
We use a bold faced letter to represent a point
in $\mathbb{R}^d$ ($d \geq 2$).
For $\mathbf{x} \in \mathbb{R}^d$,
let $x_i$ denote the $i$th component of $\mathbf{x}$
for each $i=1, \ldots, d$.
Let $\mathbf{e}_i \in \mathbb{R}^d$
be the standard unit vector whose $i$th component is $1$, i.e.,
$\mathbf{e}_1:=(1, 0, \ldots, 0)$, $\ldots$, $\mathbf{e}_d:=(0, \ldots, 0,1)$.
Let $\mathbf{1}$ be the all-one vector $(1,\ldots,1)$ in $\mathbb{R}^d$.
Note that, for $\mathbf{x} \in \mathbb{R}^d$,
the standard inner product of $\mathbf{x}$ and $\mathbf{1}$ is
\[
\mathbf{x} \cdot \mathbf{1} = \sum_{i=1}^d x_i.
\]

For $\mathbf{v}_1, \ldots, \mathbf{v}_n \in \mathbb{R}^d$,
let $\text{{\rm Conv}}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$
denote the \emph{convex hull} of $\mathbf{v}_1, \ldots, \mathbf{v}_n \in \mathbb{R}^d$, i.e.,
\[
\text{{\rm Conv}}(\mathbf{v}_1, \ldots, \mathbf{v}_n) :=
\left\{ \sum_{i=1}^n \lambda_i\mathbf{v}_i \mid \sum_{i=1}^n \lambda_i=1,
\lambda_i \geq 0, 1
\leq i \leq n \right\}.
\]

\subsection{The regular $(d-1)$-dimensional simplex \boldmath$\triangle^{d-1}{(\bf p)}$}

Let $\mathcal{H}^d$ be
the hyperplane in $\mathbb{R}^d$ defined by
the equation $\mathbf{x} \cdot \mathbf{1} = 0$,
and let $\mathcal{H}_+^d$ be
the open half space in $\mathbb{R}^d$ defined by
the inequality $\mathbf{x} \cdot \mathbf{1} > 0$,
i.e.,
\[
\mathcal{H}^d := \{\mathbf{x} \in \mathbb{R}^d \mid
\mathbf{x} \cdot \mathbf{1} = 0 \},
\qquad
\mathcal{H}_+^d := \{\mathbf{x} \in \mathbb{R}^d \mid
\mathbf{x} \cdot \mathbf{1} > 0 \}.
\]
We fix a point $\mathbf{p}$ in $\mathcal{H}_+^d$.
Let $\triangle^{d-1}(\mathbf{p})$ be the intersection of the hyperplane $\mathcal{H}^d$
and the closed cone
\[
\{\mathbf{x} \in \mathbb{R}^d \mid x_i \leq p_i \ (i= 1, \ldots, d) \}.
\]

\begin{figure}
\psfrag{p}{\footnotesize${\bf p}=(p_1,p_2,p_3)$}
\psfrag{q}{\footnotesize$\mathcal{H}^3$}
\psfrag{x}{\footnotesize$x$}
\psfrag{y}{\footnotesize$y$}
\psfrag{z}{\footnotesize$z$}
\psfrag{r}{\footnotesize$\triangle^2({\bf p})$}
\psfrag{s}{\footnotesize$(-p_2-p_3,p_2,p_3)$}
\psfrag{t}{\footnotesize$(p_1,-p_1-p_3,p_3)$}
\psfrag{u}{\footnotesize$(p_1,p_2,-p_1-p_2)$}
\begin{center}
\includegraphics[height=5cm]{Tetrahedron1}
\end{center}
\caption{A point ${\bf p} \in \mathcal{H}^3_+$ and the triangle $\triangle^2({\bf p})$}
\label{tetrahedron}
\end{figure}

\begin{Lem}\label{lem:delta}
For $\mathbf{p} \in \mathcal{H}_+^d$,
the set $\triangle^{d-1}(\mathbf{p})$ is the convex hull
$\text{{\rm Conv}}(\mathbf{v}_1, \ldots, \mathbf{v}_d)$
of the vectors $\mathbf{v}_1, \ldots, \mathbf{v}_d$ defined by
\begin{equation*}
\mathbf{v}_ i = \mathbf{p} - (\mathbf{p} \cdot \mathbf{1}) \mathbf{e}_i
\quad (i = 1, \ldots, d).
\end{equation*}
Moreover, $\triangle^{d-1}(\mathbf{p})$ is a regular $(d-1)$-simplex.
\end{Lem}

\begin{proof}
Let $\mathbf{v}_1$, $\ldots$, $\mathbf{v}_d \in \mathbb{R}^d$ be the intersections of
the hyperplane $\mathcal{H}^d$
and the lines going through $\mathbf{p}$ with directional vectors
$\mathbf{e}_1, \ldots, \mathbf{e}_d$, respectively.
Then
$\mathbf{v}_ i= \mathbf{p} - (\mathbf{p} \cdot \mathbf{1}) \mathbf{e}_i$ for $i = 1, \ldots, d$.
By definition, we have
$\triangle^{d-1}(\mathbf{p}) = \text{{\rm Conv}}(\mathbf{v}_1, \ldots, \mathbf{v}_d)$.
Since $\mathbf{v}_1, \ldots, \mathbf{v}_d$ are linearly independent,
the set $\triangle^{d-1}(\mathbf{p})$ is a $(d-1)$-simplex.
Moreover, since the length of each edge of $\triangle^{d-1}(\mathbf{p})$ is equal to
$\sqrt{2}(\mathbf{p} \cdot \mathbf{1})$,
the simplex $\triangle^{d-1}(\mathbf{p})$ is regular.
\end{proof}

Note that the distance between $\mathbf{p}$ and each vertex of $\triangle^{d-1}(\mathbf{p})$ is
equal to $\mathbf{p} \cdot \mathbf{1}$.
Moreover, the directional vector for the line passing through the vertices $\mathbf{v}_i$ and $\mathbf{v}_j$ is
$\mathbf{e}_j - \mathbf{e}_i$
for distinct $i$, $j$ in $\{1,\ldots,d\}$.
The center of $\triangle^{d-1}(\mathbf{p})$ is
$\frac{1}{d} \sum_{i=1}^d \mathbf{v}_i
= \mathbf{p} - \frac{1}{d}(\mathbf{p} \cdot \mathbf{1}) \mathbf{1}$.
Therefore,
the directional vector from this center to the point $\mathbf{p}$ is parallel to the all-one vector $\mathbf{1}$, and
the distance between this center and the point $\mathbf{p}$ is $\frac{1}{\sqrt{d}}(\mathbf{p} \cdot \mathbf{1})$
which is $\frac{1}{\sqrt{2d}}$ times the edge length of $\triangle^{d-1}(\mathbf{p})$.

We say that two geometric figures in $\mathbb{R}^d$ are \emph{homothetic} if
they are related by a geometric contraction or expansion.
From the above observation, we can conclude the following:

\begin{Prop}\label{X1}
If $\mathbf{p}, \mathbf{q} \in \mathcal{H}_+^d$,
then $\triangle^{d-1}(\mathbf{p})$ and $\triangle^{d-1}(\mathbf{q})$ are homothetic.
\end{Prop}

\subsection{A bijection from $\mathcal{H}_+^d$
to the set of certain regular $(d-1)$-simplices}

\begin{Lem}\label{fixed}
The vertices of $\triangle^{d-1}(\mathbf{1})$
may be labeled as $\mathbf{w}_1, \ldots, \mathbf{w}_d$
so that $\mathbf{w}_j-\mathbf{w}_i$ is a positive scalar multiple of
$\mathbf{e}_i - \mathbf{e}_{j}$ for any distinct $i,j$ in $\{1,\ldots,d\}$.
\end{Lem}

\begin{proof}
By Lemma~\ref{lem:delta}, the vertices of $\triangle^{d-1}(\mathbf{1})$ are
$\mathbf{1} - d \mathbf{e}_{i}$ for $i=1, \ldots, d$.
We denote $\mathbf{1} - d \mathbf{e}_{i}$ by $\mathbf{w}_i$ to obtain the desired labeling.
\end{proof}

\begin{Lem}\label{regsim}
Let $d$ be an integer with $d \geq 2$.
Suppose that
$\Lambda$ is a regular $(d-1)$-simplex contained in the hyperplane $\mathcal{H}^d$
homothetic to $\triangle^{d-1}(\mathbf{1})$.
Then,
there exists
$\mathbf{p} \in \mathcal{H}_+^d$
such that $\Lambda=\triangle^{d-1}(\mathbf{p})$.
\end{Lem}

\begin{proof}
Since $\Lambda$ is homothetic to $\triangle^{d-1}(\mathbf{1})$,
there exists $\mathbf{v}_1, \ldots, \mathbf{v}_d \in \mathbb{R}^d$
which are linearly independent
such that
$\Lambda=\text{{\rm Conv}}(\mathbf{v}_1, \ldots, \mathbf{v}_d)$
and $\mathbf{v}_j - \mathbf{v}_i$ is a positive scalar multiple of
$\mathbf{e}_i - \mathbf{e}_j$ for any distinct $i$ and $j$ in $\{1, \ldots, d\}$ by Lemma~\ref{fixed}.
Moreover, ${\mathbf v}_i \cdot \mathbf{e}_i  < {\mathbf v}_j \cdot \mathbf{e}_i $
for any distinct $i$ and $j$ in $\{1, \ldots, d\}$.
Let $\mathbf{p} \in \mathbb{R}^d$ be a vector
defined by $p_i : \max\{ \mathbf{v}_k \cdot \mathbf{e}_i \mid 1 \leq k \leq d \}$
$(i=1, \ldots, d)$.
Then, $\Lambda=\triangle^{d-1}(\mathbf{p})$.
Since $\mathbf{v}_1 \in \mathcal{H}^d$,
we have
$\mathbf{v}_1 \cdot \mathbf{1}=0$.
Since $p_i \geq \mathbf{v}_1 \cdot \mathbf{e}_i$ for any $i=1, \ldots, d$,
we have
$\mathbf{p} \cdot \mathbf{1} \geq \mathbf{v}_1 \cdot \mathbf{1}=0$.
If $\mathbf{p} \cdot \mathbf{1} = 0$, then
we obtain $\mathbf{p} = \mathbf{v}_1$ and
$p_1 = \mathbf{v}_1 \cdot \mathbf{e}_1 < \mathbf{v}_2 \cdot \mathbf{e}_1$,
which is a contradiction to the definition of $p_1$.
Therefore $\mathbf{p} \cdot \mathbf{1} > 0$,
i.e., $\mathbf{p} \in \mathcal{H}_+^d$.
Thus the lemma holds.
\end{proof}

Let $d$ be an integer with $d \geq 2$.
Let $\mathcal{F}^{d-1}_*$ be
the set of
the regular $(d-1)$-simplices in
the hyperplane $\mathcal{H}^d$ which are homothetic to $\triangle^{d-1}(\mathbf{1})$.
Let $f_*$ be a map from $\mathcal{H}_+^d$ to $\mathcal{F}^{d-1}_*$
defined by $f_*(\mathbf{p}) = \triangle^{d-1}(\mathbf{p})$.
By Lemma \ref{lem:delta} and Proposition~\ref{X1},
$\triangle^{d-1}(\mathbf{p}) \in \mathcal{F}^{d-1}_*$ and therefore
the map $f_*$ is well-defined.

\begin{Prop}\label{prop:bijection}
For each integer $d \geq 2$,
the map $f_* : \mathcal{H}_+^d \to \mathcal{F}^{d-1}_*$ is a bijection.
\end{Prop}

\begin{proof}
By Lemma \ref{regsim}, the map $f_*$ is surjective.
Suppose that $\triangle^{d-1}(\mathbf{p}) = \triangle^{d-1}(\mathbf{q})$.
Since the centers of $\triangle^{d-1}(\mathbf{p})$ and $\triangle^{d-1}(\mathbf{q})$
are the same, we have
$\mathbf{p} - \frac{1}{d}(\mathbf{p} \cdot \mathbf{1}) \mathbf{1}
= \mathbf{q} - \frac{1}{d}(\mathbf{q} \cdot \mathbf{1}) \mathbf{1}$.
Since the lengths of edges of $\triangle^{d-1}(\mathbf{p})$ and $\triangle^{d-1}(\mathbf{q})$
are the same, we have
$\sqrt{2}(\mathbf{p} \cdot \mathbf{1}) = \sqrt{2}(\mathbf{q} \cdot \mathbf{1})$.
Therefore, we have $\mathbf{p} = \mathbf{q}$.
Thus the map $f_*$ is injective.
Hence the map $f_*$ is a bijection.
\end{proof}

Let $\mathcal{F}^{d-1}$ be the set of the interiors of the regular $(d-1)$-simplices in
the hyperplane $\mathcal{H}^d$ which are homothetic to $\triangle^{d-1}(\mathbf{1})$.
Then there is a clear bijection $\varphi: \mathcal{F}_*^{d-1} \rightarrow \mathcal{F}^{d-1}$
such that for each element in $\mathcal{F}_*^{d-1}$, its $\varphi$-value is its interior.
Therefore we obtain the following corollary.

\begin{Cor}\label{cor:bijection}
For each integer $d \geq 2$,
the map $\varphi \circ f_* : \mathcal{H}_+^d \to \mathcal{F}^{d-1}$ is a bijection.
\end{Cor}

\subsection{A characterization of the competition graphs of $d$-partial orders}

Let $A^{d-1}(\mathbf{p})$ be the interior of the regular simplex $\triangle^{d-1}(\mathbf{p})$,
i.e., $A^{d-1}(\mathbf{p}) := \text{int}(\triangle^{d-1}(\mathbf{p}))$. Then
\[
A^{d-1}(\mathbf{p}) = \{\mathbf{x} \in \mathcal{H}^d \mid \mathbf{x} \prec \mathbf{p} \}.
\]

\begin{Prop}\label{X3}
For $\mathbf{p},\mathbf{q} \in \mathcal{H}_+^d$,
$\triangle^{d-1}(\mathbf{p})$ is
contained in $A^{d-1}(\mathbf{q})$
if and only if $\mathbf{p} \prec \mathbf{q}$.
\end{Prop}

\begin{proof}
Suppose that $\mathbf{p}\prec \mathbf{q}$.
Take a point $\mathbf{a}$ in $\triangle^{d-1}(\mathbf{p})$.
Then $a_k \leq p_k$ for each $k=1, \ldots, d$.
By the assumption that $\mathbf{p}\prec \mathbf{q}$, $a_k < q_k$ for each $k=1, \ldots, d$,
that is, $\mathbf{a} \prec \mathbf{q}$.
Thus $\triangle^{d-1}(\mathbf{p})$ is contained in $A^{d-1}(\mathbf{q})$.

Suppose that $\triangle^{d-1}(\mathbf{p})$ is
contained in $A^{d-1}(\mathbf{q})$.
Then, by Lemma~\ref{lem:delta},
$\mathbf{p} - (\mathbf{p} \cdot \mathbf{1}) \mathbf{e}_i$ $(i=1, \ldots, d)$
are points in $A^{d-1}(\mathbf{q})$.
By the definition of $A^{d-1}(\mathbf{q})$, we have
$\mathbf{p} - (\mathbf{p} \cdot \mathbf{1}) \mathbf{e}_i \prec \mathbf{q}$ $(i=1, \ldots, d)$,
which implies $\mathbf{p} \prec \mathbf{q}$.
\end{proof}

\begin{Lem}\label{lem:adj}
Let $d$ be a positive integer and let $D$ be a $d$-partial order.
Then, two vertices $\mathbf{v}$ and $\mathbf{w}$ of $D$ are adjacent in the competition graph of $D$
if and only if there exists a vertex $\mathbf{a}$ in $D$ such that
$\triangle^{d-1}(\mathbf{a}) \subseteq A^{d-1}(\mathbf{v}) \cap A^{d-1}(\mathbf{w})$.
\end{Lem}

\begin{proof}
By definition,
two vertices $\mathbf{v}$ and $\mathbf{w}$ are adjacent in the competition graph of $D$
if and only if
there exists a vertex $\mathbf{a}$ in $D$ such that $\mathbf{a} \prec \mathbf{v}$
and $\mathbf{a} \prec \mathbf{w}$.
By Proposition~\ref{X3},
$\mathbf{a} \prec \mathbf{v}$
and $\mathbf{a} \prec \mathbf{w}$ holds
if and only if
$\triangle^{d-1}(\mathbf{a}) \subseteq A^{d-1}(\mathbf{v})$
and $\triangle^{d-1}(\mathbf{a}) \subseteq A^{d-1}(\mathbf{w})$,
that is, $\triangle^{d-1}(\mathbf{a}) \subseteq A^{d-1}(\mathbf{v}) \cap A^{d-1}(\mathbf{w})$.
Thus the lemma holds.
\end{proof}

The following result extends Theorems~\ref{dpo} and \ref{interval}.

\begin{Thm}\label{thm:intersectiongeneral}
Let $G$ be a graph and let $d$ be an integer with $d \geq 2$.
Then, $G$ is the competition graph of a $d$-partial order
if and only if
there exists a family $\mathcal{F}$ of the interiors of regular $(d-1)$-simplices in $\mathbb{R}^d$
which are
contained in the hyperplane $\mathcal{H}^d$ and homothetic to
$A^{d-1}(\mathbf{1})$
and there exists a one-to-one correspondence between the vertex set of $G$ and $\mathcal{F}$
such that
\begin{itemize}
\item[{\rm ($\star$)}]
two vertices $v$ and $w$ are adjacent in $G$ if and only if
two elements in $\mathcal{F}$ corresponding to $v$ and $w$
have the intersection containing the closure of another element in $\mathcal{F}$.
\end{itemize}
\end{Thm}

\begin{proof}
First we show the ``only if" part.
Let $D$ be a $d$-partial order
and let $G$ be the competition graph of $D$.
Without loss of generality, we may assume that $V(D) \subseteq \mathcal{H}^d_+$
by translating each of the vertices of $D$ in the same direction and by the same amount
since the competition graph of $D$ is determined only by the adjacency among vertices of $D$.
Consequently $A^{d-1}(\mathbf{v}) \neq \emptyset$ for each vertex $\mathbf{v}$ of $D$.
Let
$\mathcal{F}=\{A^{d-1}(\mathbf{v}) \mid \mathbf{v} \in V(D)\}$
and let $f:V(G) \to \mathcal{F}$
be the map defined by
$f(\mathbf{v}) = A^{d-1}(\mathbf{v})$ for $\mathbf{v} \in V(D)$.
Note that $\mathcal{F} \subseteq \mathcal{F}^{d-1}$.
Since the map $f:V(G) \to \mathcal{F}$
is a restriction of the map $\varphi \circ f_*:V(G) \to \mathcal{F}^{d-1}$,
it follows from Corollary~\ref{cor:bijection} that
$f$ is a bijection.
By Lemma \ref{lem:adj}, the condition ($\star$) holds.

Second, we show the ``if" part.
Suppose that there exist a family $\mathcal{F}  \subseteq \mathcal{F}^{d-1}$
and a bijection $f:V(G) \to \mathcal{F}$ such that the condition ($\star$) holds.
By Corollary~\ref{cor:bijection},
each element in $\mathcal{F}$ can be represented as $A^{d-1}(\mathbf{p})$
for some $\mathbf{p} \in \mathcal{H}^d_+$.
Let $D$ be a digraph with vertex set
$V(D)=\{\mathbf{p} \in \mathbb{R}^d \mid A^{d-1}(\mathbf{p}) \in \mathcal{F}\}$
and arc set $A(D)=\{(\mathbf{p}, \mathbf{q}) \mid \mathbf{p}, \mathbf{q} \in V(D),
\mathbf{p} \neq \mathbf{q}, \triangle^{d-1}(\mathbf{q}) \subseteq A^{d-1}(\mathbf{p}) \}$.
By Proposition~\ref{X3}, $(\mathbf{p},\mathbf{q}) \in A(D)$ if and only if $\mathbf{q} \prec \mathbf{p}$,
so $D$ is a $d$-partial order.
Now, take two vertices $v$ and $w$ in $G$.
Then, by the hypothesis and above argument, $v$ and $w$ correspond to some points $\mathbf{p}$ and $\mathbf{q}$
in $\mathbb{R}^d$, respectively,
so that $v$ and $w$ are adjacent if and only if
both $A^{d-1}(\mathbf{p})$ and $A^{d-1}(\mathbf{q})$ contain the closure of an element in $\mathcal{F}$,
that is, $\triangle^{d-1}(\mathbf{r})$ for some $\mathbf{r} \in \mathbb{R}^d$.
By the definition of $D$, $(\mathbf{p},\mathbf{r}) \in A(D)$ and $(\mathbf{q},\mathbf{r}) \in A(D)$.
Consequently, $v$ and $w$ are adjacent if and only if
the corresponding vertices $\mathbf{p}$ and $\mathbf{q}$ have a common out-neighbor in $D$.
Hence $G$ is the competition graph of the $d$-partial order $D$.
\end{proof}

\subsection{Intersection graphs and the competition graphs of $d$-partial orders}

\begin{Thm}\label{thm:open}
If $G$ is the intersection graph of
a finite family of homothetic open regular $(d-1)$-simplices,
then $G$ together with sufficiently many new isolated vertices
is the competition graph of a $d$-partial order.
\end{Thm}

\begin{proof}
Let $\mathcal{A} = \{A_1, \ldots A_n \}$ be
a finite family of homothetic open regular $(d-1)$-simplices,
and let $G$ be the intersection graph of $\mathcal{A}$
with bijection $\phi:\mathcal{A} \to V(G)$.
For each distinct pair of $i$ and $j$ in $\{1, \ldots, n\}$
such that $A_i \cap A_j \neq \emptyset$,
let $B_{ij}$ be an open regular $(d-1)$-simplex homothetic $A_1$
such that the closure of $B_{ij}$ is contained in $A_i \cap A_j$.
We can take such $B_{ij}$ so that $B_{ij} \cap B_{i'j'} = \emptyset$
for distinct pairs $\{i,j\}$ and $\{i',j'\}$.
Let $\mathcal{B} = \{B_{ij} \mid i, j \in \{1, \ldots, n\},
i \neq j, A_i \cap A_j \neq \emptyset \}$.
Then the family $\mathcal{F} := \mathcal{A} \cup \mathcal{B}$
and a map $f: \mathcal{F} \to V(G) \cup \{ z_1, \ldots, z_{|\mathcal{B}|} \}$
such that $f|_{\mathcal{A}} = \phi$ and $f(\mathcal{B}) = \{ z_1, \ldots, z_{|\mathcal{B}|} \}$
satisfy the condition ($\star$) in Theorem \ref{thm:intersectiongeneral}.
Thus $G \cup \{ z_1, \ldots, z_{|\mathcal{B}|} \}$ is
the competition graph of a $d$-partial order.
\end{proof}

\begin{Lem}\label{lem:closed}
If $G$ is the intersection graph of
a finite family $\mathcal{F}$ of homothetic closed regular $(d-1)$-simplices,
then
$G$ is the intersection graph of
a finite family of homothetic open regular $(d-1)$-simplices.
\end{Lem}

\begin{proof}
Let $\mathcal{D} = \{\triangle_1, \ldots \triangle_n \}$ be
a finite family of homothetic closed regular $(d-1)$-simplices,
and let $G$ be the intersection graph of $\mathcal{D}$
with bijection $\phi:\mathcal{D} \to V(G)$.
Let
\[
\varepsilon = \frac{1}{3} \min \{ d( \triangle_i, \triangle_j) \mid
i, j \in \{1, \ldots, n\},
\triangle_i \cap \triangle_j = \emptyset \}
\]
where
$d( \triangle_i, \triangle_j) = \inf\{d({\mathbf x}, {\mathbf y})
\mid {\mathbf x} \in \triangle_i, {\mathbf y} \in \triangle_j \}$.

We make each simplex in $\mathcal{D}$ $(1+\varepsilon)$ times bigger
while the center of each simplex is fixed.
Then we take the interiors of these closed simplices.
By the choice of $\varepsilon$, the graph $G$ is
the intersection graph of the family of newly obtained open simplices.
Hence the lemma holds.
\end{proof}

\begin{Thm}\label{thm:closed}
If $G$ is the intersection graph of
a finite family $\mathcal{F}$ of homothetic closed regular $(d-1)$-simplices,
then $G$ together with sufficiently many new isolated vertices
is the competition graph of a $d$-partial order.
\end{Thm}

\begin{proof}
The theorem follows from
Lemma~\ref{lem:closed} and Theorem~\ref{thm:open}.
\end{proof}

\begin{Rem}
In the case where $d=2$,
Theorem~\ref{thm:closed} is the same as Theorem~\ref{interval}.
Due to Theorem~\ref{dpo}, the converse of Theorem \ref{thm:closed} is true for $d=2$.
In fact, we can show that the converse of Theorem~\ref{thm:open} is also true for $d=2$.
\end{Rem}

The following example shows that the converses of Theorems~\ref{thm:open}
and \ref{thm:closed}
are not true for $d = 3$.

\begin{Ex}
Let $G$ be a subdivision of $K_5$ given in Figure~\ref{counterexample}.
Then, by Theorem~\ref{thm:intersectiongeneral},
the family of homothetic equilateral triangles given in the figure
makes $G$ together with $9$ isolated vertices into the competition graph of a $3$-partial order.
However,
$G$ is not the intersection graph of any family of homothetic equilateral
closed triangles.
By Lemma \ref{lem:closed},
$G$ is not the intersection graph of any family of homothetic equilateral
open triangles, either.
\end{Ex}

\begin{proof}
Suppose that there exists a family $\mathcal{F}:=\{\triangle(v) \mid v \in V(G) \}$
of homothetic equilateral closed triangles
such that $G$ is the intersection graph of $\mathcal{F}$.
Since $v_1v_2v_3v_4v_1$ is an induced cycle in $G$,
the triangles $\triangle(v_1)$, $\triangle(v_2)$, $\triangle(v_3)$, and $\triangle(v_4)$
are uniquely located as in Figure~\ref{counterexample1}
up to the sizes of triangles.
Since the vertices $v_1$, $v_3$, and $v_4$ are neighbors of both $v_5$ and $v_7$ in $G$
whereas $v_2$ is not, and the vertices $v_5$ and $v_7$ are not adjacent in $G$,
we may conclude that the locations of $\triangle(v_5)$ and $\triangle(v_7)$
should be those for the triangles I and II given in Figure~\ref{counterexample1}.
Since the triangle II cannot have intersections with $\triangle(v_2)$ and the triangle I,
all of its sides are surrounded by $\triangle(v_1)$, $\triangle(v_2)$, $\triangle(v_3)$, and $\triangle(v_4)$.
Now, since $v_6$ is adjacent to $v_5$ and $v_7$,
$\triangle(v_6)$ must have intersections with both $\triangle(v_5)$ and $\triangle(v_7)$.
However, it cannot be done without having an intersection with
one of $\triangle(v_1)$, $\triangle(v_2)$, $\triangle(v_3)$, and $\triangle(v_4)$,
which is a contradiction to the fact that
none of $v_1$, $v_2$, $v_3$, and $v_4$ is adjacent to $v_6$ in $G$.
\end{proof}

\begin{figure}
\psfrag{a}{$v_1$}
\psfrag{b}{$v_2$}
\psfrag{c}{$v_3$}
\psfrag{d}{$v_4$}
\psfrag{e}{$v_5$}
\psfrag{f}{$v_6$}
\psfrag{g}{$v_7$}
\psfrag{A}{$A^2(\mathbf{v}_1)$}
\psfrag{B}{$A^2(\mathbf{v}_2)$}
\psfrag{C}{$A^2(\mathbf{v}_3)$}
\psfrag{D}{$A^2(\mathbf{v}_4)$}
\psfrag{E}{$A^2(\mathbf{v}_5)$}
\psfrag{F}{$A^2(\mathbf{v}_6)$}
\psfrag{G}{$A^2(\mathbf{v}_7)$}
\psfrag{h}{$G$}
\begin{center}
\includegraphics[height=5cm]{Counterexample.eps}
\end{center}
\caption{A subdivision $G$ of $K_5$ and a family of homothetic equilateral triangles making
$G$ together with $9$ isolated vertices into
the competition graph of a $3$-partial order}
\label{counterexample}
\end{figure}

\begin{figure}
\psfrag{A}{$\triangle(v_1)$}
\psfrag{B}{$\triangle(v_2)$}
\psfrag{C}{$\triangle(v_3)$}
\psfrag{D}{$\triangle(v_4)$}
\psfrag{E}{I}
\psfrag{G}{II}
\begin{center}
\includegraphics[height=5cm]{Counterexample1.eps}
\end{center}
\caption{An assignment of homothetic equilateral triangles to vertices
$v_1$, $v_2$, $v_3$, $v_4$, $v_5$, $v_7$ of $G$ given in Figure~\ref{counterexample}}
\label{counterexample1}
\end{figure}

\section{The partial order competition dimension of a graph}

\begin{Prop}\label{prop:01}
Let $d$ be a positive integer.
If $G$ is the competition graph of a $d$-partial order,
then $G$ is the competition graph of a $(d+1)$-partial order.
\end{Prop}

\begin{proof}
Let $D$ be a $d$-partial order such that
$G$ is the competition graph of $D$.
For each $\mathbf{v} \in V(D) \subseteq \mathbb{R}^{d}$,
we define
$\tilde{\mathbf{v}} \in \mathbb{R}^{d+1}$
by
\[
\tilde{\mathbf{v}} = \left(v_1, \ldots, v_d, \sum_{i=1}^d v_i \right).
\]
Then $\{\tilde{\mathbf{v}} \mid \mathbf{v} \in V(D) \}$
defines a $(d+1)$-partial order $\tilde{D}$.
Since
\begin{eqnarray*}
\tilde{\mathbf{v}} \prec \tilde{\mathbf{w}}
&\Leftrightarrow & {v}_i < {w}_i \ (i=1,\ldots,d) \ \mbox{ and } \  \sum_{i=1}^d v_i < \sum_{i=1}^d w_i \\
&\Leftrightarrow & {v}_i < {w}_i \ (i=1,\ldots,d) \\
&\Leftrightarrow & \mathbf{v} \prec \mathbf{w},
\end{eqnarray*}
the $(d+1)$-partial order $\tilde{D}$ is the same digraph
as the $d$-partial order $D$.
Hence $G$ is the competition graph of the $(d+1)$-partial order $\tilde{D}$.
\end{proof}

Proposition~\ref{prop:02} can be shown by using Theorem~8 in \cite{dim2poset}.
We present a new proof from which Proposition~\ref{prop:dimub} also follows.

\begin{Prop}\label{prop:02}
For any graph $G$,
there exists positive integers $d$ and $k$
such that $G$ together with $k$ isolated vertices
is the competition graph of a $d$-partial order.
\end{Prop}

\begin{proof}
Let $n = |V(G)|$ and label the vertices of $G$ as $v_1, \ldots, v_n$.
Fix four real numbers $r_1$, $r_2$, $r_3$, and $r_4$
such that $r_1 < r_2 < r_3 < r_4$.
We define a map $\phi:V(G) \to \mathbb{R}^{n}$ by
\begin{align*}
\phi(v_i)_j =
	\begin{cases}
	r_2 & \text{if } j = i; \\
	r_4 & \text{if } j \neq i.
	\end{cases}
\end{align*}
We define a map $\psi: E(G) \to \mathbb{R}^{n}$ by
\begin{align*}
\psi(e)_k =
	\begin{cases}
	r_1 & \text{if } v_k \in e; \\
	r_3 & \text{if } v_k \notin e.
	\end{cases}
\end{align*}
Let $V= \{\phi(v_i) \mid v_i \in V(G) \} \cup \{\psi(e) \mid e \in E(G) \} \subseteq \mathbb{R}^{n}$.
Then $V$ defines an $n$-partial order $D$.
By definition, the in-neighborhood of the vertex $\psi(e) \in V$
is $\{\phi(v_i), \phi(v_j)\}$ for an edge $e = \{v_i,v_j\}$ of $G$ and
the in-neighborhood of the vertex $\phi(v) \in V$
is the empty set for a vertex $v$.
Thus the competition graph of $D$ is $G$
together with isolated vertices as many as $|E(G)|$.
Hence, by taking $d=n$ and $k=|E(G)|$, we complete the proof.
\end{proof}
Now we may introduce the following notion. Recall that for a finite subset $S$ of $\mathbb{R}^d$,
$D_S$ is the digraph defined by $V(D_S) = S$ and
$A(D_S) = \{(\mathbf{x},\mathbf{v}) \mid \mathbf{v}, \mathbf{x} \in S,
\mathbf{v} \prec \mathbf{x} \}$.
\begin{Defi}
For a graph $G$, we define
the \emph{partial order competition dimension} $\dim_{\text{{\rm poc}}}(G)$ of $G$
as the smallest nonnegative integer $d$
such that $G$ together with $k$ isolated vertices is the competition graph of $D$
for some $d$-partial order $D$ and some nonnegative integer $k$,
i.e.,
\[
\dim_{\text{{\rm poc}}}(G) := \min \{d \in \mathbb{Z}_{\geq 0} \mid
\exists k \in \mathbb{Z}_{\geq 0}, \exists S \subseteq \mathbb{R}^d,
\text{ s.t. }
G \cup I_k = C(D_S) \},
\]
where $\mathbb{Z}_{\geq 0}$ is the set of nonnegative integers and $I_k$ is a set of $k$ isolated vertices.
\end{Defi}

\begin{Rem}
Wu and Lu~\cite{dim2poset} introduced the notion of
the \emph{dimension-$d$ poset competition number} of a graph $G$,
denoted by $\mathcal{PK}^d(G)$,
which is defined to be the smallest nonnegative integer $p$
such that $G$ together $p$ additional isolated vertices
is isomorphic to the competition graph of a poset of dimension at most $d$
if such a poset exists, and to be $\infty$ otherwise.
By using $\mathcal{PK}^d(G)$, the partial order competition dimension of $G$
can be represented as
$\dim_{\text{{\rm poc}}}(G)=\min \{d \mid \mathcal{PK}^d(G) < \infty \}$.
Therefore $\mathcal{PK}^d(G) < \infty$ implies that $\dim_{\text{{\rm poc}}}(G) \le d$.
In this respect, Proposition~3.2 and the ``if" part of Proposition~3.10
may follow from their result presenting the dimension-$d$ poset competition numbers
of a complete graph with or without isolated vertices,
which are also shown to be trivially true in this paper.
\end{Rem}

\begin{Prop}\label{prop:dimub}
For any graph $G$, we have
$\dim_{\text{{\rm poc}}}(G) \leq |V(G)|$.
\end{Prop}

\begin{proof}
The proposition follows from
the construction of a $d$-partial order
in the proof of Proposition~\ref{prop:02}.
\end{proof}

For a graph $G$, the partial order competition dimension of an induced subgraph of $G$
is less than or equal to that of $G$.
To show this, we need the following lemmas.

\begin{Lem}\label{lem:subgraph}
Let $D$ be a digraph and let $G$
be the competition graph of $D$.
Let $S$ be a set of vertices.
The competition graph of
$D[S]$ is a subgraph of $G[S]$,
where $D[S]$ and $G[S]$ mean the subdigraph of $D$
and the subgraph of $G$, respectively, induced by $S$.
\end{Lem}

\begin{proof}
Let $H$ be the competition graph of
$D[S]$. Obviously, $V(H) = S$.
Take an edge $\{u,v\}$ of $H$.
By definition, there exists a vertex $w$ in $D[S]$ such that $(u,w)$ and $(v,w)$ are arcs of $D[S]$.
Consequently, $(u,w)$ and $(v,w)$ are arcs of $D$ and so $\{u,v\}$ is an edge of $G$.
Since $u,v \in S$, $\{u,v\}$ is an edge of $G[S]$. Hence $H$ is a subgraph of $G[S]$.
\end{proof}

\begin{Lem}\label{lem:outneighbor}
Let $D$ be a transitive acyclic digraph and let $G$
be the competition graph of $D$.
For any non-isolated vertex $u$ of $G$,
there exists an isolated vertex $v$ of $G$
such that $(u,v)$ is an arc of $D$.
\end{Lem}

\begin{proof}
Take a non-isolated vertex $u$ of $G$. Since $u$ has a neighbor $w$ in $G$,
$u$ and $w$ have a common out-neighbor in $D$. Take a longest directed path in $D$ originating from $u$.
We denote by $v$ the terminal vertex of the directed path.
Since $D$ is acyclic, the out-degree of $v$ in $D$ is zero and so $v$ is
isolated in $G$.
By the hypothesis that $D$ is transitive, $(u,v)$ is an arc of $D$.
\end{proof}

\begin{Prop}\label{prop:induced}
Let $G$ be a graph and let $H$ be an
induced subgraph of $G$. Then
$\dim_{\text{{\rm poc}}}(H) \leq \dim_{\text{{\rm poc}}}(G)$.
\end{Prop}

\begin{proof}
Let $d = \dim_{\text{{\rm poc}}}(G)$.
Then, there exists a $d$-partial order $D$ whose competition graph is
the disjoint union of $G$ and a set $J$ of isolated vertices.
Let $I$ be the set of isolated vertices in $G$.
Let $S = V(H) \cup I \cup J \subseteq \mathbb{R}^d$.
Then the digraph $D_S$ is a $d$-partial order. By Lemma~\ref{lem:subgraph},
the competition graph of $D_S$ is a subgraph of
$H \cup (I \setminus V(H)) \cup J$.

Now take two adjacent vertices $\mathbf{x}$ and $\mathbf{y}$ in $H$.
Then, since they are adjacent in $G$, there exists a vertex $\mathbf{v} \in V(D)$
such that $\mathbf{v}\prec\mathbf{x}$ and $\mathbf{v}\prec \mathbf{y}$.
If $\mathbf{v}$ is isolated in $G$ or $\mathbf{v} \in J$,
then $(\mathbf{x},\mathbf{v})$ and $(\mathbf{y},\mathbf{v})$ belong to $A(D_S)$ by definition.
Suppose that $\mathbf{v} \not\in I \cup J$. Then, by Lemma~\ref{lem:outneighbor},
there exists a vertex $\mathbf{w}$ in $I \cup J$
such that $\mathbf{w} \prec \mathbf{v}$.
Then $\mathbf{w}\prec\mathbf{x}$ and $\mathbf{w}\prec\mathbf{y}$
and so $(\mathbf{x},\mathbf{w})$ and $(\mathbf{y},\mathbf{w})$ belong to $A(D_S)$.
Thus $H \cup (I \setminus V(H)) \cup J$ is a subgraph of the competition graph of $D_S$
and we have shown that it is the competition graph of $D_S$.
Hence $\dim_{\text{{\rm poc}}}(H) \leq d$ and the proposition holds.
\end{proof}

It does not seem to be easy to compute the partial order competition dimension of a graph in general.
In this context, we first characterize graphs having small partial order competition dimensions.
In such a way, we wish to have a better idea to settle the problem.

Let $K_n$ denote the complete graph with $n$ vertices.

\begin{Prop}\label{prop:dim0}
Let $G$ be a graph.
Then, $\dim_{\text{{\rm poc}}}(G)= 0$ if and only if $G = K_1$.
\end{Prop}

\begin{proof}
The proposition immediately follows from the definition of $0$-partial order.
\end{proof}

\begin{Prop}\label{prop:dim1}
Let $G$ be a graph.
Then, $\dim_{\text{{\rm poc}}}(G)= 1$ if and only if
$G = K_{t+1}$ or
$G = K_t \cup K_1$ for some positive integer $t$.
\end{Prop}

\begin{proof}
First we remark that
if $D$ is a $1$-partial order with $V(D) \subseteq \mathbb{R}^1$
and $v^* \in V(D)$ is the minimum among $V(D)$,
then the competition graph of $D$ is the disjoint union of
a clique $V(D) \setminus \{v^*\}$
and an isolated vertex $v^*$.
Therefore, if $\dim_{\text{{\rm poc}}}(G) = 1$,
then we obtain
$G = K_{t+1}$ or
$G = K_t \cup K_1$ for some nonnegative integer $t$.
By Proposition \ref{prop:dim0}, $G \neq K_{1}$
and thus $t$ is a positive integer.

If $G = K_{t+1}$ or
$G = K_t \cup K_1$ for some positive integer $t$,
then we obtain $\dim_{\text{{\rm poc}}}(G) \leq 1$.
By Proposition \ref{prop:dim0}, since $G \neq K_{1}$,
we have $\dim_{\text{{\rm poc}}}(G) = 1$.
\end{proof}

\begin{Lem}\label{lem:iso}
Let $G$ be a graph such that $\dim_{\text{{\rm poc}}}(G) \geq 2$ and
let $G'$ be a graph obtained from $G$ by adding isolated vertices.
Then
$\dim_{\text{{\rm poc}}}(G)= \dim_{\text{{\rm poc}}}(G')$.
\end{Lem}

\begin{proof}
Let $a_1, \ldots, a_k$ be the isolated vertices added to $G$ to obtain $G'$.
Let $d = \dim_{\text{{\rm poc}}}(G)$.
Then $G$ can be made into  the competition graph a $d$-partial order $D$
by adding sufficiently many isolated vertices.
Since $d \geq 2$, we can locate $k$ points $\mathbf{a}_1, \ldots, \mathbf{a}_k$ in $\mathbb{R}^d$
corresponding to $a_1, \ldots, a_k$ so that
no two points in $\{\mathbf{a}_1, \ldots, \mathbf{a}_k \}$
are related by $\prec$
and that
no point in $V(D)$ and no point in $\{ \mathbf{a}_1, \ldots, \mathbf{a}_k \}$
are related by $\prec$.
Indeed, we can do this in the following way:
for $i=1, \ldots, k$,
let $\mathbf{a}_i$ be a point in $\mathbb{R}^d$ defined by
\[
(\mathbf{a}_i)_1 = r_1 + i; \quad
(\mathbf{a}_i)_2 = r_2 - i; \quad
(\mathbf{a}_i)_j = 0 \ (j=3,\ldots,d),
\]
where
$r_1 := \max\{ (\mathbf{v})_1 \mid \mathbf{v} \in V(D) \}$
and
$r_2 := \min\{ (\mathbf{v})_2 \mid \mathbf{v} \in V(D) \}$.
Then $G'$ is the competition graph of $D$ together with $\mathbf{a}_1, \ldots, \mathbf{a}_k$
and thus $\dim_{\text{{\rm poc}}}(G') \leq \dim_{\text{{\rm poc}}}(G)$.

Since $G$ is an induced subgraph of $G'$, by Proposition~\ref{prop:induced},
$\dim_{\text{{\rm poc}}}(G) \leq \dim_{\text{{\rm poc}}}(G')$.
Hence $\dim_{\text{{\rm poc}}}(G) = \dim_{\text{{\rm poc}}}(G')$.
\end{proof}

\begin{Prop}\label{prop:dim2}
Let $G$ be a graph.
Then, $\dim_{\text{{\rm poc}}}(G) = 2$
if and only if
$G$ is an interval graph which is neither $K_s$ nor $K_t \cup K_1$
for any positive intergers $s$ and $t$.
\end{Prop}

\begin{proof}
Suppose that $\dim_{\text{{\rm poc}}}(G) = 2$.
By Theorem \ref{dpo},
$G$ is an interval graph.
By Propositions \ref{prop:dim0} and \ref{prop:dim1},
$G$ is neither $K_s$ nor $K_t \cup K_1$ for any positive intergers $s$ and $t$.

Suppose that
$G$ is an interval graph which is
neither $K_s$ nor $K_t \cup K_1$ for any positive intergers $s$ and $t$.
By Theorem \ref{interval},
$\dim_{\text{{\rm poc}}}(G) \leq 2$.
By Propositions \ref{prop:dim0} and \ref{prop:dim1}
$\dim_{\text{{\rm poc}}}(G) \ge 2$.
Thus, $\dim_{\text{{\rm poc}}}(G) = 2$.
\end{proof}

\begin{Prop}\label{prop:cycle}
If $G$ is a cycle of length at least four, then
$\dim_{\text{{\rm poc}}}(G) = 3$.
\end{Prop}

\begin{proof}
Let $G$ be a cycle of length $n$ with $n \geq 4$.
Note that $G$ is not an interval graph.
By Propositions \ref{prop:dim0}, \ref{prop:dim1}, and \ref{prop:dim2},
we have $\dim_{\text{{\rm poc}}}(G) \geq 3$.
Let $\mathcal{F}$ be the family of $n$ closed triangles given in Figure~\ref{dimcycle}.
\begin{figure}
\begin{center}
\includegraphics[height=5cm]{dimcycle.eps}
\end{center}
\caption{A family of homothetic equilateral closed triangles}
\label{dimcycle}
\end{figure}
Then the intersection graph of $\mathcal{F}$ is the cycle of length $n$.
By Theorem~\ref{thm:closed} with $d=3$, $G$ together with sufficiently many isolated vertices
is the competition graph of a $3$-partial order.
Thus $\dim_{\text{{\rm poc}}}(G) \leq 3$.
Hence $\dim_{\text{{\rm poc}}}(G) = 3$.
\end{proof}

\begin{Thm}
If a graph $G$ contains an induced cycle of length at least four,
then $\dim_{\text{{\rm poc}}}(G) \geq 3$.
\end{Thm}

\begin{proof}
The theorem follows from Propositions~\ref{prop:induced} and~\ref{prop:cycle}.
\end{proof}

\begin{Thm}\label{thm:tree}
Let $T$ be a tree.
Then $\dim_{\text{{\rm poc}}}(T) \leq 3$,
and the equality holds if and only if $T$
is not a caterpillar.
\end{Thm}

\begin{proof}
By Theorem~\ref{thm:closed} with $d=3$, we need to show that
there exists a family of homothetic equilateral closed triangles in $\mathbb{R}^2$ whose intersection graph is $T$.
As a matter of fact,
it is sufficient to find such a family in the $xy$-plane
with the base of each triangle parallel to the $x$-axis.
We call the vertex of a triangle which is opposite to the base the \emph{apex} of the triangle.
We show the following stronger statement
by induction on the number of vertices:
\begin{quote}
For a tree $T$ and a vertex $v$ of $T$,
there exists a family $\mathcal{F}^T_v := \{ \triangle(x) \mid x \in V(T)\}$
of homothetic equilateral closed triangles whose intersection graph is $T$ such that,
for any vertex $x$ distinct from $v$, the apex
and the base of $\triangle(x)$ are below the apex and the base of $\triangle(v)$, respectively.
\end{quote}
We call the family $\mathcal{F}^T_v$ in the above statement
a \emph{good family} for $T$ and $v$.

If $T$ is the tree having exactly one vertex, then the statement is vacuously true.
Assume that the statement holds for any tree on $n-1$ vertices, where $n \geq 2$.
Let $T$ be a tree with $n$ vertices.
We fix a vertex $v$ of $T$ as a root.
Let $T_1, \ldots, T_k$ $(k \geq 1)$ be the connected components of $T - v$.
Then $T_1, \ldots, T_k$ are trees.
For each $i = 1, \ldots, k$,
$T_i$ has exactly one vertex, say $w_i$, which is a neighbor of $v$ in $T$.
We take $w_i$ as a root of $T_i$.
By the induction hypothesis,
there exists a good family $\mathcal{F}^{T_i}_{w_i}$ for $T_i$ and $w_i$
for each $i = 1, \ldots, k$.
Preserving the intersection or the non-intersection of two triangles in $\mathcal{F}^{T_i}_{w_i}$
for each $i=1, \ldots, k$,
we may translate the triangles in
$\mathcal{F}^{T_1}_{w_1} \cup \cdots \cup \mathcal{F}^{T_k}_{w_k}$
so that the apexes of $\triangle(w_1)$, $\ldots$, $\triangle(w_k)$ are on the $x$-axis
and any two triangles from distinct families do not intersect.
Let $\delta_i$ be the distance between the apex of $\triangle(w_i)$ and the apex of a triangle
which is the second highest among the apexes of the triangles in $\mathcal{F}^{T_i}_{w_i}$.
Now we draw a triangle $\triangle(v)$ in such a way that
the base of $\triangle(v)$ is a part of the line
$y = -\frac{1}{2}\min \{ \delta_1, \ldots, \delta_k \}$
and long enough to intersect all of the triangles $\triangle(w_1), \ldots, \triangle(w_k)$.
Then the family
$\mathcal{F}^{T}_{v} := \mathcal{F}^{T_1}_{w_1} \cup \cdots \cup \mathcal{F}^{T_k}_{w_k}
\cup \{\triangle(v)\}$ is a good family for $T$ and $v$
and thus the statement holds.
Hence, $\dim_{\text{{\rm poc}}}(T) \leq 3$ for a tree $T$.

Since trees which are interval graphs are caterpillars,
the latter part of the theorem follows from
Propositions \ref{prop:dim0}, \ref{prop:dim1}, and \ref{prop:dim2}.
\end{proof}

\section{Concluding Remarks}

In this paper, we studied the competition graphs of $d$-partial orders
and gave a characterization by using homothetic open simplices.
Since any graph can be made into the competition graph of a $d$-partial order
for some positive integer $d$ by adding isolated vertices,
we introduced the notion of the partial order competition dimension of a graph.
We gave characterizations of graphs having partial order competition dimension $0$, $1$, and $2$.
We also showed that cycles and trees have
partial order competition dimension at most $3$.
It would be an interesting research problem
to characterize graphs $G$ having partial order competition dimension $3$.