Transitivity check vs. Transitive Closure Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to determine if a digraph is transitive or not?
Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon&gt;0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying two boolean $n\times n$ matrices, and hence by a result of Fischer and Meyer from the 70s, this also implies an O($n^{3-\varepsilon/3}$) time algorithm for transitive closure. 

Suppose that you want to detect a triangle in an $n$ node $G$. We can now create the following graph $H$. $H$ is tripartite with partitions $I,J,K$ on $n$ nodes each. Here each node $x$ of $G$ has copies $x_I,x_J,x_K$ in the parts $I,J,K$. For each edge $(u,v)$ of $G$ add directed edges $(u_I,v_J)$ and $(u_J,v_K)$. For each nonedge $(u,v)$ of $G$ add the directed edge $(u_I,v_K)$. 

First, if $G$ contains a triangle $u,v,w$, then $H$ is not transitive. This is since the edges $(u_I,v_J),(v_J,w_K)$ are in $H$ but $(u_I,w_K)$ is not. Second, if $H$ is not transitive, then there must exist some directed path from some node $s$ to some node $t$ in $H$ such that $(s,t)$ is not a directed edge in $H$. However, the longest paths in $H$ have $2$ edges, and so any such path must be of the form $(u_I,v_J),(v_J,w_K)$ and $(u_I,w_K)$ is not in $H$, hence $u,v,w$ form a triangle in $G$.