Feedback edge set in bipartite digraph

Source abstract

Let $β(G)$ denote the minimum size of a feedback edge set of a digraph $G$, and let $γ(G)$ denote the number of unordered pairs of nonadjacent vertices. Motivated by the Chudnovsky--Seymour--Sullivan conjecture for $3$-free digraphs, we study the corresponding feedback-edge problem for bipartite digraphs. In the bipartite setting, $γ(G)$ is taken to count only nonadjacent pairs with ends in distinct partite sets. We prove that every $4$-free bipartite digraph $G$ satisfies $β(G)\le γ(G)/2$. We also determine the exact Turán number of $2k$-free strong bipartite digraphs with partite sets $X$ and $Y$: if $|X|,|Y|\ge k+1$, then the maximum number of edges is $$(|X|-(k-1))(|Y|-(k-1))+2k-2.$$ Finally, for the extremal case $k=2$, we analyze the structure of $4$-free strong bipartite Turán digraphs and prove the sharper bound $β(G)\le γ(G)/3$ for all such digraphs. This constant is attained by a natural balanced three-block construction.