Random crossings in dependency trees
This addresses a theoretical problem in computational linguistics regarding syntactic structure, but it is incremental as it builds on prior hypotheses about dependency length minimization.
The paper investigates the expected number of crossings in dependency trees when sentence order is randomized, finding that it depends on sentence length and vertex degree moments, with minimum crossings in star trees and maximum in linear trees.
It has been hypothesized that the rather small number of crossings in real syntactic dependency trees is a side-effect of pressure for dependency length minimization. Here we answer a related important research question: what would be the expected number of crossings if the natural order of a sentence was lost and replaced by a random ordering? We show that this number depends only on the number of vertices of the dependency tree (the sentence length) and the second moment about zero of vertex degrees. The expected number of crossings is minimum for a star tree (crossings are impossible) and maximum for a linear tree (the number of crossings is of the order of the square of the sequence length).