{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:02Z","timestamp":1753893782837,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.\r\nLet ${\\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:\r\n\r\nLet $H$ be a dag with $h$ vertices and $m$ edges which is not a rooted star. For every $a^* &gt; a(H)$ there exists $c^* = c^*(a^*,H) &gt; 0$ such a.a.s. $G \\sim {\\vec G}(n,n^{-1\/a^*})$ has the property that every set $X$ of at most $c^*\\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$.\r\nIf $H$ is totally balanced then for every $0 &lt; a^* &lt; a(H)$, a.a.s. $G \\sim {\\vec G}(n,n^{-1\/a^*})$ has a single directed acyclic subgraph that covers all its $H$-copies.\r\n\r\nAs 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.<\/jats:p>","DOI":"10.37236\/11275","type":"journal-article","created":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T10:05:31Z","timestamp":1671185131000},"source":"Crossref","is-referenced-by-count":0,"title":["The Covering Threshold of a Directed Acyclic Graph by Directed Acyclic Subgraphs"],"prefix":"10.37236","volume":"29","author":[{"given":"Raphael","family":"Yuster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2022,12,16]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p45\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p45\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T10:05:31Z","timestamp":1671185131000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i4p45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,16]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,10,6]]}},"URL":"https:\/\/doi.org\/10.37236\/11275","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,12,16]]},"article-number":"P4.45"}}