Extremal results on feedback arc sets in digraphs

For an oriented graph $G$, let $\beta (G)$ denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any $m$-edge oriented graph $G$ satisfies $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the bound $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$ is sharp as a function of $m$ if $B$ is not bipartite, but the exponent $3/4$ in the lower order term can be improved if $B$ is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in $[3/4,1]$ is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Constructing highly arc transitive digraphs using a direct fibre product

We introduce a construction of highly arc transitive digraphs using a direct fibre product. This product generalizes some known classes of highly arc transitive digraphs but also allows us to construct new ones. We use the product to obtain counterexamples to a conjecture advanced by Cameron, Praeger and Wormald on the structure of certain highly arc transitive digraphs.