Ferrer-i-Cancho (2017): Random crossings in dependency trees #

Ferrer-i-Cancho asks how many crossings a sentence would show if its word order were lost and replaced by a uniformly random one. Two links cross in a third of the linearizations when they share no endpoint and in none otherwise, so the expected number of crossings is a third of the number of pairs of links that can cross (eq. 13, three_mul_sum_crossings_map), whatever the link structure. In a tree that number is fixed by the sentence length and the second moment of the degrees (eq. 3, two_mul_disjointLinkPairs_add_sum_degree_sq_of_isTree), so a random linearization expects n (n - 1 - ⟨k²⟩) / 6 crossings (eq. 14, six_mul_sum_crossings_map_add_of_isTree): six for the sentence of Fig. 1 (fig1_sum_crossings_map), none in any order for a star tree (star_crossings_map).

Implementation notes #

Expectations are stated as counts over all n ! linearizations, with the divisions cleared.
Crossings are counted as ordered quadruples. Four distinct linked positions alternate in one of their 4 ! equally likely relative orders (Equiv.Perm.factorial_mul_card_monotone_comp), and each unordered pair of disjoint links has eight ordered witnesses.
Potential crossings are counted for any link structure, 2 · C_pairs + ∑ k² = m (m + 1) for m links, through ordered pairs of darts; a tree has n - 1 links because its undirected view is a tree (DependencyGrammar.Graph.IsTree.isTree_toSimpleGraph).

References #

source

def FerrerICancho2017.disjointLinkPairs {n : ℕ} (g : DependencyGrammar.Graph n) :

ℕ

The unordered pairs of links sharing no endpoint — the pairs that can cross at all, [FC17]'s potential crossings. Each pair is counted once, by the representative with both links least-endpoint-first and the earlier-starting link first.

Equations

One or more equations did not get rendered due to their size.

Instances For

Crossings under a relabelling #

source

theorem FerrerICancho2017.crossings_map {n : ℕ} {g : DependencyGrammar.Graph n} (σ : Equiv.Perm (Fin n)) :

(g.map σ).crossings = {x : Fin n × Fin n × Fin n × Fin n | g.Linked x.1 x.2.1 ∧ g.Linked x.2.2.1 x.2.2.2 ∧ DependencyGrammar.Alternate (σ x.1) (σ x.2.1) (σ x.2.2.1) (σ x.2.2.2)}.card

Relabelling scores the crossing quadruples in the positions the permutation assigns rather than in g's own.

One linearization in twenty-four alternates a distinct quadruple #

Summing over linearizations, grouped by quadruple #

Eight ordered witnesses per unordered disjoint pair #

The expected-crossings identity #

source

theorem FerrerICancho2017.three_mul_sum_crossings_map {n : ℕ} {g : DependencyGrammar.Graph n} :

3 * ∑ σ : Equiv.Perm (Fin n), (g.map σ).crossings = n.factorial * disjointLinkPairs g

Expected crossings under random linearization ([FC17], eq. 13): summed over all n ! linearizations, three times the crossing count is n ! times the number of disjoint link pairs. So a uniformly random ordering expects a third of a crossing per pair of links sharing no endpoint, whatever the sentence's own order was.

Potential crossings from the degree sequence #

Ordered pairs of darts number (2m)² for m links. Those sharing a position are counted from each dart's endpoints: a dart (a, b) meets 2 (k_a + k_b) - 2 darts, which sums to 4 ∑ k² - 4m.

source

theorem FerrerICancho2017.two_mul_disjointLinkPairs_add_sum_degree_sq {n : ℕ} {g : DependencyGrammar.Graph n} :

2 * disjointLinkPairs g + ∑ v : Fin n, g.toSimpleGraph.degree v ^ 2 = g.toSimpleGraph.edgeFinset.card * (g.toSimpleGraph.edgeFinset.card + 1)

Potential crossings from the degrees: in any link structure with m links, 2 · C_pairs + ∑ k² = m (m + 1).

source

theorem FerrerICancho2017.two_mul_disjointLinkPairs_add_sum_degree_sq_of_isTree {n : ℕ} {g : DependencyGrammar.Graph n} (hT : g.IsTree) :

2 * disjointLinkPairs g + ∑ v : Fin n, g.toSimpleGraph.degree v ^ 2 = n * (n - 1)

Potential crossings of a tree ([FC17], eq. 3, from [FC13]): C_pairs = n (n - 1 - ⟨k²⟩) / 2, where ⟨k²⟩ = ∑ k² / n.

source

theorem FerrerICancho2017.six_mul_sum_crossings_map_add_of_isTree {n : ℕ} {g : DependencyGrammar.Graph n} (hT : g.IsTree) :

6 * ∑ σ : Equiv.Perm (Fin n), (g.map σ).crossings + n.factorial * ∑ v : Fin n, g.toSimpleGraph.degree v ^ 2 = n.factorial * (n * (n - 1))

Expected crossings of a tree ([FC17], eq. 14): a uniformly random linearization expects n (n - 1 - ⟨k²⟩) / 6 crossings, a function of the sentence length and the degree second moment alone.

The paper's examples #

source

def FerrerICancho2017.fig1 :

DependencyGrammar.Tree 9

Fig. 1: She loved me for the dangers I had passed in [Mel88]'s analysis, where the preposition heads its object and the auxiliary heads the relative clause. Relations other than the subject and object of loved, which the caption names, are dep.

Equations