论文标题
通过定向的无环子图的定向无环图的覆盖阈值
The covering threshold of a directed acyclic graph by directed acyclic subgraphs
论文作者
论文摘要
令$ h $为扎根恒星以外的定向无环图。众所周知，存在常数$ c（h）$和$ c（h）$，因此完整的有向图$ d_n $的以下内容保留。 $ d_n $的$ c \ log n $指导的循环子图覆盖了$ d_n $的每$ h $ -scopy，而少于$ c \ log n $指导的acyclicclic of $ d_n $的$ d_n $不涵盖所有$ h $ copies。在这里，这种二分法得到了很大的加强。令$ {\ vec g}（n，p）$表示随机定向图。 $ h $的{\ em分数是$ a（h）= max \ {\ frac {| e（h'）|} {| v（h'）| -1} \} $，其中最大值均超过所有非辛格尔顿子图。如果$ a（h）= \ frac {| e（h）|} {| v（h）| -1} $，那么$ h $ is {\ em完全平衡}。完整的图形，完整的多部分图，周期，树木以及实际上几乎所有图形都是完全平衡的。事实证明： 1）让$ h $是$ h $顶点的DAG，除了根生星以外的其他$ M $边缘。对于每个$ a^*> a（h）$都存在$ c^*= c^*（a^*，h）> 0 $，因此几乎可以肯定的是，$ g \ sim {\ vec g}（\ n，n，n，n，n，n^{ - 1/a^*}）$都具有最多的$ c^*$ c^*$ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $ g $的属性$ g $。此外，存在$ s（h）= m/2 + o（m^{4/5} h^{1/5}）$，以至于以下任何此类$ x $的强烈断言：$ g $中的$ h $ copy in $ g $中的$ g $不超过$ s（h）的每个元素，每个元素均由$ x $ x $ x $ x $ x $ x $ x $。 2）如果$ h $完全平衡，则每$ 0 <a^* <a（h）$，几乎肯定$ g \ sim {\ vec g}（n，n，n，n，n，n^{ - 1/a^*}）$具有单个定向的acyclic子段，覆盖了所有$ h $ opies。 至于第一个结果，请注意，如果$ h = o（m）$，则$ s（h）=（1+o_m（1））m/2 $是$ h $的边缘的一半。实际上，对于无限的许多$ h $，它认为$ s（h）= m/2 $，最佳。至于第二个结果，一般不能放松$ H $完全平衡的要求。
Let $H$ be a directed acyclic graph other than a rooted star. It is known that there are constants $c(H)$ and $C(H)$ such that the following holds for the complete directed graph $D_n$. There are at most $C\log n$ directed acyclic subgraphs of $D_n$ that cover every $H$-copy of $D_n$, while fewer than $c\log n$ directed acyclic subgraphs of $D_n$ do not cover all $H$-copies. Here this dichotomy is considerably strengthened. Let ${\vec G}(n,p)$ denote the random directed graph. The {\em 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 {\em totally balanced}. Complete graphs, complete multipartite graphs, cycles, trees, and, in fact, almost all graphs, are totally balanced. It is proved: 1) Let $H$ be a dag with $h$ vertices and $m$ edges other than a rooted star. For every $a^* > a(H)$ there exists $c^* = c^*(a^*,H) > 0$ such that almost surely $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$. 2) If $H$ is totally balanced then for every $0 < a^* < a(H)$, almost surely $G \sim {\vec G}(n,n^{-1/a^*})$ has a single directed acyclic subgraph that covers all its $H$-copies. 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.
