The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:

What is the asymptotically maximum $L = L(n)$ such that there exists a "square-free" set of $n$ paths through an $n$-node graph $G = (V, E)$, such that each path has length $L$?

By "square-free," we mean that there are no four distinct nodes $a, b, c, d \in V$ and distinct paths $\pi_{ab}, \pi_{bc}, \pi_{cd}, \pi_{da}$ with $a, b \in \pi_{ab}$, etc.

The best known bound is $L = O(n^{1/4})$. I am curious about a directed version of the above question, where we view the paths as directed and we are sensitive to the direction of the square's edges. In particular, there are four different ways that the edges of a square can be directed:

enter image description here

These define four different versions of the above problem, where we view the paths as directed and the goal is to determine $L_a, L_b, L_c,$ or $L_d$ where only the corresponding type of square is forbidden. The first three cases turn out to be not so interesting: it's easy to see $L_a = \Theta(n)$ (since we can make even a very long path system cycle-free by insisting that the paths are ordered according to a topological sort of the nodes), and it's not too hard to show $L_b = L_c = O(n^{1/4})$ using arguments similar to those for the undirected version of the problem.

My question is about $L_d$: I have been unable to find any interesting upper or lower bounds on this quantity.

Are there any known estimates on $L_d$? More generally, is there a body of literature on "Turan-like" problems about forbidden structures in systems of directed paths, like this one?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.