A note on subdigraphs of digraphs with large outdegrees (Q791535): Difference between revisions

A digraph without loops and parallel edges on a set of n vertices such that the outdegree of every vertex is at least q is denoted by \((n,\geq q)\)-digraph. The following problem is considered in the list of unsolved problems given by \textit{C. ST. J. A. Nash-Williams} [Bull. Lond. Math. Soc. 14, 294-328 (1982; Zbl 0492.05024)]: if D is an \((m+n,\geq q+r)\)- digraph, must there be some subdigraph of D which is an \((m,\geq q)-\) or on \((n,\geq r-\)digraph? In the paper the author shows that the answer is ''No''. More precisely, it is proved that for every \(k>0\) and every prime \(p\equiv 3\) (mod 4) that satisfies \(p>k^ 22^{2k-2}\) there exists a \((p,\geq 1/2(p-1))-\)digraph that contains neither \((k,\geq [1/2k])-\) nor \((p-k,\geq 1/2(p-1)-k+1)\)- subdigraphs.