Cycles in dense digraphs (Q949775): Difference between revisions

\(G\) is a digraph containing no 3-cycles, and \(X\) is a subset of its edges such that \(G \setminus X\) is acyclic. Let \(\beta(G)\) be the minimum cardinality of such an \(X\). The authors wish to bound \(\beta(G)\) with \(\gamma(G)\), that denote the number of unordered pairs \(\{u, v\}\) that are not adjacent in \(G\). Their first result is that \(\beta(G) \leq \gamma(G)\). They also exhibit an infinite family of digraphs for which \(\gamma(G)=2n^2\) for any \(n\) natural, and \(\beta(G)= \gamma(G)/2\). It leads to Conjecture \(\beta(G) \leq \gamma(G)/2\). These inequalities are in intimate relation to the Cacetta-Häggkvist conjecture [\textit{L. Cacetta} and \textit{R. Häggkvist}, in: Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] that asserts: If \(G\) is a digraph containing no 3-cycles, then some vertex has outdegree less than \(n/3\). The conjecture is verified for special graph, namely it holds for {\parindent=6mm \begin{itemize}\item[(i)]if \(V(G)\) is the union of two cliques \item[(ii)]\(G\) is a circular interval digraph. \end{itemize}} The proof techniques involve a four function theorem, that resembles but not equivalent to that of \textit{R. Ahlswede and D. E. Daykin} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 43, 183--185 (1978; Zbl 0357.04011)].