The covering threshold of a directed acyclic graph by directed acyclic subgraphs (Q2112584)

Summary: Let \(H\) be a directed acyclic graph (dag) that is not a rooted star. It is known that there are constants \(c=c(H)\) and \(C=C(H)\) such that the following holds for \(D_n\), the complete directed graph on \(n\) vertices. There is a set of at most \(C\log n\) directed acyclic subgraphs of \(D_n\) that covers every \(H\)-copy of \(D_n\), while every set of at most \(c\log n\) directed acyclic subgraphs of \(D_n\) does not cover all \(H\)-copies. Here this dichotomy is considerably strengthened. Let \(\vec{G}(n, p)\) denote the probability space of all directed graphs with \(n\) vertices and with edge probability \(p\). The fractional arboricity of \(H\) is \(a(H) = max \{\frac{|E(H')|}{|V(H')|-1}\}\), where the maximum is over all non-singleton subgraphs of \(H\). If \(a(H) = \frac{|E(H)|}{|V(H)|-1}\) then \(H\) is totally balanced. Complete graphs, complete multipartite graphs, cycles, trees, and, in fact, almost all graphs, are totally balanced. It is proven that: \begin{itemize} \item Let \(H\) be a dag with \(h\) vertices and \(m\) edges which is not a rooted star. For every \(a^\ast > a(H)\) there exists \(c^\ast = c^\ast (a^\ast , H) > 0\) such a.a.s. \(G \sim\vec{G}(n,n^{-1/a^\ast })\) has the property that every set \(X\) of at most \(c^\ast \log n\) directed acyclic subgraphs of \(G\) does not cover all \(H\)-copies of \(G\). Moreover, there exists \(s(H) = m/2 + O(m^{4/5}h^{1/5})\) such that the following stronger assertion holds for any such \(X\): there is an \(H\)-copy in \(G\) that has no more than \(s(H)\) of its edges covered by each element of \(X\). \item If \(H\) is totally balanced then for every \(0 < a^\ast < a(H)\), a.a.s. \(G \sim\vec{G}(n,n^{-1/a^\ast })\) has a single directed acyclic subgraph that covers all its \(H\)-copies. \end{itemize} As for the first result, note that if \(h=o(m)\) then \(s(H)=(1+o_m(1))m/2\) is about half of the edges of \(H\). In fact, for infinitely many \(H\) it holds that \(s(H)=m/2\), optimally. As for the second result, the requirement that \(H\) is totally balanced cannot, generally, be relaxed.