%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{tikz, tikz-cd, tikz-3dplot}
\usetikzlibrary{positioning}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{patterns}
\usetikzlibrary{decorations.markings}

\tikzset{->-/.style={decoration={  markings,  mark=at position #1 with {\arrow{>}}},postaction={decorate}}}

\tikzset{dot/.style={fill,circle,inner sep=1pt,minimum size=1pt}}

\DeclareMathOperator*\supp{supp}
\DeclareMathOperator*\relint{relint}
\DeclareMathOperator\conv{conv}
\DeclareMathOperator\Hom{\overrightarrow{\text{Hom}}}
\DeclareMathOperator\oldHom{Hom}
\DeclareMathOperator\indeg{indeg}
\DeclareMathOperator\outdeg{outdeg}
\DeclareMathOperator\Poset{Poset}
\DeclareMathOperator\im{im}
\DeclareMathOperator\outN{\overrightarrow{N}}
\DeclareMathOperator\inN{\overleftarrow{N}}
\DeclareMathOperator\N{\overrightarrow{{\mathcal N}}}
\DeclareMathOperator\Nin{\overleftarrow{{\mathcal N}}}
\DeclareMathOperator\conn{conn}
\DeclareMathOperator\Aut{Aut}
\DeclareMathOperator\ch{{\chi}_o}

\newcommand\defi{\textit}  

\newcommand \bhom {\overset{\text{\tiny$\leftrightarrow$}}{\simeq}}
\newcommand \dhom {\overset{\text{\tiny$\rightarrow$}}{\simeq}} 
\newcommand \lhom {\overset{\text{\tiny$-$}}{\simeq}}
\newcommand \biI {\overset{\text{\tiny$\leftrightarrow$}}{I_n}}
\newcommand \dI {\overset{\text{\tiny$\rightarrow$}}{I_n}} 
\newcommand \bi {\overset{\text{\tiny$\leftrightarrow$}}}
\newcommand\T{\mathbb T}
\newcommand\inv{inv}
\newcommand\R{\mathbb{R}}
\newcommand\Z{\mathbb{Z}}
\newcommand\A{\mathcal{A}}
\newcommand\tA{\widetilde{\A}}
\newcommand\B{\mathcal{B}}
\newcommand\x{\mathbf{x}}
\newcommand\ck{\mathcal{K}}
\renewcommand\th{\widetilde{h}}
\renewcommand\k{\mathbb{K}}
\newcommand\diam{diam}
\newcommand\tourn{\overrightarrow{K_n}}
\newcommand\tourm{\overrightarrow{K_m}}
\newcommand\id{{\rm id}}
\newcommand\lk{{\rm lk}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{question}[thm]{Question}
%\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{example}[thm]{Example}

%\usepackage{lipsum}
%\usepackage{float}
\usepackage{graphicx,subcaption, epsfig}
\usepackage{tikz, tikz-cd, tikz-3dplot}
\usepackage{mathtools}
\usetikzlibrary{positioning}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{patterns}
\usetikzlibrary{decorations.markings}

\tikzset{->-/.style={decoration={  markings,  mark=at position #1 with {\arrow{>}}},postaction={decorate}}}

\tikzset{dot/.style={fill,circle,inner sep=1pt,minimum size=1pt}}


%% define your title in the usual way
\title[Homomorphism Complexes]{Homomorphism Complexes, Reconfiguration, \\
and Homotopy for Directed Graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~Dochtermann and A.~Singh]{Anton Dochtermann\thanks{\href{mailto:dochtermann@txstate.edu}{dochtermann@txstate.edu}.}\addressmark{1} \and Anurag Singh\thanks{\href{mailto:anurags@iitbhilai.ac.in}{anurags@iitbhilai.ac.in}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Texas State University \\ \addressmark{2}Department of Mathematics, Indian Institute of Technology (IIT) Bhilai}

%% put the date of submission here
\received{November 16, 2021}

%% leave this blank until submitting a revised version
\revised{March 11, 2022}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The neighborhood complex of a graph was introduced by Lov\'asz to provide topological lower bounds on chromatic number, and more general  homomorphism complexes of graphs were further studied by Babson and Kozlov.  Such `Hom complexes' are also related to reconfiguration problems as well as a notion of discrete homotopy. Here we initiate the detailed study of Hom complexes for directed graphs (digraphs). For any pair of digraphs $G$ and $H$ we consider the polyhedral complex $\overrightarrow{\text{Hom}}(G,H)$ that parametrizes the digraph homomorphisms $f \colon G \rightarrow H$. Such complexes have applications in the study of chains in graded posets and cellular resolutions of monomial ideals.

 We study topological properties of  $\overrightarrow{\text{Hom}}$ complexes and relate them to graph operations including products, adjunctions, and foldings. We introduce the notion of the neighborhood complex of a digraph and establish several properties regarding its topology, including its homotopy type as a $\overrightarrow{\text{Hom}}$ complex, dependence on directed bipartite subgraphs, and vanishing theorems for higher homology.  Inspired by the notion of reconfiguration for digraph colorings we study the connectivity of $\overrightarrow{\text{Hom}}(G,T_n)$ for $T_n$ a tournament, obtaining a complete answer for the case of transitive $T_n$. Finally we use paths in the internal hom objects of directed graphs to define various notions of homotopy, and discuss connections to the topology of $\overrightarrow{\text{Hom}}$ complexes.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{digraph, directed homomorphism complex, directed neighborhood complex, tournament, reconfiguration, homotopy}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{directed-hom.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above




\section{Introduction and background}\label{sec:intro}


The study of the chromatic number of graphs and more general graph homomorphisms is an active area of research (see for instance the recent monograph \cite{HelNes}). In his seminal proof of Kneser's conjecture Lov\'asz \cite{Lov}  introduced topological methods to the study of graph colorings via the neighborhood complex ${\mathcal N}(G)$ of a graph $G$.  Using a Borsuk--Ulam type argument he showed that the topology (connectivity) of ${\mathcal N}(G)$ provides a lower bound on $\chi(G)$, the chromatic number of $G$. 

It turns out that the neighborhood complex can be recovered (up to homotopy) as a special case of a more general notion of a \emph{homomorphism complex} $\oldHom(T,G)$, parametrizing all graph homomorphisms from $T$ to $G$ (with ${\mathcal N}(G)$ being the special case that $T = K_2$).  Details of this construction were worked out by Babson and Kozlov in \cite{BabKozCom}. Since these original works, several authors have studied homomorphism complexes and their applications to various combinatorial problems.  We refer to \cite{DocSin} for an overview of these developments.



 
As Kozlov \cite{KozCom} has pointed, one can define a \emph{Hom complex} in any category where there is notion of a \emph{multihomomorphism} between objects. In \cite{MatMor} Matsushita considered Hom complexes of `$r$-sets', which include hypergraphs and other generalizations of graphs.  He showed how such complexes can be modeled by simplicial sets and how many results from Hom complexes of graphs, including the $\times$-homotopy theory of \cite{DocHom}, can be extended to this setting.

In this work we apply these ideas to the class of \emph{directed} graphs (or digraphs for short).  For two digraphs $G$ and $H$ we consider the complex $\Hom(G,H)$ that parametrizes homomorphisms $f \colon G \rightarrow H$.  We will see that many of the categorical properties of such complexes that were satisfied in the undirected setting carry over to this context. Some of our results follow directly from the general theory of homomorphism complexes alluded to above, but in many cases we require new tools and constructions that seem specific to the directed graph setting.  At the same time we will see that the $\Hom$ complexes of digraphs exhibit behavior that is not seen in the undirected setting, providing insight into the nuances of the category of directed graphs.

We consider homomorphism complexes of digraphs to be a natural area of study in its own right, but we see how these concepts also connect to several other areas of existing research.  For instance in \cite{BraHou} Braun and Hough study a morphism complex associated to maximal chains in a graded poset.  These complexes can be recovered as $\Hom(T,G(P))$ complexes of directed graphs by considering the Hasse diagram $G(P)$ of the underlying poset $P$, and choosing $T$ to be a directed path.  

%Hence our complex $\Hom(G,H)$ for arbitrary directed graphs $G$ and $H$ generalize this construction. 

Homomorphism complexes of directed graphs also make an appearance in commutative algebra.  In \cite{DocEng} the first author and Engstr\"om showed that minimal resolutions of the class of \emph{cointerval} monomial ideals are supported on complexes that can be described as digraph homomorphism complexes.   The idea of using homomorphism complexes to describe resolutions of monomial ideals was further investigated by Braun, Browder, and Klee in \cite{BraBroKle}, where they considered ideals defined by nondegenerate morphisms between simplicial complexes.   It is our hope that a thorough understanding of homomorphism complexes of digraphs may lead to further applications of this kind.

In addition, the $1$-skeleton of $\Hom(G,H)$ provides a natural model to study \emph{reconfiguration} questions regarding homomorphisms of directed graphs.  In many areas of combinatorics, one is interested in moving among solutions to a given problem via  a \emph{reconfiguration graph}. This has practical applications when exact counting of solutions is not possible in reasonable time, in which case Markov chain simulation can be used. For these questions the connectedness, diameter, realizability, and algorithmic properties of the configuration graph are typically studied (see \cite{MynNas} for a survey). In our context a pair of homomorphisms of directed graphs $f,g \colon G \rightarrow H$ will be considered adjacent if $f$ and $g$ agree on all but one vertex, defining a reconfiguration graph that corresponds to the $1$-skeleton of $\Hom(G,H)$. For undirected graphs the connectivity and diameter of this graph are well studied with many results and open questions, but it seems that the analogous questions for digraphs have not been explored.

Finally, the connectivity and higher topology of $\Hom(G,H)$ is also a natural place to consider a notion of \emph{homotopy} for directed graphs.   For any two digraphs $G$ and $H$ the 0-cells of $\Hom(G,H)$ are given by the homomorphisms $G \rightarrow H$, and hence paths in the 1-skeleton of $\Hom(G,H)$ provide a natural notion of homotopy between them.  This perspective was investigated for undirected graphs by the first author in \cite{DocHom} and with Schultz in \cite{DocSch}, where the resulting notion was called $\times$-homotopy.  In both the undirected and directed setting, homotopy can be described by certain paths in the exponential graph $H^G$, and can also be recovered via a certain `cylinder' object.  For digraphs we see that $H^G$ is itself a directed graph, and there is an additional subtlety regarding which notion of path in $H^G$ one considers. This leads to a hierarchy of homotopies which relate to homomorphism complexes and other topological constructions, and also connect to existing theories from the literature (see for instance \cite{BBDL} and \cite{GLMY}).
 
 

\section{Definitions and examples}\label{sec:definitions}

\subsection{The category of directed graphs and \texorpdfstring{$\Hom$}{h} complexes} \label{sec:graphs}

For us a \defi{directed graph} (or \defi{digraph}) $G = (V(G), E(G))$ consists of a finite vertex set $V(G)$ and an edge set $E(G) \subseteq V(G) \times V(G)$.  Hence our digraphs have at most one directed edge from any vertex to another, and may have loops $(v,v)$.  Also note that we allow both $(v,w) \in E(G)$ and $(w,v) \in E(G)$ (in which we have a \emph{bidirected edge}). If $G$ is a digraph we let $G^{\text{\tiny}{o}}$ denote the subgraph of $G$ induced on the set of looped vertices. If $(v,w)$ is an edge in $G$ we will often write $v \sim w$ and say that `$v$ is adjacent to $w$'. If $G$ is a digraph and $v \in V(G)$ we define the \defi{out-neighborhood} and \defi{in-neighborhood} of $v$ as
\[\outN_G(v) = \{w \in V(G): (v,w) \in E(G)\},\]
\[\inN_G(v) = \{w \in V(G): (w,v) \in E(G)\}.\]

For any two directed graphs $G$ and $H$ a \defi{(digraph) homomorphism} is a vertex set mapping $f \colon V(G) \rightarrow V(H)$ that preserves adjacency, so that if $(x,y) \in E(G)$ we have $(f(x), f(y)) \in E(H)$. We let $\Hom_0(G,H)$ denote the set of all directed graph homomorphisms from $G$ to $H$. 
 
If $G$ and $H$ are directed graphs the (categorical) \defi{product} $G \times H$ is the directed graph with vertex set $V(G \times H) = V(G) \times V(H)$ and with adjacency given by $((g,h), (g^\prime, h^\prime)) \in E(G \times H)$ if $(g, g^\prime) \in E(G)$ and $(h, h^\prime) \in E(H)$.   Given directed graphs $G$ and $H$ the \defi{exponential graph} $H^G$ is the digraph with vertex set given by all vertex set mappings $f \colon V(G) \rightarrow V(H)$ with adjacency given by $(f,g)$ is a directed edge if whenever $(v,v^\prime) \in E(G)$ we have $(f(v), g(v^\prime)) \in E(H)$.  With this definition one can check that for any digraphs $G$, $H$, and $K$, we have a natural bijection of sets
\[\varphi: \Hom_0(G \times H, K) \xrightarrow{\cong} \Hom_0(G, K^H).\]
%\noindent
%Here a homomorphism $f:G \times H \rightarrow K$ is sent to $\varphi(f) \colon G \rightarrow K^H$, where $\varphi(f)(g)(h) = f(g,h)$ for any $g \in G$ and $h \in H$.



We next turn to the main definition of the paper.   For this we follow closely the construction of the Hom complex of undirected graphs as studied in \cite{BabKozCom}. Here if $G$ and $H$ are directed graphs we define a \defi{multihomomorphism} to be a map $\alpha \colon V(G) \rightarrow 2^{V(H)} \backslash \{\emptyset\}$ such that if $(v,w) \in E(G)$ we have $\alpha(v) \times \alpha(w) \subseteq E(H)$.  We let $\Delta^{V(H)}$ denote the simplex whose vertex set is $V(H)$, and use $C(G,H)$ to denote the polyhedral complex given by the direct product $\prod_{x \in V(G)} \Delta^{V(H)}$. The cells of $C(G,H)$ are given by direct products of simplices $\prod_{x \in V(G)} \sigma_x$.

\begin{defn}
Suppose $G$ and $H$ are directed graphs. Then \defi{$\Hom(G,H)$} is the polyhedral subcomplex of $C(G,H)$ with cells given by all multihomomorphisms $\alpha \colon V(G) \rightarrow 2^{V(H)} \backslash \{\emptyset\}$.  An element
\[\prod_{x \in V(G)} \sigma_x \in C(G,H)\]
\noindent
is in $\Hom(G,H)$ if and only if for all $(x,y) \in E(G)$ we have $(u,v) \in E(H)$ for any $u \in \sigma_x$ and $v \in \sigma_y$. In particular the vertex set of $\Hom(G,H)$ is given by the set $\Hom_0(G,H)$ of all directed graph homomorphisms $f \colon G \rightarrow H$.
\end{defn}

Note that for directed graphs $G$ and $H$ the set of all multihomomorphisms naturally forms a poset $P(G,H)$, where $\alpha \leq \beta$ if $\alpha(v) \subseteq \beta(v)$ for all $v \in V(G)$.  The poset $P(G,H)$ can be seen to be the face poset of the regular CW-complex $\Hom(G,H)$.  If we let $|P(G,H)|$ denote the geometric realization of the order complex of this poset we then have that $|P(G,H)|$ is the \emph{barycentric subdivision} of $\Hom(G,H)$, so that in particular $|P(G,H)|$ and $\Hom(G,H)$ are homeomorphic.  In many of our proofs we will think of $\Hom(G,H)$ as a poset, by which we mean the poset $P(G,H)$ described above. 

%Kozlov has pointed out that there is a notion of a `homomorphism complex' for any category of objects where the underlying morphisms are set maps satisfying some condition.  Cells are defined as set valued functions where each restriction is a morphism in the category, see \cite{KozCom} for more details. A notion of homomorphism complex for `$r$-sets' has been studied by Matsushita in \cite{MatMor}, and we use some results from this work.


%If $G$ and $H$ are directed graphs we let $\overline{G}$ and $\overline{H}$ denote the underlying undirected graphs.  We note that $\Hom(G,H) \subset \oldHom(\overline{G},\overline{H})$, since an element $\alpha \in \Hom(G,H)$ is in particular a multihomomorphism of the underlying undirected graphs. 

We note that we can recover any complex $\oldHom(G,H)$  of \emph{undirected} graphs via our construction in the `usual' way of embedding graphs into the category of directed graphs.   Namely, given undirected graphs $G$ and $H$ we construct directed graphs $\widehat{G}$ and $\widehat{H}$ where for each edge in the underlying graph we introduce a bidirected edge (a directed edge in each direction). One can then see that $\Hom(\widehat{G}, \widehat{H}) = \oldHom(G,H)$.  Hence the construction of $\Hom$ complexes for digraphs is in particular a generalization of the theory for graphs. We also point that if $P$ and $Q$ are graded posets then a \emph{strictly} order preserving poset map $P \rightarrow Q$ can be thought of as a homomorphism of directed graphs $G(P) \rightarrow G(Q)$, where $G(P)$ is the Hasse diagram of $P$ thought of as a directed graph.  Hence our construction of $\Hom$ complexes for directed graphs generalizes the work of Braun and Hough in \cite{BraHou}, where the topology of complexes of maximal chains in a graded poset is studied. 


Inspired by constructions in the undirected setting, we also introduce notions of \emph{directed neighborhood complexes} as follows.


\begin{defn}\label{def:neighbor}
Suppose $G$ is a directed graph.  The \defi{out-neighborhood complex} $\N(G)$ is the simplicial complex on vertex set $\{v \in V(G): \mathrm{indeg}(v)>0\}$, with facets given by the out neighborhoods $\outN_G(v)$ for all $v \in V(G)$.


The \defi{in-neighborhood complex} $\overleftarrow{\mathcal{N}}(G)$ has vertex set $\{v \in V(G): \mathrm{outdeg}(v)>0\}$, and facets given by the in-neighborhoods $\inN_G(v)$ for all $v \in V(G)$.
\end{defn}

\begin{figure}[h]
\begin{subfigure}[]{0.3\textwidth}
    \centering
    \begin{tikzpicture}
\node (a) at (0,0) {1};
\node (b) at (0,-2) {2};
\node (c) at (2,0) {3};
\node (d) at (2,-2) {4};
\node (e) at (-1,-1.25) {5};
\draw[->-=.7] (a)--(b);
\draw[->-=.73] (c)--(a);
\draw[->-=.7] (c)--(b);
\draw[->-=.7] (d)--(a);
\draw[->-=.73] (c)--(d);
\draw[->-=.7] (e)--(a);
\draw[->-=.7] (e)--(c);
\draw[->-=.7] (e)--(d);
\draw[->-=.7] (b)--(d);
%\draw[->] (b) edge (d) (c) edge (d);
\end{tikzpicture}
\caption{$G$}
\end{subfigure}
\begin{subfigure}[]{0.3\textwidth}
    \centering
     \begin{tikzpicture}[scale=1.3]
   % NODES
    
   \pattern[pattern=north east lines,opacity=0.5] (0.0,  0.0)--(-0.9,-0.5)--(1.5, -0.5)--cycle;
   \pattern[pattern=north west lines,opacity=0.5] (-0.5, -1.5)--(-0.9,-0.5)--(1.5, -0.5)--cycle;
   %\fill[fill=gray!20] (0.0,  0.0)--(-1.0, -1.5)--(1.0, -1.5);
  \path[draw] (0.0,  0.0)--(-0.9,-0.5);
  \path[draw] (-0.9,-0.5)--(1.5, -0.5);
  \path[draw] (0.0,  0.0)--(1.5, -0.5);
  \path[draw] (-0.5, -1.5)--(-0.9,-0.5);
  \path[draw] (-0.5, -1.5)--(1.5, -0.5);
  
  \node[dot] (a) at ( 0.0,  0.0) {};
  \node[dot] (b) at (-0.5, -1.5) {};
 % \node[dot] (c) at ( 1.0, -1.5) {};
  \node[dot] (e) at ( 1.5, -0.5) {};
  \node[dot] (f) at (-0.9,-0.5) {};
   \node[inner sep=0pt] () at ( -0.1,  0.2) {{$3$}};
   \node[inner sep=0pt] () at ( -0.7,  -1.5) {{$2$}};
   %\node[inner sep=0pt] () at ( 1.2,  -1.55) {{$5$}};
   \node[inner sep=0pt] () at ( 1.5,  -0.25) {{$4$}};
   \node[inner sep=0pt] () at ( -1.1,  -0.5) {{$1$}};
   \end{tikzpicture}
    \caption{$\N(G)$}
\end{subfigure}
\begin{subfigure}[]{0.3\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.3]
   % NODES
    
   \pattern[pattern=north east lines,opacity=0.5] (0.0,  0.0)--(-0.5, -1.5)--(1.0, -1.5)--cycle;
   \pattern[pattern=north west lines,opacity=0.5] (0.0,  0.0)--(1.5, -0.5)--(1.0, -1.5)--cycle;
   %\fill[fill=gray!20] (0.0,  0.0)--(-1.0, -1.5)--(1.0, -1.5);
   \path[draw] ( 0.0,  0.0)--(-0.5, -1.5);
   \path[draw] (-0.5, -1.5)--(1.0, -1.5);
   \path[draw] ( 0.0,  0.0)--(1.0, -1.5);
   \path[draw] ( 0.0,  0.0)--(1.5, -0.5);
   \path[draw] (1.0, -1.5)--(1.5, -0.5);
   \path[draw] ( 0.0,  0.0)--(-0.9,-0.5);
   
   \node[dot] (a) at ( 0.0,  0.0) {};
   \node[dot] (b) at (-0.5, -1.5) {};
   \node[dot] (c) at ( 1.0, -1.5) {};
   \node[dot] (e) at ( 1.5, -0.5) {};
   \node[dot] (f) at (-0.9,-0.5) {};
   \node[inner sep=0pt] () at ( -0.1,  0.2) {{$3$}};
   \node[inner sep=0pt] () at ( -0.7,  -1.5) {{$2$}};
   \node[inner sep=0pt] () at ( 1.2,  -1.55) {{$5$}};
   \node[inner sep=0pt] () at ( 1.5,  -0.25) {{$4$}};
   \node[inner sep=0pt] () at ( -1.1,  -0.5) {{$1$}};
   \end{tikzpicture}
    \caption{$\Nin(G)$}
\end{subfigure}
   \caption{A graph $G$, along with its out- and in-neighborhood complexes.}\label{fig:exampleofnbdcomplex}
   \label{fig:outcomplex}
\end{figure}



\subsubsection{Examples}

We next discuss some examples of $\Hom$ complexes.   Here we let $\overrightarrow{L}_n$, $\overrightarrow{C}_n$ and $\tourn$ denote the directed path graph $1\rightarrow 2\rightarrow \cdots \rightarrow n$, directed cycle graph $1\rightarrow 2\rightarrow \cdots \rightarrow n\rightarrow 1$, and the transitive $n$-tournament, respectively.  We have the following easy observations. 
\begin{itemize}
\item $\Hom(\overrightarrow{L}_r, \overrightarrow{L}_s)$ is a disjoint union of $s-r+1$ points if $s\geq r$, and is empty otherwise.

\item $\Hom(\overrightarrow{C}_r, \overrightarrow{C}_s)$ is a disjoint union of $s$ points if $s$ divides $r$, and is empty otherwise.

\item $\Hom(\overrightarrow{K}_{n-1},\tourn)$ is a path on $n$ vertices.
\end{itemize}


\begin{figure}[h]
\begin{subfigure}[]{0.4\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.2]
\node[dot] (a) at (-0.75,0) {};
\node[dot] (b) at (0.75,0) {};
\node[dot] (c) at (1.35,1.1) {};
\node[dot] (d) at (0.75,2.2) {};
\node[dot] (e) at (-0.75,2.2) {};
\node[dot] (f) at (-1.35,1.1) {};
 \draw[->-=.85] (a)--(d);
 \draw[->-=.85] (b)--(a);
 \draw[->-=.85] (c)--(a);
 \draw[->-=.85] (e)--(a);
 \draw[->-=.85] (f)--(a);
 \draw[->-=.85] (b)--(e);
 \draw[->-=.85] (c)--(b);
 \draw[->-=.85] (d)--(b);
 \draw[->-=.85] (f)--(b);
 \draw[->-=.85] (d)--(c);
 \draw[->-=.85] (e)--(c);
 \draw[->-=.85] (f)--(c);
 \draw[->-=.85] (e)--(d);
 \draw[->-=.85] (f)--(d);
 \draw[->-=.85] (f)--(e);
\end{tikzpicture}\vspace{0.2cm}
    \caption*{$T_6$}\label{fig:T6}
\end{subfigure}
\begin{subfigure}[]{0.35\textwidth}
    \centering
    \begin{tikzpicture}[scale=1]
   \pattern[pattern=north west lines,opacity=0.6] (0,0) -- (1.5,0)  -- (0.75,1) --cycle;
   \pattern[pattern=north west lines,opacity=0.6] (0,2) -- (1.5,2)  -- (0.75,1) --cycle;
   
   \draw (0,0) node[dot] {}  -- (1.5,0) node[dot] {}  -- (0.75,1) node[dot] {}  --cycle;
   \draw (0,2) node[dot]{}-- (1.5,2) node[dot]{}  -- (0.75,1)node[dot]{} --cycle;
   \draw (2,2.5) node[dot]{}-- (1.5,2) -- (2,1.5) node[dot]{};
   \draw (0.25,1) node[dot]{}-- (0.75,1)  (-0.25,1.5) node[dot]{} -- (0,2)-- (-0.75,2) node[dot]{} -- (-1.5, 1) node[dot]{} -- (-0.75,0) node[dot]{}-- (0,0) (1.5,0)-- (2,0) node[dot]{}-- (2.5,0.5) node[dot]{};
   \draw (-0.75,2)-- (-1.25,2.5) node[dot]{} (-0.75,0)-- (-1.25,-0.5) node[dot]{};
   \end{tikzpicture}\vspace{0.2cm}
    \caption*{$\Hom(\overrightarrow{K}_{3},T_6)$}\label{fig:k3t6}
    \end{subfigure}
    \caption{The tournament $T_6$ and its complex of morphisms from the acyclic $3$-tournament.}\label{fig:example3}
    \end{figure}
    
\begin{figure}[h]
\begin{subfigure}[]{0.33\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.05]
\node[dot] (a) at (-0.75,0) {};
\node[dot] (b) at (0.65,-0.25) {};
\node[dot] (c) at (1.5,0.55) {};
\node[dot] (d) at (1.5,1.65) {};
\node[dot] (e) at (0.65,2.45) {};
\node[dot] (f) at (-0.75,2.2) {};
\node[dot] (g) at (-1.35,1.1) {};
 \draw[->-=.85] (a) node[anchor=east] {\tiny{1}} --(e);
 \draw[->-=.85] (a)--(f);
 \draw[->-=.85] (a)--(g);
 \draw[->-=.85] (b) node[anchor= north west] {\tiny{2}}--(a); 
 \draw[->-=.85] (c) node[anchor=west] {\tiny{3}} --(a);
 \draw[->-=.85] (d) node[anchor=west] {\tiny{4}}--(a);
 \draw[->-=.85] (c)--(b);
 \draw[->-=.85] (d)--(b);
 \draw[->-=.85] (e) node[anchor=south west] {\tiny{5}} --(b);
 \draw[->-=.85] (b)--(f);
 \draw[->-=.85] (b)--(g);
 \draw[->-=.85] (d)--(c);
 \draw[->-=.85] (e)--(c);
 \draw[->-=.85] (f) node[anchor=south east] {\tiny{6}} --(c);
 \draw[->-=.85] (c)--(g) node[anchor=east] {\tiny{7}} ;
 \draw[->-=.85] (e)--(d);
 \draw[->-=.85] (f)--(d);
 \draw[->-=.85] (g)--(d);
 \draw[->-=.85] (f)--(e);
 \draw[->-=.85] (g)--(e);
 \draw[->-=.85] (g)--(f);
\end{tikzpicture}\vspace{0.05cm}
    \caption*{$T_7$}\label{fig:t71}
\end{subfigure}
\begin{subfigure}[]{0.66\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.01]
    
    \pattern[pattern=north east lines,opacity=0.5] (-0.7,2) -- (1.4,-1)  -- (8.4,-1)--(8.4,2) --cycle;
    
   \draw (-0.7,2) node[dot] {} node[anchor=east] {\tiny{0,4,1}} \foreach \x in {0,0.7,...,7.7} {
            -- (\x,2) node[dot] {}   } -- (8.4,2) node[dot] {} node[anchor=west] {\tiny{6,3,0}};
   \draw (1.4,-1) node[dot] {} node[anchor=east] {\tiny{6,3,0}} \foreach \x in {2.1,2.8,...,7.7} {
            -- (\x,-1) node[dot] {}   }-- (8.4,-1) node[dot] {} node[anchor=west] {\tiny{0,4,1}};
            
    \draw \foreach \x in {1.4,2.1,2.8,...,8.4} {  (\x,-1)  -- (\x,0) node[dot] {} -- (\x,1) node[dot] {}--(\x,2)
       (\x,-1)--(\x-0.7,0) node[dot] {} --(\x-1.4,1) node[dot] {} --(\x-2.1,2) };
    \draw (0,1) node[anchor=east] {\tiny{6,4,1}} --(0,2) (0.7,0) node[anchor=east] {\tiny{6,3,1}}--(0.7,1)--(0.7,2) (8.4,0) node[anchor=west] {\tiny{6,4,1}} --(7.7,1)--(7.0,2) (8.4,1) node[anchor=west] {\tiny{6,3,1}}--(7.7,2);
   \end{tikzpicture}\vspace{0.2cm}
    \caption*{$\Hom(\overrightarrow{C}_{3},T_7)\cong$ M{\"o}bius strip}\label{fig:c3t71}
\end{subfigure}
   \caption{The tournament $T_7$ and its complex of morphisms from the $3$-cycle $\protect\overrightarrow{C}_3$.}\label{fig:example4}
\end{figure}

%\item Let $O_6$ be the directed graph as shown in the figure below. Then $\Hom(\overrightarrow{C}_{3}, O_6)$ is disjoint union of three solid cubes.


\begin{figure}[h]
\begin{subfigure}[]{0.35\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.2]
\node[dot] (a) at (-0.75,0) {};
\node[dot] (b) at (0.75,0) {};
\node[dot] (c) at (1.5,1.1) {};
\node[dot] (d) at (0.75,2.2) {};
\node[dot] (e) at (-0.75,2.2) {};
\node[dot] (f) at (-1.5,1.1) {};
 \draw[->-=.85] (b)node[anchor=west] {\tiny{2}} --(a) node[anchor=east] {\tiny{1}};
 \draw[->-=.85] (e) node[anchor=east] {\tiny{4}} --(a);
 \draw[->-=.85] (a) -- (f) node[anchor=east] {\tiny{3}} ;
 \draw[->-=.85] (a)--(c) node[anchor=west] {\tiny{5}};
 \draw[->-=.85] (c)--(b);
 \draw[->-=.85] (b)--(d) node[anchor=west] {\tiny{6}};
 \draw[->-=.85] (f)--(b);
 \draw[->-=.85] (d)--(c);
 \draw[->-=.85] (c)--(e);
 \draw[->-=.85] (e)--(d);
 \draw[->-=.85] (d)--(f);
 \draw[->-=.85] (f)--(e);
\end{tikzpicture}\vspace{0.2cm}
    \caption*{$O_6$}\label{fig:o6}
\end{subfigure}
\begin{subfigure}[]{0.6\textwidth}
    \centering
    \begin{tikzpicture}[scale=0.8]
    \pattern[pattern=north east lines,opacity=0.5] (0,0) -- (2,-0.3) -- (2,1.7) -- (0,2) -- cycle;
    \pattern[pattern=north east lines,opacity=0.5] (0,2) -- (2,1.7) -- (2.5,2.2) -- (0.5,2.5) -- cycle;
    \pattern[pattern=north east lines,opacity=0.5] (2,-0.3) -- (2,1.7) -- (2.5,2.2) -- (2.5,0.2) -- cycle;
    
    \draw (0,0) node[dot]{} node[anchor=east] {\tiny{1,3,2}} -- (0,2) node[dot]{}node[anchor=east] {\tiny{1,5,2}}  -- (0.5,2.5)node[dot]{} node[anchor=south] {\tiny{1,5,4}}  -- (0.5,0.5)node[dot]{} node[anchor=north west] {\tiny{1,3,4}}  -- cycle;
    \draw (0,0) -- (2,-0.3) node[dot]{} node[anchor=north] {\tiny{6,3,2}} -- (2,1.7)node[dot]{} node[anchor=north east] {\tiny{6,5,2}} -- (0,2) -- cycle;
    \draw (0,0) -- (2,-0.3) -- (2.5,0.2) node[dot]{} node[anchor=west] {\tiny{6,3,4}} -- (0.5,0.5) -- cycle;[fill=green,fill opacity=0.5] (0.5,0.5) -- (0.5,2.5) -- (2.5,2.2)  -- (2.5,0.2) -- cycle;
    \draw (2,-0.3) -- (2,1.7) -- (2.5,2.2) -- (2.5,0.2) -- cycle;
    \draw (0,2) -- (2,1.7) -- (2.5,2.2)node[dot]{} node[anchor= south west] {\tiny{6,5,4}} -- (0.5,2.5) -- cycle;
    
    
    \pattern[pattern=north west lines,opacity=0.5] (4,0) -- (6,-0.3) -- (6,1.7) -- (4,2) -- cycle;
    \pattern[pattern=north west lines,opacity=0.5] (4,2) -- (6,1.7) -- (6.5,2.2) -- (4.5,2.5) -- cycle;
    \pattern[pattern=north west lines,opacity=0.5] (6,-0.3) -- (6,1.7) -- (6.5,2.2) -- (6.5,0.2) -- cycle;
    
    \draw (4,0) node[dot]{} node[anchor=north] {\tiny{2,1,3}} -- (4,2) node[dot]{}node[anchor=east] {\tiny{2,6,3}}  -- (4.5,2.5)node[dot]{} node[anchor=south] {\tiny{2,6,5}}  -- (4.5,0.5)node[dot]{} node[anchor=north west] {\tiny{2,1,5}}  -- cycle;
    \draw (4,0) -- (6,-0.3) node[dot]{} node[anchor=north] {\tiny{4,1,3}} -- (6,1.7)node[dot]{} node[anchor=north east] {\tiny{4,6,3}} -- (4,2) -- cycle;
    \draw (4,0) -- (6,-0.3) -- (6.5,0.2) node[dot]{} node[anchor=west] {\tiny{4,1,5}} -- (4.5,0.5) -- cycle;[fill=green,fill opacity=0.5] (4.5,0.5) -- (4.5,2.5) -- (6.5,2.2)  -- (6.5,0.2) -- cycle;
    \draw (6,-0.3) -- (6,1.7) -- (6.5,2.2) -- (6.5,0.2) -- cycle;
    \draw (4,2) -- (6,1.7) -- (6.5,2.2)node[dot]{} node[anchor= south west] {\tiny{4,6,5}} -- (4.5,2.5) -- cycle;
    
    
    \pattern[pattern=north east lines,opacity=0.5] (8,0) -- (10,-0.3) -- (10,1.7) -- (8,2) -- cycle;
    \pattern[pattern=north east lines,opacity=0.5] (8,2) -- (10,1.7) -- (10.5,2.2) -- (8.5,2.5) -- cycle;
    \pattern[pattern=north east lines,opacity=0.5] (10,-0.3) -- (10,1.7) -- (10.5,2.2) -- (10.5,0.2) -- cycle;
    
    \draw (8,0) node[dot]{} node[anchor=north] {\tiny{3,2,1}} -- (8,2) node[dot]{}node[anchor=east] {\tiny{3,4,1}}  -- (8.5,2.5)node[dot]{} node[anchor=south] {\tiny{3,4,6}}  -- (8.5,0.5)node[dot]{} node[anchor=north west] {\tiny{3,2,6}}  -- cycle;
    \draw (8,0) -- (10,-0.3) node[dot]{} node[anchor=north] {\tiny{5,2,1}} -- (10,1.7)node[dot]{} node[anchor=north east] {\tiny{5,4,1}} -- (8,2) -- cycle;
    \draw (8,0) -- (10,-0.3) -- (10.5,0.2) node[dot]{} node[anchor=west] {\tiny{5,2,6}} -- (8.5,0.5) -- cycle;[fill=green,fill opacity=0.5] (8.5,0.5) -- (8.5,2.5) -- (10.5,2.2)  -- (10.5,0.2) -- cycle;
    \draw (10,-0.3) -- (10,1.7) -- (10.5,2.2) -- (10.5,0.2) -- cycle;
    \draw (8,2) -- (10,1.7) -- (10.5,2.2)node[dot]{} node[anchor= south west] {\tiny{5,4,6}} -- (8.5,2.5) -- cycle;
   \end{tikzpicture}\vspace{0.2cm}
    \caption*{$\Hom(\overrightarrow{C}_{3},O_6)$}\label{fig:k3o6}
    \end{subfigure}
    \caption{The octahedral graph \texorpdfstring{$O_6$}{oct} and its complex of morphisms from the $3$-cycle $\protect\overrightarrow{C}_3$.}
    \label{fig:example5}
    \end{figure}


\section{Summary of results}
We next give an overview of our contributions, and refer to \cite{DocSin} for precise statements and proofs. 

\subsection{Structural results}
Our first collection of results involve structural properties of the $\Hom$ complexes that parallel those of homomorphism complexes in the undirected setting.  These include functorial properties of $\Hom(-,-)$ as well as graph operations that induce homotopy equivalences on the relevant complexes.  In this setting we will often describe our homotopy equivalences in terms of poset maps which induce \emph{strong homotopy equivalences} on the underlying topological spaces. We refer to \cite{DocSin} for further discussion. Our first result involves products and adjunctions.

\begin{thm}
For digraphs $A$, $B$, and $C$, we have strong homotopy equivalences
\begin{enumerate}
    \item $\Hom(A,B \times C) \simeq \Hom(A,B) \times \Hom(A,C)$;
    \item $\Hom(A \times B, C) \simeq \Hom(A,C^B).$
    \end{enumerate}
    \end{thm}
    
    
As an important consequence of the above we have $\Hom(G,H) \simeq \Hom({\bf 1}, H^G)$, where ${\bf 1}$ is the graph consisting of a single looped vertex.  This latter complex can be described as a \emph{clique complex} of a certain subgraph of $H^G$, we refer to \cite{DocSin} for details.

Our next result involves the notion of a folding in the digraph setting. Here if $v, w \in V(G)$ are vertices of a digraph $G$ with the property that $\outN_G(v) \subseteq \outN_G(w)$ and $\inN_G(v) \subseteq \inN_G(w)$ then we have a homomorphism $G \rightarrow G \backslash \{v\}$ given by $v \mapsto w$ (and $u \mapsto u$ for all $u \neq v$) called a \emph{(directed) folding}.
    
    \begin{thm}
If $G \rightarrow G\backslash \{v\}$ is a directed folding then for any digraph $H$ we have strong homotopy equivalences
\begin{enumerate}
    \item $\Hom(H,G) \simeq \Hom(H,G \backslash \{v\})$; 
   
    \item $\Hom(G \backslash \{v\}, H) \simeq \Hom(G,H)$.
\end{enumerate}
\end{thm}



\begin{example}
As an example of a folding we refer to Figure \ref{fig:example2}. Here we let $C_3^1$ denote the directed graph on vertex set $[4]$ and $E(C_3^1)=E(\overrightarrow{C}_{3})\sqcup \{(4,1)\}$.  Note that we have a directed folding $C_3^1 \rightarrow \overrightarrow{C}_{3}$.
\end{example}

\begin{figure}[h]
\begin{subfigure}[]{0.32\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.2]
\node[dot] (a) at (0,0) {};
\node[dot] (b) at (1.25,0.9) {};
\node[dot] (c) at (0.75,2.2) {};
\node[dot] (d) at (-0.75,2.2) {};
\node[dot] (e) at (-1.25,0.9) {};
 \draw[->-=.85] (b)--(a);
 \draw[->-=.85] (c)--(a);
 \draw[->-=.85] (a)--(d);
 \draw[->-=.85] (a)--(e);
 \draw[->-=.85] (c)--(b);
 \draw[->-=.85] (d)--(b);
 \draw[->-=.85] (b)--(e);
 \draw[->-=.85] (d)--(c);
 \draw[->-=.85] (e)--(c);
 \draw[->-=.85] (e)--(d);
\end{tikzpicture}\vspace{0.2cm}
    \caption*{$T_5$}\label{fig:T5}
\end{subfigure}
\begin{subfigure}[]{0.32\textwidth}
    \centering
    \begin{tikzpicture}[scale=1]
   \newdimen\R
    \R=1.5cm
   \draw (0:\R) node[dot] {}\foreach \x in {24,48,...,359} {
            -- (\x:\R) node[dot] {}
        } -- cycle (90:\R);
   
   \end{tikzpicture}\vspace{0.2cm}
    \caption*{$\Hom(\overrightarrow{C}_{3},T_5)$}\label{fig:c3t5}
\end{subfigure}
\begin{subfigure}[]{0.32\textwidth}
    \centering
    \begin{tikzpicture}[scale=0.9]
   \newdimen\R
    \R=1.3cm
    \newdimen\S
    \S=1.7cm
   \draw (0:\R) node[dot] {} -- (24:\R) node[dot] {} -- (48:\R) node[dot] {} -- (72:\R) node[dot] {} (96:\R) node[dot] {} -- (120:\R) node[dot] {} -- (144:\R) node[dot] {} -- (168:\R) node[dot] {} -- (192:\R) node[dot] {} -- (216:\R) node[dot] {} (240:\R) node[dot] {} -- (264:\R) node[dot] {} -- (288:\R) node[dot] {} (312:\R) node[dot] {} -- (336:\R) node[dot] {} -- (359:\R);
   
   \draw (240:\S) node[dot] {} -- (264:\S) node[dot] {} -- (288:\S) node[dot] {} -- (312:\S) node[dot] {} -- (336:\S) node[dot] {} -- (0:\S) node[dot] {} (24:\S) node[dot] {} -- (48:\S) node[dot] {} -- (72:\S) node[dot] {} -- (96:\S) node[dot] {} -- (120:\S) node[dot] {} -- (144:\S) node[dot] {} (168:\S) node[dot] {} -- (192:\S) node[dot] {} -- (216:\S) node[dot] {};
   
   \draw \foreach \x in {0,24,48,...,336} {
            (\x:\R)-- (\x:\S) } (216:\S) -- (240:\R);
   
   \pattern[pattern=north west lines,opacity=0.6] (24:\R)--(24:\S)--(48:\S)--(48:\R)--cycle;
   \pattern[pattern=north east lines,opacity=0.6] (48:\R)--(48:\S)--(72:\S)--(72:\R)--cycle;
   \pattern[pattern=north east lines,opacity=0.6] (96:\R)--(96:\S)--(120:\S)--(120:\R)--cycle;
   \pattern[pattern=north west lines,opacity=0.6] (120:\R)--(120:\S)--(144:\S)--(144:\R)--cycle;
   \pattern[pattern=north east lines,opacity=0.6] (168:\R)--(168:\S)--(192:\S)--(192:\R)--cycle;
   \pattern[pattern=north west lines,opacity=0.6] (192:\R)--(192:\S)--(216:\S)--(216:\R)--cycle;
   \pattern[pattern=north west lines,opacity=0.6] (240:\R)--(240:\S)--(264:\S)--(262:\R)--cycle;
   \pattern[pattern=north east lines,opacity=0.6] (264:\R)--(264:\S)--(288:\S)--(288:\R)--cycle;
   \pattern[pattern=north west lines,opacity=0.6] (312:\R)--(312:\S)--(336:\S)--(336:\R)--cycle;
   \pattern[pattern=north east lines,opacity=0.6] (336:\R)--(336:\S)--(0:\S)--(0:\R)--cycle;
   
   \end{tikzpicture}\vspace{0.2cm}
    \caption*{$\Hom(C_3^1,T_5)$}\label{fig:c4t5}
\end{subfigure}
\caption{The tournament $T_5$ and two of its (homotopy equivalent) $\Hom$ complexes.}
   \label{fig:example2}
\end{figure}    


The functorial properties of the $\Hom$ complexes also allow for a general obstruction theory for digraph homomorphisms in the spirit of the `topological lower bounds' on chromatic number discussed above.  In this context a natural example is given by an application of \emph{Dold's theorem} to the free ${\mathbb Z}_3$-action on the complexes $\Hom(\overrightarrow{C}_3,G)$ for various choices of $G$.  For example if $G$ is any digraph with the property that $\Hom(\overrightarrow{C}_3,G)$ is $2$-connected then $G$ does not admit a homomorphism into the graph $T_7$ depicted in Figure \ref{fig:example4}.  We again refer to \cite{DocSin} for more discussion.

\subsection{Topology of directed neighborhood complexes}

Our next results involve the topology of the  \emph{out-} and \emph{in-neighborhood complexes} $\N(G)$ and $ \Nin (G)$, as defined above. We refer to \cite{DocSin} for details and precise statements but we summarize our results here. Our first theorem compares the topology of the out- and in-neighborhood complexes of digraphs.

\begin{thm}
For any directed graph $G$ we have homotopy equivalences
\[\N(G) \simeq \Nin(G) \simeq \Hom(K_2, G).\]
\end{thm}

In \cite{DocSin} we provide three proofs of this theorem, including the observation that $\N(G)$ and $\Nin(G)$ can be viewed as dual nerves of a relation in a Dowker type construction.  We also prove that any simplicial complex can be recovered up to isomorphism as $\N(G)$ for some directed graph $G$.  This stands in contrast to the undirected setting, where the neighborhood complex must be homotopy equivalent to a space with a free ${\mathbb Z}_2$-action. 

Again motivated by results in the undirected setting, we next address the effect that directed bipartite subgraphs have on the topology of directed neighborhood complexes.   Here $\overrightarrow{K}_{m,n}$ is the graph with vertex set $[m] \cup [n]$ and with all directed edges $\{(i,j):i \in [m], j \in [n]\}$.  We then have the following result, which extends an analogous property for neighborhood complexes of undirected graphs first established by Kahle in \cite{Kah}.


\begin{thm}
If a digraph $G$ does not contain a copy of $\overrightarrow{K}_{m,n}$ (for any $m+n = d$) then the complex $\N(G)$ admits a strong deformation retract onto a complex of dimension at most $d-3$.
\end{thm}

Our main result in this setting  is a vanishing theorem regarding the homology of the neighborhood complexes.  In what follows a digraph $G$ is \emph{simple} if for any pair of vertices $u,v \in V(G)$ we never have $(u,v) \in E(G)$ and $(v,u) \in E(G)$.  Also recall that a simplicial complex $X$ is \emph{$n$-Leray} if $\widetilde{H}_i(\N(G)) = 0$ for all $i \geq n$, and that this property holds for any induced subcomplex.  We then have the following.

\begin{thm}
If $G$ is a simple directed graph on at most $2n+2$ vertices then $\N(G)$ is $n$-Leray.
\end{thm}

 This result is tight in the sense that there exists a digraph $T_m$ on $m=2n+3$ vertices with $\N(T_m) \simeq \mathbb{S}^n$, see \cite{DocSin}.  In \cite{DocSin} we also discuss an operation on digraphs $G$ that has the effect of suspending (up to homotopy equivalence) the corresponding complex $\N(G)$.  This is a digraph analogue of the \emph{Mycielskian} $\mu(G)$ of an undirected graph $G$, and extends results of Csorba from \cite{Cso}.
 
%\begin{theorem}
%For any digraph $G$ we have a homotopy equivalence
  %  \[\N(M^3(G))  \simeq S (\N(G)).\]
%\end{theorem}


\subsection{Reconfiguration into tournaments}
Our next collection of results involve complexes of the form $\Hom(G,T_n)$, where $T_n$ is a \emph{tourmanent} (an orientation of the complete graph) on $n$ vertices.  Tournaments play an important role in digraph theory, and for instance homomorphisms $G \rightarrow T_n$ can be used to define a notion of \emph{oriented chromatic number} $\chi_o(G)$.  We are interested in properties of $\Hom(G,T_n)$ and how they compare to homomorphism complexes of undirected graphs. In particular the connectivity of $\Hom(G,T_n)$ is a natural place to study \emph{reconfiguration} questions as a digraph analogue of the well-studied question of mixings of (undirected) graph colorings. In this context one is interested in the connectivity and diameter of the ($1$-skeleton of the) complex $\Hom(G,T_n)$.


We mostly study the case that $T_n = \tourn$ is an \emph{acyclic} (or \emph{transitive}) tournament.  We note that in the undirected setting, the connectivity of even $\oldHom(G,K_3)$ is a subtle question (see \cite{CHJmixing}).  For the case of digraph homomorphisms into transitive tournaments we have a much more straightforward answer. Our main result in this setting is the following.

\begin{thm}
Let $\tourn$ denote the transitive tournament on $n$ vertices. Then for any digraph $G$ the complex $\Hom(G,\tourn)$ is empty or contractible. Furthermore, if $\Hom(G,\tourn)$ is nonempty then the diameter of its $1$-skeleton satisfies
\[\diam((\Hom(G,\overrightarrow{K_n}))^{(1)}) \leq |V(G)|.\]
\end{thm}


In the special case that $G = \tourm$ is itself a transitive tournament we can say more about the topology and polyhedral structure of $\Hom(\tourm, \tourn)$.  In particular we show that such complexes can be recovered as certain \emph{mixed subdivisions} of a dilated simplex $m\Delta^{n-m}$, and are hence homeomorphic to an $(n-m)$-dimensional ball for any $m \leq n$ (see Figure \ref{fig:example1}).


It is an open question to determine the possible homotopy types of $\Hom(G,T_n)$ for other choices of tournaments $T_n$. For instance does the topology of $\Hom(K_2,T_n) \simeq \N(T_n)$ say something about the combinatorial properties of $T_n$?  In \cite{DocSin} we show that any sphere ${\mathbb S}^n$ can be recovered up to homotopy type as $\N(T_n)$ for some choice of tournament $T_n$, but for instance we have yet to find an example of a neighborhood complex $\N(T_n)$ that has torsion in its homology. 


\begin{figure}[h]
%\captionsetup[subfigure]{labelformat=empty}
\begin{subfigure}[]{0.5\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.1]
   % NODES
   \pattern[pattern=north west lines, opacity=0.5] (0,0)--(1,0)--(1,-1)--(0,-1)--cycle;
   \pattern[pattern=north east lines, opacity=0.6] (0,0)--(1,0)--(0,1)--cycle;
   \pattern[pattern=north east lines, opacity=0.6] (2,-1)--(1,0)--(1,-1)--cycle;
   
   \path[draw] (0,0)node[dot] {} node[anchor=south east] {\tiny{$1,3$}} -- (1,0)node[dot] {} node[anchor=south west] {\tiny{$1,4$}} -- (1,-1) node[dot] {} node[anchor=north west] {\tiny{$2,4$}} -- (0,-1) node[dot] {} node[anchor=north east] {\tiny{$2,3$}}--cycle;
   \draw[] (0,0)--(0,1)node[dot] {} node[anchor=south] {\tiny{$1,2$}} --(1,0)-- (2,-1)node[dot] {} node[anchor=west] {\tiny{$3,4$}} --(1,-1);
   \end{tikzpicture}\vspace{0.25cm}
    \caption*{$\Hom(\overrightarrow{K}_{2},\overrightarrow{K}_{4})$}\label{fig:homk2k4}
\end{subfigure}
\begin{subfigure}[]{0.4\textwidth}
    \centering
    \begin{tikzpicture}[scale=0.85]
   % NODES
   \pattern[pattern=north west lines,opacity=0.5] (0,0) --(0,1) --(1,1)--(1,0) --cycle;
   
   \pattern[pattern=north east lines,opacity=0.6] (0,1)-- (1,1)--(1,2) --(0,2) --cycle;
   \pattern[pattern=north east lines,opacity=0.6] (1,1) --(1,0)-- (2,0) --(2,1) -- cycle;
   
%   \draw[pattern=north east lines, pattern color=blue] (0,0) rectangle (2,4);
   
   \pattern[pattern=north west lines,opacity=0.5] (1,2)--(1,1)--(2,1)-- cycle;
   
   \pattern[pattern=north west lines,opacity=0.5] (0,3)--(0,2)--(1,2)-- cycle;
   
   \pattern[pattern=north west lines,opacity=0.5] (2,0)--(3,0)--(2,1)-- cycle;
   
   \draw[] (0,0) node[dot] {} node[anchor=east] {\tiny{$2,3,4$}}--(1,0) node[dot] {} node[anchor=north]  {\tiny{$2,3,5$}} --(2,0)node[dot] {} node[anchor=north] {\tiny{$2,4,5$}}-- (3,0)node[dot] {} node[anchor=west] {\tiny{$3,4,5$}} --(2,1) node[dot] {} node[anchor=south west] {\tiny{$1,4,5$}}--(1,2)node[dot] {} node[anchor=south west] {\tiny{$1,2,5$}}--(0,3)node[dot] {} node[anchor=south] {\tiny{$1,2,3$}}--(0,2)--(0,1)--cycle;
   
   \draw (0,2)node[dot] {} node[anchor=east] {\tiny{$1,2,4$}} --(1,2)--(1,1)--(1,0);
   \draw (0,1)node[dot] {} node[anchor=east] {\tiny{$1,3,4$}}--(1,1) node[dot] {}--(2,1)--(2,0);
   \end{tikzpicture}\vspace{0.1cm}
    \caption*{$\Hom(\overrightarrow{K}_{3},\overrightarrow{K}_{5})$}\label{fig:homk3k5}
\end{subfigure}
   \caption{Examples of $\Hom$ complexes between acyclic tournaments.}
   \label{fig:example1}
\end{figure}




\subsection{Discrete homotopy for directed graphs}
Our last collection of results involves applications of $\Hom$ complexes to various notions of \emph{homotopy} for directed graphs.  Recall that the vertices of $\Hom(G,H)$ correspond to the graph homomorphisms $f \colon G \rightarrow H$. This naturally suggests the following.

\begin{defn}
Suppose $G$ and $H$ are digraphs and $f,g \colon G \rightarrow H$ are homomorphisms. Then $f$ is \emph{bihomotopic} to $g$ (written $f \bhom g$) if there exists a path from $f$ to $g$ in the complex $\Hom(G,H)$.
\end{defn}

Bihomotopy is a special case of the \emph{strong homotopy} of $r$-sets as developed by Matsushita \cite{MatMor} and is a digraph analogue of the $\times$-homotopy developed in \cite{DocHom}. We study properties of bihomotopy, including its relation to paths in exponential graphs and how the resulting notion of $\bhom$-equivalence of digraphs is characterized by the topology of $\Hom$ complexes.  This in particular leads to a digraph analogue of a result of Brightwell and Winkler from \cite{BriWinGibbs}, and more generally we have the following.


\begin{thm}\label{thm:bihomotopy}
Bihomotopy of digraphs satisfy the following properties.
\begin{enumerate}
    \item We have $f \bhom g$ if and only if there exists a bidirected path from $f$ to $g$ in $H^G$;
\item
Directed foldings $G \rightarrow G-v$ preserve bihomotopy type;

\item
$G \bhom {\bf 1}$ if and only if $\Hom(T,G)$ is connected for any digraph $T$.
\end{enumerate}
\end{thm}

We use other notions of paths in $H^G$ to define increasingly weaker notions of homotopy for digraph homomorphisms.  The existence of a \emph{directed} path in $H^G$ defines a notion of \emph{dihomotopy} $f \dhom g$, whereas a path in the underlying undirected graph of $H^G$ defines a \emph{line homotopy} $f \simeq g$.  Dihomotopy is an example of a `directed homotopy theory', whereas line homotopy is related to constructions of Grigor’yan, Lin, Muranov, and Yau from \cite{GLMY}.  

By definition we have the following hierarchy of homotopies.
\[f \bhom g \Rightarrow f \dhom g \Rightarrow f \lhom g.\]
\noindent
To see that these implications are strict we refer to Figure \ref{fig:directedhomotopy}.  Here a homomorphism $f \colon G \rightarrow H$ is denoted by $(f(a),f(b))$.  Note that $(0,1) \dhom (3,2)$ and $(0,1) \lhom (4,5)$.


 \begin{figure}[h]
\begin{subfigure}[]{0.2\textwidth}
\vspace{1.5cm}
    \centering
    
    \begin{tikzpicture}[scale=0.85]
\node (a) at (0,0) {a};
\node (b) at (2,0) {b};
\draw[->-=.5] (a) to [out=30,in=150,looseness=0.5] (b);
\draw[->-=.5] (b) to [out=210,in=330,looseness=0.5] (a);
% \draw[->] (b) edge (d) (c) edge (d);
\end{tikzpicture}
\vspace*{1.15cm}
\caption{The graph $G$}
\end{subfigure}
\begin{subfigure}[]{0.2\textwidth}
    \centering
    \begin{tikzpicture}[scale=0.85]
\node (a) at (0,0) {2};
\node (b) at (0,1.5) {0};
\node (c) at (2,1.5) {1};
\node (d) at (2,0) {3};
\node (e) at (0,-1.5) {4};
\node (f) at (2,-1.5) {5};

\draw[->- =.5] (b)--(a) node[midway,above right] {};
\draw[->- =.5] (c)--(d) node[midway,above right] {};
\draw[->-=.5] (b) to [out=30,in=150,looseness=0.3] (c);
\draw[->-=.5] (c) to [out=210,in=330,looseness=0.5] (b);
\draw[->-=.5] (a) to [out=30,in=150,looseness=0.3] (d);
\draw[->-=.5] (d) to [out=210,in=330,looseness=0.5] (a);
\draw[->- =.5] (e)--(a) node[midway,above right] {};
\draw[->- =.5] (f)--(d) node[midway,above right] {};
\draw[->-=.5] (e) to [out=30,in=150,looseness=0.3] (f);
\draw[->-=.5] (f) to [out=210,in=330,looseness=0.5] (e);
% \draw[->] (b) edge (d) (c) edge (d);
\end{tikzpicture}
\vspace{0.1cm}
\caption{The graph $H$}
\end{subfigure}
\begin{subfigure}[]{0.25\textwidth}
    \centering
    \vspace{0.5cm}
    \begin{tikzpicture}[scale=0.8]
\node (d) at (0,1.75) {{\tiny (0,1)}};
\node (e) at (1.5,.25) {{\tiny (2,3)}};
\node (f) at (0,.25) {{\tiny (1,0)}};
\node (g) at (1.5,1.75) {{\tiny (3,2)}};
\node (g) at (3,1.75) {{\tiny (4,5)}};
\node (g) at (3,0.25) {{\tiny (5,4)}};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (b) at (1.5,0) {};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (c) at (0,0) {};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (a) at (0,1.5) {};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (i) at (1.5,1.5) {};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (j) at (3,1.5) {};
\node[fill,circle,inner sep=1.5pt,minimum size=1pt] (k) at (3,0) {};
% \draw[->] (b) edge (d) (c) edge (d);
\end{tikzpicture}
\vspace{1cm}
\caption{$\Hom(G,H)$}
\end{subfigure}
\begin{subfigure}[]{0.33\textwidth}
    \centering
    \begin{tikzpicture}[scale=0.85]
\node (a) at (-2,2) {{\tiny (0,1)}};
\node (b) at (0,0) {{\tiny (2,3)}};
\node (c) at (-2,0) {{\tiny (1,0)}};
\node (d) at (0,2) {{\tiny (3,2)}};
\node (e) at (2,2) {{\tiny (4,5)}};
\node (f) at (2,0) {{\tiny (5,4)}};
\draw[->- =.5] (a)--(d) node[midway,above right] {};
\draw[->- =.5] (c)--(b) node[midway,above right] {};
\draw[->- =.5] (e)--(d) node[midway,above right] {};
\draw[->- =.5] (f)--(b) node[midway,above right] {};
\draw[->-=.5] (a) to [out=130,in=60,looseness=8] (a);
\draw[->-=.5] (b) to [out=130,in=60,looseness=8] (b);
\draw[->-=.5] (c) to [out=130,in=60,looseness=8] (c);
\draw[->-=.5] (d) to [out=130,in=60,looseness=8] (d);
\draw[->-=.5] (e) to [out=130,in=60,looseness=8] (e);
\draw[->-=.5] (f) to [out=130,in=60,looseness=8] (f);
% \draw[->] (b) edge (d) (c) edge (d);
\end{tikzpicture}
\vspace{0.1cm}
\caption{The graph $(H^G)^{\text{\tiny}{o}}$}
\end{subfigure}
   \caption{An illustration of the various homotopies.}\label{fig:directedhomotopy}
\end{figure}


From Theorem \ref{thm:bihomotopy} we have seen that the topology of the $\Hom$ complex characterizes bihomotopies of digraph homomorphisms, and allows for higher categorical constructions. In the case of line homotopy we conjecture that the  \defi{directed clique complex} of a digraph plays a similar role, see \cite{DocSin} for more details. In both cases this leads to a \emph{homology} theory for digraphs that is invariant under the relevant homotopy equivalence.  It is an open question to decide whether any of these notions of equivalence can be given the structure of a \emph{model category}.


\acknowledgements{We thank Nikola Mili\'evi\'c, Raphael Steiner and Hiro Tanaka for helpful conversations.}


\printbibliography


\end{document}




