Packing Triangles in Regular Tournaments. Issue 1 (9th August 2012) - Yuster, Raphael
Abstract We prove that a regular tournament with n vertices has more than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz9b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n211.5(1−o(1)) pairwise arc‐disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz77" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n28, so these tournaments do not have <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7hz54" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n28 pairwise arc‐disjoint triangles.