×

The covering threshold of a directed acyclic graph by directed acyclic subgraphs. (English) Zbl 1506.05178

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:
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\).
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.

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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon and J. Spencer.The probabilistic method. John Wiley & Sons, 2004. · Zbl 1333.05001
[2] N. Alon and R. Yuster. Threshold functions forH-factors.Combinatorics, Probability and Computing, 2(2):137-144, 1993. · Zbl 0794.05098
[3] R. Boppona and J. Spencer. A useful elementary correlation inequality.Journal of Combinatorial Theory, Series A, 50(2):305-307, 1989. · Zbl 0663.60007
[4] Y. Chee, C. Colbourn, D. Horsley, and J. Zhou. Sequence covering arrays.SIAM Journal on Discrete Mathematics, 27(4):1844-1861, 2013. · Zbl 1292.05079
[5] P. Erd˝os and A. R´enyi. On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960. · Zbl 0103.16301
[6] Z. F¨uredi. Scrambling permutations and entropy of hypergraphs.Random Structures & Algorithms, 8(2):97-104, 1996. · Zbl 0842.05002
[7] Z. F¨uredi, P. Hajnal, V. R¨odl, and W. Trotter. Interval orders and shift graphs. In A. Hajnal and V. T. S´os, editors,Sets, Graphs, and Numbers, volume 60, pages 297-313. North-Holland Publishing Co.; J´anos Bolyai Mathematical Society, 1992. · Zbl 0785.05082
[8] Y. Ishigami. Containment problems in high-dimensional spaces.Graphs and Combinatorics, 11(4):327-335, 1995. · Zbl 0843.05018
[9] Y. Ishigami. An extremal problem ofdpermutations containing every permutation of everytelements.Discrete Mathematics, 159(1-3):279-283, 1996. · Zbl 0860.05001
[10] S. Janson. Poisson approximation for large deviations.Random Structures & Algorithms, 1(2):221-229, 1990. · Zbl 0747.05079
[11] C. S. J. A. Nash-Williams. Decomposition of finite graphs into forests.Journal of the London Mathematical Society, 1(1):12, 1964. · Zbl 0119.38805
[12] J. Radhakrishnan. A note on scrambling permutations.Random Structures & Algorithms, 22(4):435-439, 2003. · Zbl 1023.05003
[13] J. Spencer. Minimal scrambling sets of simple orders.Acta Mathematica Hungarica, 22(3-4):349-353, 1972. · Zbl 0242.05001
[14] J. Tarui. On the minimum number of completely 3-scrambling permutations.Discrete Mathematics, 308(8):1350-1354, 2008. · Zbl 1137.05004
[15] R. Yuster. Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs.Electronic Journal of Combinatorics, 27(4):#P4.13, 2020 · Zbl 1450.05071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.