Diplomamunka

Rudolf Gábor Témavezető:Horváth Sándor 2

Bipartite graphs in the combinatorics of words

Gábor Rudolf

August 26, 2002

Introduction

The basic idea of this paper is very simple:given two words we consider the graph given by connecting the positions of the two words containing identical letters.The paper has two main parts:first we use a variant of Lentin’s construction(which can be used to study equations on words of fixed length, see [13]) to get a generalization of the Fine-Wilf periodicity theorem and a natural proof of some sharpness results.This section is largely based on [17].In the second part we present a new approach to the subword problem with an algorithmic point of view based on non-crossing matchings in bipartite graphs and using many results from the theory of partially ordered sets.As these parts are largely independent,in references we omit the first number(i.e.we refer to Theorem 1.3.5 as 3.5,etc.).

1 On the sharpness and generalizations of the Fine-Wilf periodicity theorem

On the notation used in this part

For a word w w(i) denotes the i^{th} letter of w while w^{ω} denotes the infinite word ”wwww … ” . If S is a set of positive integers and w(i) = z(i) for every i ∈ S we denote this fact by w|_{s} = z|_{s}. For two positive integers n and p we denote the unique value i ∈ {1, 2, …, p} for which n ≡ b (mod p) by n mod p. The greatest common divisor of p and q is denoted by gcd(p, q). The set of positive integers is denoted by ω.

1.1 The Fine-Wilf Periodicity Theorem

Theorem 1.1.1. (Fine-Wilf Periodicity Theorem): Let X be a finite alphabet, |X| ≥ 2,p and q are positive integers; w ∈ X^{p}, z ∈ X^{q}. Then w = z if and only if w^{ω} and z^{ω} have a common prefix of length p + q − gcd(p, q).

The proof of this theorem can be found at [1],[10],[4]and [11]. We shall also give an alternative proof using our more general results.

Definition 1.1.2. Let X be a finite alphabet,|X| ≥ 2; p ≤ q are positive integers.We call an S set of integers a (p,q)-Fine-Wilf set if it has the following property: For all w ∈ X^{p}, z ∈ X^{q} : w^{ω} = z^{ω} ⟺ w^{ω}|_{S} = z^{ω}|_{S}. We call S minimal if none of its true subsets are (p,q)-Fine-Wilf sets.

We shall see that for |X| ≥ 2 the previous definition does not depend on the size of X. With this terminology the Fine-Wilf theorem can be restated as follows:

Theorem 1.1.1b. For every pair of positive integers p ≤ q {1, 2, …, p + q − gcd(p, q)} is a (p,q)-Fine-Wilf set.

Our main aim is to give a characterization of Fine-Wilf sets and minimal Fine-Wilf sets.The latter characterization can also be used to prove the Fine-Wilf theorem (in its form 1.1b.) and to prove some results on the sharpness of the Fine-Wilf theorem.The following construction of bipartite graphs corresponding to sets of integers will be our main tool in obtaining the desired characterizations.

1.2 Bipartite graphs and periodic words

We begin with the following obvious observation:

Proposition 1.2.1. For the words w ∈ X^{p}, z ∈ X^{q}:

w^{ω}(i) = z^{ω}(i) ⟺ w(i mod p) = z(i mod q)

Our main idea is to connect positions of the words where their letters must be the same. This idea is formalized in the following definition.

Definition 1.2.2. Let p ≤ q be positive integers.For every S set of positive integers we define G_{S} = G_{S}(p, q) = (W, Z, E_{S}) as a bipartite graph on vertices {W_{1}, W_{2}, …, W_{p}} = W and {Z_{1}, Z_{2}, …, Z_{q}} = Z with edges E_{S} = {e_{s} : s ∈ S} ,where e_{s} = (W_{smodp}, Z_{smodq}) .(If the edges corresponding to two (or more) elements of S connect the same vertices, we consider them multiple edges).

As a direct consequence of 2.1.we get

Proposition 1.2.3. For w ∈ X^{p}and z ∈ X^{q} :

w^{ω}|_{S} = z^{ω}|_{S} ⟺ ∀(W_{i}, Z_{j}) ∈ E_{S} : w(i) = z(j)

Notation. Note that vertices in W correspond to positions of w, while those in Z correspond to positions in z.We adopt the following convention in notation: we refer to general vertices of G_{S} as V_{i} or Y_{j} (where V, Y ∈ {W, Z}), and refer to the letters in the positions corresponding to V_{i} and Y_{j} as v(i) and y(i), respectively, i.e. v(i) = w(i) if V = W and v(i) = z(i) if V = Z. For any two vertices let V_{i} ∼_{S} Y_{j} denote the fact that they are in the same connected component of G_{s}.The connected component of V_{i} is denoted by [V i]_{S}.

It follows from 2.3. that if two vertices are in the same connected component of G_{s} then the two letters in the positions corresponding to these vertices must be same too, hence we get

Proposition 1.2.4. w^{ω}|_{S} = z^{ω}|_{S} if and only if the following implication holds for all V_{i}, Y_{j} ∈ W ∪ Z: V_{i} ∼_{S} Y_{j} ⇒ v(i) = y(j)

We can use this result to give a characterization of Fine-Wilf sets using their corresponding bipartite graphs.

1.3 Characterizations of the Fine-Wilf sets

Theorem 1.3.1. An S set of positive integers is a (p,q)-Fine-Wilf set if and only if ∼_{S}=∼_{ω} (i.e. the connected components of G_{S} are the same as those of G_{ω}).

Proof. Let w ∈ X^{p}, z ∈ X^{q} be two arbitrary words of lengths p and q.Let us consider the following statements:

s1: w^{ω} = z^{ω} s2: ∀V_{i}, Y_{j} ∈ W ∪ Z : V_{i} ∼_{ω} Y_{j} ⇒ v(i) = y(j) s3: w^{ω}|_{S} = z^{ω}|_{S} s4: ∀V_{i}, Y_{j} ∈ W ∪ Z : V_{i} ∼_{S} Y_{j} ⇒ v(i) = y(j)

By 2.4. we have the equivalences s1 ⟺ s2 and s3 ⟺ s4.

I. If ∼_{S}=∼_{ω},then obviously s2 ⟺ s4.It follows that s1 ⟺ s3,which means that S is a (p,q)-Fine-Wilf set.

II. If S is a (p,q)-Fine-Wilf set,then s1 ⟺ s3;it follows that s2 ⟺ s4. Let us now suppose indirectly that ∼_{S}≠∼_{ω}.As G_{S} is a subgraph of G_{ω}(and so its connected components are subsets of those of G_{ω}),there must exist two vertices such that V_{i} ∼_{ω} Y_{j} but V_{i} ≁_{S} Y_{j}.Let a and b be two different elements of X.It is easy to verify that for the words w_{0}, z_{0}(defined below) s4 holds while s2 does not.This contradicts s2 ⟺ s4,which proves the theorem.

w_{0}(k) := \{ \begin{matrix}a if W_{k} ∈ [V_{i}]_{S} \\ b for all other k ∈ \{1, ..., p\} \end{matrix} z_{0}(k) := \{ \begin{matrix}a if Z_{k} ∈ [V_{i}]_{S} \\ b for all other k ∈ \{1, ..., q\} \end{matrix}

Let us now examine the connected components of the graph G_{ω}.

Proposition 1.3.2. V_{i} ∼_{ω} Y_{j} ⟺ i ≡ j (mod gcd(p, q))

Proof. We prove the following statement from which the proposition immediately follows:

(V_{i}, Y_{j}) ∈ E_{S} ⟺ i ≡ j (mod gcd(p, q)).

To prove this it is sufficient to observe that both sides are equivalent to the existence of a positive integer k such that k ≡ i (mod p) and k ≡ j (mod q).

We remark that the proof given above also shows that every connected component of G_{ω} is a complete bipartite graph.By comparing 3.1. and 3.2. we get

Theorem 1.3.1b. S is a (p,q)-Fine-Wilf set if and only if the following implication holds for all V_{i}, Y_{j} ∈ W ∪ Z:

i ≡ j (mod gcd(p, q)) ⇒ V_{i} ∼_{S} Y_{j}.

Corollary 1.3.3. I. If gcd(p, q) = 1, S is a Fine-Wilf set if and only if G_{S} is connected. II. If gcd(p, q) ≠ 1,let us consider the sets S_{i} := {k| (k −1) gcd(p, q)+i ∈ S} for every i ∈ {1, …, gcd(p, q)}.S is a (p,q)-Fine-Wilf set if and only if for every i S_{i} is a (\frac{p}{gcd(p,q)}, \frac{q}{gcd(p,q)})-Fine-Wilf set.

Proof. I. is an obvious consequence of 3.1b. since i ≡ j (mod 1) for all i, j. II. follows immediately from the fact that for every i ∈ {1, …, gcd(p, q)} the subgraph spanned by G_{S}(p, q) on the connected component of G_{ω}(p, q) containing W_{i}(and Z_{i}) is isomorphic to the graph G_{S_{i}} (\frac{p}{gcd(p,q)}, \frac{q}{gcd(p,q)}).This isomorphism can be given as follows(we refer to the vertices of the latter graph in bold letters):By 3.2. the vertices of the first graph must be of the form V_{(k−1) gcd(p,q)+i} for some positive k.V_{(k−1) gcd(p,q)+i} ⟷ V_{k} gives a bijection between the vertices of the two graphs;by checking the definition under 2.2. it is easy to verify that this is an isomorphism.

The second part of 3.3. means that we can restrict ourselves to the case gcd(p, q) = 1. We can now use the first part to obtain characterizations for Fine-Wilf sets where the criteria will not feature graphs.We start by giving some criteria for the connectedness of biparte graphs (We omit the proof of the following elementary lemma).

Lemma 1.3.4. Let G = (W, Z, E) be a bipartite graph with at least 3 vertices.Then the following statements are equivalent: I. G is connected. II. If W_{0} ⊂ W, Z_{0} ⊂ Z, ∅ ≠ W_{0} ∪ Z_{0} ≠ W ∪ Z then there exists an edge in E with exactly one end in W_{0} ∪ Z_{0}. III. For every subset W_{0} of W,∅ ≠ W_{0} ≠ W there is a path of length 2 with exactly one end in W_{0}.The same must also hold for the subsets of Z.

Before we apply these criteria we introduce some notations which will allow us to present the results in a more concise form.

Notation. For an integer m,a set of integers S and I ⊂ {1, …, m} let S_{m}(I) := {s ∈ S| ∃i ∈ I : s ≡ i (mod m)}.For I = {i} we also use S_{m}(i) := S_{m}({i}).We adopt the convention that for a set referred to as P ⊂ {1, …, p} P̄ will denote its complementing set,i.e. P̄ := {1, …, p} \ P.

Theorem 1.3.5. For gcd(p, q) = 1 S is a (p,q)-Fine-Wilf set if and only if for every P ⊂ {1, …, p}, Q ⊂ {1, …, q} (where P ∪ Q ≠ ∅ ≠ P̄ ∪ Q̄):

(S_{p}(P) ∩ S_{q}(Q̄)) ∪ (S_{p}(P̄) ∩ (S_{q}(Q)) ≠ ∅

Proof. I.If the conditions on the sets hold,by 3.3. we have to prove that G_{S} is connected.We use the criterium for connectedness given at 3.4.(II.): for the subsets W_{0} ⊂ W, Z_{0} ⊂ Z let P = {i| W_{i} ∈ W_{0}}, Q = {j| Z_{j} ∈ Z_{0}}.Then by our conditions there exists in S an s ∈ (S_{p}(P) ∩ S_{q}(Q̄)) ∪ (S_{p}(P̄) ∩ (S_{q}(Q)). It is easy to verify that the edge (W_{smodp}, Z_{smodq}) has exactly one end in W_{0} ∪ Z_{0}. II. If G_{S} is connected and P, Q are as stated above,let W_{0} = {W_{i}| i ∈ P }, Z_{0} = {Z_{j}| j ∈ Q}.Then there exists an edge e_{s} corresponding to some s ∈ S with exactly one end in W_{0} ∪ Z_{0}.It is easy to see that s ∈ (S_{p}(P) ∩ S_{q}(Q̄)) ∪ (S_{p}(P̄) ∩ (S_{q}(Q)).

Theorem 1.3.6. For gcd(p, q) = 1 S is a (p,q)-Fine-Wilf set if and only if the following two conditions hold: I. For every P ⊂ {1, …, p} (∅ ≠ P ≠ {1, …, p}) there exists an integer q_{P} such that S_{p}(P) ∩ S_{q}(q_{P}) ≠ ∅ and S_{p}(P̄) ∩ S_{q}(q_{P}) ≠ ∅. II. For every q ⊂ {1, …, q} (∅ ≠ Q ≠ {1, …, q}) there exists an integer p_{Q} such that S_{q}(Q) ∩ S_{p}(p_{Q}) ≠ ∅ and S_{q}(Q̄) ∩ S_{p}(p_{Q}) ≠ ∅.

Proof. The proof is similar to that of 3.5.using 3.4.(III.) instead of 3.4.(II.).

Remark. In the general case (when gcd(p, q) > 1 is possible) theorems 3.5. and 3.6. have to be modified by considering the sets {i, gcd(p, q) + i, 2 gcd(p, q) + i, …, p − gcd(p, q) + i} and {i, gcd(p, q) + i, 2 gcd(p, q) + i, …, q − gcd(p, q) + i} for values 1 ≤ i ≤ gcd(p, q) instead of the sets {1, …, p} and {1, …, q}.

The criteria in theorems 3.5 and 3.6 were designed to provide that there are enough elements in S. For minimal Fine-Wilf sets it is possible to give a characterization featuring restrictive criteria. Examination of minimal Fine-Wilf sets will also yield results pertaining to the sharpness of the Fine-Wilf theorem.

1.4 Minimal Fine-Wilf sets and sharpness results

The following simple observation is based upon our characterization of Fine-Wilf sets in 3.1.

Proposition 1.4.1. S is a minimal (p,q)-Fine-Wilf set if and only if G_{S} is a maximal spanning forest of G_{ω}(with respect to the number of edges,i.e.its connected components are the same as those of G_{ω}).

This allows us to determine the size of minimal Fine-Wilf sets:

Theorem 1.4.2. Every minimal (p,q)-Fine-Wilf set is of size p+q−gcd(p, q).

Proof. According to 3.2. G_{ω} is a graph on p + q vertices which has gcd(p, q) connected components,hence every maximal spanning forest of G_{ω} has p + q − gcd(p, q) edges.

Corollary 1.4.3. The Fine-Wilf theorem is sharp for all values of p and q.

Proof. The Fine-Wilf theorem states that {1, 2, …, p + q − gcd(p, q)} is a (p,q)-Fine-Wilf set.As this is a set of size p + q − gcd(p, q),by 4.2. it has to be minimal.

We now apply the method of ”converting” the criteria on the graphs (as in 3.5. and 3.6.) to give a characterization of minimal Fine-Wilf sets. We first review some elementary facts:

Lemma 1.4.4. I. Let G be a graph on n vertices with c connected components.A subgraph G_{S} of G with n − c edges is a maximal spanning forest in G if and only if it is acyclic. II. Let G = (W, Z, E) be a bipartite graph.Then every cycle of G has even length and alternates between W and Z. III. Let G = (W, Z, E) be a bipartite graph and C a cycle of length 2k in G.Then there exist two sets of size k, W_{0} ⊂ W and Z_{0} ⊂ Z,such that W_{0} ∪ Z_{0} spans every edge of C.

Theorem 1.4.5. Let gcd(p, q) = 1.Then S is a minimal Fine-Wilf set if and only if |S| = p + q − 1 and for all P ⊂ {1, …, p}, Q ⊂ {1, …, q} such that |P | = |Q| =: k > 0 : |S_{p}(P) ∩ S_{q}(Q)| ≤ 2k − 1 holds.

Proof. I. If S is a minimal (p,q)-Fine-Wilf set then by 4.2. |S| = p + q − 1 and by 4.1. G_{S} is a forest,therefore it is acyclic.It follows that for any two sets of size k,W_{0} ⊂ W and Z_{0} ⊂ Z, G_{S} spans at most 2k-1 edges in W_{0} ∪ Z_{0}. Let W_{0} := {W_{i}| i ∈ P }, Z_{0} := {Z_{j}| j ∈ Q}.As every element in S_{p}(P)∩S_{q}(Q) corresponds to an edge between W_{0} and Z_{0},|S_{p}(P) ∩ S_{q}(Q)| ≤ 2k − 1 follows. II. If |S| = p + q − 1 and S is not a minimal Fine-Wilf set then by 4.4.(I.) G_{S} has a cycle C of lengt 2k for some k.So by 4.4.(III.) there exist two sets of size k, W_{0} ⊂ W and Z_{0} ⊂ Z,such that there are at least 2k edges between W_{0} and Z_{0}. Let P = {i| W_{i} ∈ W_{0}}, Q = {j| Z_{j} ∈ Z_{0}};as every edge between W_{0} and Z_{0} corresponds to an element in S_{p}(P) ∩ S_{q}(Q),we have |S_{p}(P) ∩ S_{q}(Q)| ≥ 2k.

We can use this result to give an alternative proof of the Fine-Wilf theorem:

Proof of Theorem 1.1b. We have to show,that S := {1, 2, …, p+q−gcd(p, q)} is a (p,q)-Fine-Wilf set.First we note that we can restrict ourselves to the case gcd(p, q) = 1:by considering our words as elements of (X^{gcd(p,q)})^{+},the problem is reduced to this case,albeit over a larger alphabet.In accordance with 4.5. let us now consider two sets P = {p_{1}, …, p_{k}} ⊂ {1, …, p} and

Q = {q_{1}, …, q_{k}} ⊂ {1, …, q}.Then S_{q}(Q) = ⋃_{i=1}^{k} S_{q}(q_{i}),where

S_{q}(q_{i}) := \{ \begin{matrix}\{q_{i}, q_{i} + q\} if q_{i} < p \\ \{q_{i}\} if q_{i} ≥ p \end{matrix} . Let us now suppose indirectly that

|S_{p}(P)∩S_{q}(Q)| ≥ 2k.Then |S_{q}(Q)| ≥ 2k implies that q_{i} < p for all q_{i},therefore 1 ≤ k < p and q_{i} ≢ q_{j} (mod p) for all i ≠ j. Also,for every j there must exist i_{j}, i_{j′} such that q_{j} ≡ p_{i_{j}} (mod p) and q_{j} + q ≡ p_{i_{j′}} (mod p).

As ∑_{j=1}^{k} p_{i_{j}} = ∑_{j=1}^{k} p_{i_{j′}} = ∑_{i=1}^{k} p_{i},summation over j = 1, …, k for the previous

congruences yields kq ≡ 0 (mod p).Since gcd(p, q) and 1 ≤ k < p,we have a contradiction,which proves the theorem.

We have already seen that the Fine-Wilf theorem is sharp for all p and q. In the last part of the article we examine the topic of ”counterexamples”:

Definition 1.4.6. We call the pair of words w ∈ X^{p}, z ∈ X^{q} a counterexample for (p, q) if w^{ω} and z^{ω} have a common prefix of length p+q −gcd(p, q)−1 but w^{ω} ≠ z^{ω}.

Early counterexamples for some specific values of (p, q) were given by Perrin (see [11]) using properties of ”Fibonacci-like” words.The following more general family of counterexample was constructed by S.Horváth and was presented at [12].

Example 1.4.7. ( S.Horváth) Let a and b be two different letters of the alphabet X and x an arbitrary word of length j − 1.Then it is easy to verify that the following words are counterexamples for (kj, (1 + mk)j) where m, k are positive integers:

w = (xa)^{k−1}xb, z = w^{m}xa

Remark. In the example above we have gcd(p, q) = j.The construction yields a counterexample for all pairs (p, q) where q ≡ gcd(p, q) (mod p).It follows from the next theorem that for these values it yields all the possible counterexamples.

We conclude by proving the following theorem on the structure of counterexamples which is also featured (with a different proof) in [1].

Theorem 1.4.8. I. If gcd(p, q) = 1 then there exists a counterexample w_{p,q}, z_{p,q} which is unique up to a renaming. II. In the general case every counterexample is of the following form: x is an arbitrary word of length gcd(p, q) − 1, p_{0} := \frac{p}{gcd(p,q)}, q_{0} := \frac{q}{gcd(p,q)};

w = xw_{1}xw_{2} … xw_{p_{0}}, z = xz_{1}xz_{2} … xz_{q_{0}} where w_{i} = w_{p,q}(i), z_{j} = z_{p,q}(j).

Proof. I. As S = {1, …, p + q − 1} is a minimal (p,q)-Fine-Wilf set,G_{S} is a spanning tree.The graph corresponding to S = {1, …, p + q − 2} is obtained from G_{S} by erasing the single edge corresponding to p + q − 1 which causes the tree to fall into two connected components.According to 2.4. the words w^{ω} and z^{ω} have a common prefix of length p + q − 2 if and only if for both connected components they have the same letter in every position corresponding to that component.Also,the letters assigned to the two components must be different,otherwise we would have w^{ω} = z^{ω}.So the only way to get a counterexample is by assigning different letters to the components;as the Fine-Wilf theorem is sharp,this will indeed yield a counterexample. II. Let us now consider the sets S_{i} and T_{i} (as defined in 3.3) for the sets S = {1, …, p+q−gcd(p, q)} and T = {1, …, p+q−gcd(p, q)−1},respectively.It is easy to see that for i < gcd(p, q) S_{i} = T_{i} while S_{gcd(p,q)} = {1, …, p_{0}+q_{0}−1} and T_{gcd(p,q)} = {1, …, p_{0} + q_{0} − 2}.We also know that for every i S_{i} is a (p_{0}, q_{0})-Fine-Wilf set,therefore in every counterexample the following implication must hold:

i ≡ j ≢ 0 (mod gcd(p, q)) ⇒ v(i) = y(j) (wherev, y ∈ {w, z}).

This accounts for the repetition of the word x in the positions not divisible by gcd(p, q).For the remaining positions the arguments in case I. can be applied (with p_{0}, q_{0} instead of p and q).

Remark. Example 4.7. says that for gcd(p, q) = 1, q ≡ 1 (mod p):

w_{p,q} = aa … ab, z_{p,q} = (w_{p,q})^{⌊^{\frac{q}{p}}⌋} a

This reflects the fact that in this case the graph G_{S} corresponding to S = {1, …, p + q − 1} contains an alternating path passing the vertices in W in ascending order;the last edge of this path corresponds to p + q − 1.As G_{S} is acyclic,erasing this last edge will cause the vertex W_{p} to be in a different connected component from W_{1}, …, W_{p−1}.Therefore w_{p,q}(p) must be different from w_{p,q}(1), …, w_{p,q}(p − 1).

2 Bipartite graphs in the plane and the subword problem

In this section we study the common subwords of two given words.Our main tool will be a poset-structure defined through a bipartite graph connecting the identical letters of the two words.First we review some known results about chains and antichains in partially ordered sets,then we establish some results on non-crossing matchings and non-crossing subgraphs of bipartite graphs in the plane that might also be of independent interest.

Remark. Throughout the following sections we sometimes use the somewhat nebulous term ”effectively computable” by which we mean computable in polynomial time using some well-known algorithm (such as algorithms for finding shortest and longest paths in acyclic digraphs and Ford and Fulkerson’s minimal cost flow algorithm).

2.1 Chains and antichains in partially ordered sets

In this subsection we present the results without proof.The main theorem comes from [6];in most respects we will follow the structure and notations of that paper.We begin with some necessary definitions.

Definition 2.1.1. Let ≺ be a partial ordering on the finite set P = {p_{1}, …, p_{n}}. A totally ordered subset C of P is called a chain,a set A of pairwise incomparable elements in P is an antichain.We denote the set of all chains by ℂ(≺) and denote the set of antichains by 𝔸(≺).Let c and a denote the cardinalities of the largest chain and the largest antichain,respectively.A set of pairwise disjoint non-empty chains is called a chain family,a set of pairwise disjoint non-empty antichains is an antichain family.Let 𝒞 and 𝒜 be the sets of all chain- and antichain families,respectively.We adopt the following convention in referring to chain and antichain families of a given cardinality: 𝒞_{ν} = {C_{1}, C_{2}, …, C_{ν}}, 𝒜_{α} = {A_{1}, A_{2}, …, A_{α}} (i.e. 𝒞_{ν} always denotes a chain family of cardinality ν).The maximum number of elements coverable by a chain- or antichain family of some give cardinality is denoted by c_{ν} := max_{𝒞_{ν}∈𝒞}| ⋃ 𝒞_{ν}| and a_{α} := max_{𝒜_{α}∈𝒜}| ⋃ 𝒜_{α}|,respectively.

A chain family 𝒞_{ν} = {C_{1}, C_{2}, …, C_{ν}} and an antichain family 𝒜_{α} = {A_{1}, A_{2}, …, A_{α}} are called orthogonal if the following two conditions hold: I. P = (⋃ 𝒞_{ν}) ∪ (⋃ 𝒜_{α}) II. C_{i} ∩ A_{j} ≠ ∅ (for 1 ≤ i ≤ ν, 1 ≤ j ≤ α)

We first note the following important property of orthogonal families:

Proposition 2.1.2. If the chain and antichain families 𝒞_{ν} and 𝒜_{α} are orthogonal then they are optimal in the following sense:

c_{ν} = | ⋃ 𝒞_{ν}| = min { ∑_{i=1}^{q} min(|A_{i}|, ν) : {A_{1}, …, A_{q}} ∈ 𝒜 is an antichain partition of P }

a_{α} = | ⋃ 𝒜_{α}| = min { ∑_{i=1}^{q} min(|C_{i}|, α) : {C_{1}, …, C_{q}} ∈ 𝒞 is a chain partition of P }

We now state the main theorem of this section.

Theorem 2.1.3. There exists a sequence

𝒞_{a}|𝒜_{1}, 𝒜_{2}, …, 𝒜_{i_{1}}|𝒞_{a−1}, 𝒞_{a−2}, …, 𝒞_{a−j_{1}}|𝒜_{i_{1}+1}, …, 𝒜_{i_{2}}|𝒞_{a−j_{1}−1}, …, 𝒞_{a−j_{2}}| …

(obtained by merging a chain family sequence 𝒞_{a}, 𝒞_{a−1}, …, 𝒞_{1} and an antichain family sequence 𝒜_{1}, 𝒜_{2}, … 𝒜_{c}) such that every member of the sequence is orthogonal to the last member of the other type preceding it(i.e. 𝒜_{1}, …, 𝒜_{i_{1}} are orthogonal to 𝒞_{a} etc.).

A very important feature of this theorem is that its proof is algorithmic (using the minimal cost flow algorithm of Ford and Fulkerson) which means that we can effectively compute the members of the sequence featured in the theorem.Some well-known results can easily be obtained as special cases of the theorem:

Corollary 2.1.4. I. Let 1 ≤ ν ≤ a.Then there exists a chain family 𝒞_{ν} and an antichain family 𝒜_{α} (for some α) that are orthogonal. II. Let 1 ≤ α ≤ c.Then there exists an antichain family 𝒜_{α} and a chain family 𝒞_{ν} (for some ν) that are orthogonal.

By comparing this with 1.2. we get

Theorem 2.1.5. (Greene,[8];Greene and Kleitman,[9])

c_{ν} = min { ∑_{i=1}^{q} min(|A_{i}|, ν) : {A_{1}, …, A_{q}} ∈ 𝒜 is an antichain partition of P }

a_{α} = min { ∑_{i=1}^{q} min(|C_{i}|, α) : {C_{1}, …, C_{q}} ∈ 𝒞 is a chain partition of P }

The algorithmic nature of 1.3. means that we can effectively compute a chain- or antichain family of a given cardinality covering the largest number of elements in P.We note that the above formulae can also be rewritten as follows:

c_{ν} = min_{𝒜_{q}∈𝒜}qν + |P − ⋃ 𝒜_{q}|, a_{α} = min_{𝒞_{q}∈𝒞}qα + |P − ⋃ 𝒞_{q}|

In the special cases α = 1 and ν = 1 we get

Theorem 2.1.6. I.(Dilworth,[2]) c_{a} = n (therefore the minimal number of chains needed to cover P equals the cardinality of the largest antichain). II.(dual version of Dilworth’s theorem) a_{c} = n (therefore the minimal number of antichains needed to cover P equals the cardinality of the largest chain).

As a conclusion we mention another useful result obtainable from 1.3.

Theorem 2.1.7. I. A chain of cardinality c is called a D-chain.The maximal number of pairwise disjoint D-chains is equal to min{|X| : X ⊂ P intersects every D-chain}. II. An antichain of cardinality a is called a D-antichain.The maximal number of pairwise disjoint D-antichains is equal to min{|X| : X ⊂ P intersects every D-antichain}.

As before,optimal subsets X ⊂ P and maximal sets of pairwise disjoint D-(anti)chains can be computed effectively.

2.2 Bipartite graphs in the plane

In this section we deal with bipartite graphs in the plane.We think of these graphs as two parallel rows of vertices connected by straight edges.This notion is formalized in the following definition.

Definition 2.2.1. G = (A, B, E, f_{A}, f_{B}) is a bipartite graph in the plane if (A, B, E) is a bipartite graph and f_{A} : {1, …, |A|} → A,f_{B} : {1, …, |B|} → B are bijections(These functions can be viewed as the numbering of the vertices from left to right).To simplify our notation,let f_{A}(i) =: A_{i}, f_{B}(i) =: B_{i}.The ordering on the vertices is denoted by ≺ (and ⪯),i.e. A_{i} ≺ A_{j} ⟺ i < j, B_{i} ≺ B_{j} ⟺ i < j. We refer to A and B as the shores of G.

While using the functions f_{A} and f_{B} to describe the geometry of G in the plane might seem awkward at first,it will prove to be very convenient later,when we deal with reversing the order of the vertices in one of the shores.We now formalize the notion of crossing edges:

Definition 2.2.2. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.Two different edges (A_{i}, B_{j}) and (A_{k}, B_{l}) are crossingif i < k,j > l or i > k, j < l.They are weakly crossing,if i ≤ k,j ≥ l or i ≥ k, j ≤ l.Two different edges that are not crossing are called compatible,two different edges that are not weakly crossing are called independent.

Our main goals are to find a non-crossing matching of maximum cardinality and to find a minimal subset of a shore of the graph that cannot be covered by a non-crossing matching.We also want to answer these questions for non-crossing edge sets.

Definition 2.2.3. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.A set of edges M ⊂ E is a non-crossing edge set if the elements in M are pairwise compatible.If the edge set M is also a matching,it is called a non-crossing matching.We adopt the following convention in referring to the edges of a given non-crossing edge set: M = {(A_{1}^{M}, B_{1}^{M}), (A_{2}^{M}, B_{2}^{M}), … }, where A_{1}^{M} ⪯ A_{2}^{M} ⪯ … and B_{1}^{M} ⪯ B_{2}^{M} ⪯ … (i.e. they are numbered from left to right).The set of all non-crossing edge sets is denoted by ℂ_{G}^{0},the set of non-crossing matchings is denoted by ℂ_{G}^{1}.

Proposition 2.2.4. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane,M ⊂ E.Then M is a non-crossing matching if and only if its elements are pairwise independent.

Proof. Note that M is a matching if and only if for any two different edges (A_{i}, B_{j}), (A_{k}, B_{l}) ∈ M : i ≠ k and j ≠ l.The proposition immediately follows.

The following can be viewed as the dual objects of non-crossing matchings and non-crossing subgraphs(this relationship will later be examined in more detail):

Definition 2.2.5. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.C ⊂ E is a crossing edge set if the edges in C are pairwise crossing. C is a weakly crossing edge set if the edges in C are pairwise weakly crossing.The set of all crossing edge sets is denoted by 𝔸_{G}^{0}.The set of all weakly crossing edge sets is denoted by 𝔸_{G}^{1}.

The previous questions can also be asked about crossing and weakly crossing edge sets(i.e.to find a maximal (weakly) crossing edge set and to find minimal subsets of a shore not coverable by such subgraphs).As we shall see later,finding a maximum cardinality element of ℂ_{G}^{0}, ℂ_{G}^{1}, 𝔸_{G}^{0} or 𝔸_{G}^{1} is equivalent to finding a maximal chain or antichain in a poset.Finding minimal non-coverable subsets requires a different approach.We need the following definitions:

Definition 2.2.6. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.The edge (A_{i}, B_{j}) ∈ E is the leftmost edge of the vertex A_{i} if (A_{i}, B_{k}) ∈ E ⇒ k ≥ j(the rightmost edge of a given vertex is defined similarly).The edge (A_{k}, B_{l}) ∈ E is a compatible right-neighbour of the edge (A_{i}, B_{j}) ∈ E if i ≤ k,j ≤ l and (A_{k}, B_{l}) is the leftmost edge of A_{k} compatible with (A_{i}, B_{j}) (i.e. if (A_{k}, B_{l′}) is compatible with (A_{i}, B_{j}) then l′ ≥ l).(A_{k}, B_{l}) is an independent right-neighbour of (A_{i}, B_{j}) if i < k, j < l and (A_{k}, B_{l}) is the leftmost edge of A_{k} independent from (A_{i}, B_{j}).An M non-crossing edge set is a leftmost non-crossing edge set if A_{i}^{M} ≺ A_{i+1}^{M} for all 1 ≤ i < |M|, (A_{1}^{M}, B_{1}^{M}) is the leftmost edge of A_{1}^{M} and for 1 < i ≤ |M| (A_{i}^{M}, B_{i}^{M}) is a compatible right-neighbour of (A_{i−1}^{M}, B_{i−1}^{M}). An M non-crossing matching is a leftmost non-crossing matching if (A_{1}^{M}, B_{1}^{M}) is the leftmost edge of A_{1}^{M} and for 1 < i ≤ |M| (A_{i}^{M}, B_{i}^{M}) is an independent right-neighbour of (A_{i−1}^{M}, B_{i−1}^{M}).

The next proposition shows that we can restrict ourselves to studying leftmost non-crossing matchings and edge sets.

Proposition 2.2.7. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.I.For every non-crossing matching M in G there exists a unique leftmost non-crossing matching M̂ covering the same vertices in A as M.Moreover, M̂ is optimal in the following sense:for every non-crossing matching M′ covering the same vertices in A as M BM̂ ; i ⪯ B_{i}^{M′} holds for every 1 ≤ i ≤ |M| (i.e. BM̂ ; i is the leftmost possible endpoint of the i^{th} edge of such a matching). II. For every non-crossing edge set M in G there exists a unique leftmost non-crossing edge set M̌ covering the same vertices in A as M.Moreover,M̌ is optimal in the following sense:for every non-crossing matching M′ covering the same vertices in A as M BM̌ ; |M̌| ⪯ B_{|M′|}^{M′} holds (i.e. BM̌ ; |M̌| is the leftmost possible endpoint of the last edge of such an edge set).

Proof. I. Let AM̂ ; i := A_{i}^{M} for all 1 ≤ i ≤ |M| and let BM̂ ; 1 be the endpoint of the leftmost edge of B_{1}^{M}.For i > 1 we define BM̂ ; i recursively:Let us suppose that we have BM̂ ; i−1 which is optimal in the sense above.Then let BM̂ ; i be the endpoint of the leftmost edge of A_{i}^{M} independent from (A_{i−1}^{M}, BM̂ ; i−1).Such an edge exists since (as M is a non-crossing matching) (A_{i}^{M}, B_{i}^{M}) is independent from (A_{i−1}^{M}, B_{i−1}^{M}),therefore (due to (A_{i−1}^{M}, BM̂ ; i−1)’s optimality) it is also independent from (A_{i−1}^{M}, BM̂ ; i−1).It is easy to see that (A_{i}^{M}, BM̂ ; i) is an independent right neighbour of (A_{i−1}^{M}, BM̂ ; i−1) and therefore it is also optimal. II. can be proven similarly.

Our algorithm is based on the next key lemma which follows immediately from the result above:

Lemma 2.2.8. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane with no isolated points in A. I. Let M be a leftmost non-crossing matching of cardinality m and let A_{i} be a vertex such that A_{m}^{M} ≺ A_{i}.Let B_{j} be the endpoint of the rightmost edge of A_{i}.If B_{j} ⪯ B_{m}^{M} then the vertex set {A_{1}^{M}, A_{2}^{M}, …, A_{m}^{M}, A_{i}} is not coverable by a non-crossing matching.Moreover,every minimal subset of A not coverable by a non-crossing matching can be obtained this way. II. Let M be a leftmost non-crossing edge set of cardinality m and let A_{i} be a vertex such that A_{m}^{M} ≺ A_{i}.Let B_{j} be the endpoint of the rightmost edge of A_{i}.If B_{j} ≺ B_{m}^{M} then the vertex set {A_{1}^{M}, A_{2}^{M}, …, A_{m}^{M}, A_{i}} is not coverable by a non-crossing edge set. Moreover,every minimal subset of A not coverable by a non-crossing edge set can be obtained this way.

Proof. I. It is obvious that the described set is not coverable.Let us now consider a minimal subset N = {A_{1}^{N}, A_{2}^{N}, …, A_{m+1}^{N}} ⊂ A that is not coverable by a non-crossing matching.As N is minimal, N_{0} := {A_{1}^{N}, A_{2}^{N}, …, A_{m}^{N}} can be covered,so by 2.7. we can consider an M leftmost non-crossing matching of cardinality m covering N_{0}.Let i be the number for which A_{i} = A_{m+1}^{N} and let B_{j} be the endpoint of the rightmost edge of A_{i}.Then B_{j} ⪯ B_{m}^{M} must hold,otherwise M ∪{(A_{i}, B_{j})} would be a non-crossing matching covering N. II. can be proven similarly.

We now describe an algorithm to find a minimal subset of A not coverable by a non-crossing matching.First we restate the problem in a form that is easier to handle.

Definition 2.2.9. For a G = (A, B, E, f_{A}, f_{B}) bipartite graph in the plane let S := {(A_{i}, B_{j}) ∈ E | (A_{i}, B_{j}) is the leftmost edge of A_{i} in G} and R := {(A_{i}, B_{j}) ∈ E| (A_{i}, B_{j}) is the rightmost edge of A_{i} in G} be the sets of the left- and rightmost edges in G,respectively.For a given edge e = (A_{i}, B_{j}) ∈ E let C_{e} := {(A_{k}, B_{l})| k < i, l ≥ j} be the set of edges weakly crossing e ”from behind”.Let T := ⋃_{e∈R} C_{e} be the set of edges that weakly cross a rightmost edge

from behind.

The previous theorem means that we have to find a leftmost non-crossing matching M with minimum cardinality the last edge of which is in T. Note that a non-crossing matching is leftmost if and only if it is a chain of independent right-neighbours starting in S.The following graph can be constructed in polynomial time:

Definition 2.2.10. For a G = (A, B, E, f_{A}, f_{B}) bipartite graph in the plane with no isolated points in A let D_{G} = (V, F) be the directed graph on vertices V := E with edges F := {((A_{i}, B_{j}), (A_{k}, B_{l})) | (A_{k}, B_{l}) ∈ E is

an independent right-neighbour of (A_{i}, B_{j}) ∈ E in G}.

We note the following obvious facts about this construction:

Proposition 2.2.11. The graph D_{G} defined above is acyclic.An edge set is a leftmost non-crossing matching in G if and only if its elements constitute the vertex set of a directed path in D_{G} starting in S.The vertex set of any directed path in D_{G} is a non-crossing matching in G.

As the following theorem shows,we can now find a minimal non-coverable subset of A by finding a shortest directed path in D_{G} starting in S and ending in T (If there is an isolated point in A,it is a non-coverable subset of cardinality 1,which is obviously minimal.Therefore we can suppose that there are no isolated points in A.).

Theorem 2.2.12. Let G = (A, B, E, f_{A}, f_{B}) be bipartite graph in the plane with no isolated points in A. I. If the elements A^{1} ≺ A^{2} ≺ ⋯ ≺ A^{m+1} constitute a minimal subset of A not coverable by a non-crossing matching then there exist elements B^{i} ∈ B (1 ≤ i ≤ m) such that (A^{1}, B^{1}), …, (A^{m}, B^{m}) are the vertices of a directed path in D starting in S and ending in T. II. If (A^{1}, B^{1}), …, (A^{m}, B^{m}) (in this order) are the vertices of a directed path in D_{G} starting in S and ending in T then there exists an element A^{m+1} ≻ A^{m} such that {A^{1}, …, A^{m+1}} is not coverable by a non-crossing matching.

Proof. I. As the subset is minimal,there exists a leftmost non-crosssing matching M of cardinality m such that A_{i}^{M} = A^{i} for 1 ≤ i ≤ m;for these values of i let B^{i} := B_{i}^{M} and let B^{m+1} be the endpoint of the rightmost edge of A^{m+1}.Then by 2.11 (A^{1}, B^{1}), …, (A^{m}, B^{m}) are indeed the vertices of a directed path in D_{G} stating in S and (A^{m}, B^{m}) ∈ C_{(A^{m+1},B^{m+1})} ⊂ T.

II. (A^{m}, B^{m}) ∈ T = ⋃_{e∈R} C_{e} ⇒ ∃e = (A^{m+1}, B^{m+1}) ∈ R such that A^{m} ≺ A^{m+1}

and B^{m} ⪰ B^{m+1}. By 2.8.(I.) {A^{1}, …, A^{m+1}} is not coverable.

We now give a summary of the algorithm:given a bipartite graph G in the plane we construct the digraph D_{G} and compute the sets S and T (for every t ∈ T we also fix an element e(t) ∈ R such that t ∈ C_{e(t)}).Then we compute a shortest directed path in D_{G} starting in S and ending in T;the vertices of this path are (A^{1}, B^{1}), …, (A^{m}, B^{m}).Let A^{m+1} be the endpoint of e((A^{m}, B^{m})) in A.Then {A^{1}, …, A^{m+1}} is a minimal cardinality subset of A not coverable by a non-crossing matching.The algorithm for finding a minimal subset of A not coverable by a non-crossing edge set is almost identical,with some changes to the basic definitions 2.9. and 2.10.:

Definition 2.2.13. For a G = (A, B, E, f_{A}, f_{B}) bipartite graph in the plane with no isolated points in A we define the sets S and R as before.For every e = (A_{i}, B_{j}) ∈ E let Č_{e} := {(A_{k}, B_{l})| k < i, l < j} be the set of edges crossing e from behind.Let Ť := ⋃_{e∈R} Č_{e} be the set of edges that cross a rightmost edge

from behind. Let Ď_{G} = (V, F) be the directed graph on vertices V := E with edges F := {((A_{i}, B_{j}), (A_{k}, B_{l})) | (A_{k}, B_{l}) ∈ E is a compatible right-neighbour

of (A_{i}, B_{j}) ∈ E in G}.

Theorem 2.2.14. Let G = (A, B, E, f_{A}, f_{B}) be bipartite graph in the plane with no isolated points in A. I. If the elements A^{1} ≺ A^{2} ≺ ⋯ ≺ A^{m+1} constitute a minimal subset of A not coverable by a non-crossing edge set then there exist elements B^{i} ∈ B (1 ≤ i ≤ m) such that (A^{1}, B^{1}), …, (A^{m}, B^{m}) are the vertices of a directed path in Ď_{G} starting in S and ending in Ť. II. If (A^{1}, B^{1}), …, (A^{m}, B^{m}) (in this order) are the vertices of a directed path in Ď_{G} starting in S and ending in Ť then there exists an element A^{m+1} ≻ A^{m} such that {A^{1}, …, A^{m+1}} is not coverable by a non-crossing edge set.

We now turn to the problem of finding a non-crossing matching and a noncrossing edge set of maximum cardinality.As we show in the next section,these problems can also be solved using a more general approach.However,the graph D_{G} can be used to obtain a less involved algorithm.

Theorem 2.2.15. I. The vertex set of a longest directed path in D_{G} is a non-crossing matching of maximum cardinality in G. II. The vertex set of a longest directed path in Ď_{G} is a non-crossing edge set of maximum cardinality in G.

Proof. I. By 2.11. the vertex set of a directed path in D_{G} is a non-crossing matching in G.Let M be a non-crossing matching of maximum cardinality in G;by 2.7. we can suppose that it is leftmost,so (again by 2.11.) it is a vertex set of a directed path in D_{G}. II. can be proven similarly.

This theorem gives us an opportunity to find maximal non-crossing matchings and edge sets by computing longest directed paths in the graphs D_{G} and Ď_{G}.

As these graphs are acyclic,this provides an efficient algorithm.Using the results on partially ordered sets from the previous section will make it possible to algorithmically solve even more general problems.Before that we need to examine the relationship between crossing and non-crossing edge sets. The connection is based on the following construction:

Definition 2.2.16. For a bijection f : {1, …, n} → X let f̄(i) := f(n − i). Let G = (A, B, E, f_{A}, f_{B}) be bipartite graph in the plane.We denote the graph obtained by reversing the order of the vertices in B by Ḡ := (A, B, E, f_{A}, f̄_{B}).

The following properties of this construction are easily verifiable:

Proposition 2.2.17. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane. I. ¯ Ḡ = G II. ℂ_{G}^{1} = 𝔸0 ; Ḡ,i.e.the non-crossing matchings of G are the crossing edge sets of Ḡ. III. ℂ_{G}^{0} = 𝔸1 ; Ḡ,i.e.the non-crossing edge sets of G are the weakly crossing edge sets of Ḡ. IV. 𝔸_{G}^{1} = ℂ0 ; Ḡ,i.e.the weakly crossing edge sets of G are the non-crossing edge sets of Ḡ. V. 𝔸_{G}^{0} = ℂ1 ; Ḡ,i.e.the crossing edge sets of G are the non-crossing matchings of Ḡ.

(Note that IV. and V. directly follow from I.-III.). An important consequence is that we can find maximum cardinality (weakly) crossing edge sets of G and minimum cardinality subsets of A not coverable by (weakly) crossing edge sets in G by applying our previous algorithms to the graph Ḡ.

Remark. It is easy to see that in this case the notion corresponding to leftmost non-crossing edge sets and matchings will be that of rightmost (weakly) crossing edge sets:the first edge is from R and every other edge (A_{i}, B_{j}) of the set is the rightmost edge of A_{i} (weakly) crossing the previous one.

Before moving on we summarize the algorithmic results of this section.

Theorem 2.2.18. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.Then we can effectively compute the following:

• A non-crossing matching of maximum cardinality.

• A non-crossing edge set of maximum cardinality.

• A crossing edge set of maximum cardinality.

• A weakly crossing edge set of maximum cardinality.

• A minimum cardinality subset of A not coverable by a non-crossing matching.

• A minimum cardinality subset of A not coverable by a non-crossing edge set.

• A minimum cardinality subset of A not coverable by a crossing edge set.

• A minimum cardinality subset of A not coverable by a weakly crossing edge set.

2.3 Poset-structures on the edges of a bipartite graph in the plane

In this section we define two partial orderings on the edges of G and use the results from the section on partially ordered sets to obtain new results on bipartite graphs in the plane.

Definition 2.3.1. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane, (A_{i}, B_{j}), (A_{k}, B_{l}) ∈ E are different edges.

(A_{i}, B_{j}) ≺^{0}_{G} (A_{k}, B_{l}) ⟺^{def} i ≤ k, j ≤ l (A_{i}, B_{j}) ≺^{1}_{G} (A_{k}, B_{l}) ⟺^{def} i < k, j < l

It is easy to verify that ≺^{0}_{G} and ≺^{1}_{G} are partial orderings of E.

The next proposition describes relationship between these partial orderings and the geometry of G(again,III.and IV. are direct consequences of I. and II.).

Proposition 2.3.2. I. Two given edges are ≺^{0}_{G}-comparaple if and only if they are compatible. II. Two given edges are ≺^{1}_{G}-comparaple if and only if they are independent. III. Two given edges are ≺^{0}_{G}-incomparaple if and only if they are crossing. IV. Two given edges are ≺^{1}_{G}-incomparaple if and only if they are weakly crossing.

Now we can describe the chain- and antichain structures of these partial orderings.We use our notations from 1.1,2.3. and 2.5.

Theorem 2.3.3. I. ℂ(≺^{0}_{G}) = ℂ_{G}^{0} , 𝔸(≺^{0}_{G}) = 𝔸_{G}^{0}

II. ℂ(≺^{1}_{G}) = ℂ_{G}^{1} , 𝔸(≺^{1}_{G}) = 𝔸_{G}^{1}

There is a very interesting relationship between the partial orderings of E given by G and those given by Ḡ.By comparing the previous theorem with 2.17. we get Corollary 2.3.4. I. ℂ(≺^{0}Ḡ) = 𝔸(≺^{1}_{G}) = ℂ0 ; Ḡ = 𝔸_{G}^{1} , 𝔸(≺^{0}Ḡ) = ℂ(≺^{1}_{G}) =

𝔸0 ; Ḡ = ℂ_{G}^{1}

II. ℂ(≺^{1}Ḡ) = 𝔸(≺^{0}_{G}) = ℂ1 ; Ḡ = 𝔸_{G}^{0} , 𝔸(≺^{1}Ḡ) = ℂ(≺^{0}_{G}) = 𝔸1 ; Ḡ = ℂ_{G}^{0}

This means that in the poset structures defined on E by ≺^{0}_{G}, ≺^{1}_{G}, ≺^{0}Ḡ and ≺^{1}Ḡ the antichain set of a partial ordering is the chain set of some other partial ordering and vice versa(see also section 5).We now apply the results on partially ordered sets to bipartite graphs in the plane. Proposition 2.3.5. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.Using the algorithm for 1.3. we can effectively compute the following:

• A non-crossing matching of maximum cardinality.

• A non-crossing edge set of maximum cardinality.

• A crossing edge set of maximum cardinality.

• A weakly crossing edge set of maximum cardinality.

• A partition of E into a minimal number of non-crossing matchings.

• A partition of E into a minimal number of non-crossing edge sets.

• A partition of E into a minimal number of crossing edge sets.

• A partition of E into a minimal number of weakly crossing edge sets.

• For every k : k non-crossing matchings with a union of maximum cardinality.

• For every k : k non-crossing edge sets with a union of maximum cardinality.

• For every k : k crossing edge sets with a union of maximum cardinality.

• For every k : k non-crossing edge sets with a union of maximum cardinality.

• A smallest subset E_{0} of E such that every non-crossing matching of maximum cardinality contains an element of E_{0} .

• A smallest subset E_{0} of E such that every non-crossing edge set of maximum cardinality contains an element of E_{0}.

• A smallest subset E_{0} of E such that every crossing edge set of maximum cardinality contains an element of E_{0}.

• A smallest subset E_{0} of E such that every weakly crossing edge set of maximum cardinality contains an element of E_{0}.

• A largest family of pairwise disjoint non-crossing matchings of maximum cardinality.

• A largest family of pairwise disjoint non-crossing edge sets of maximum cardinality.

• A largest family of pairwise disjoint crossing edge sets of maximum cardinality.

• A largest family of pairwise disjoint weakly crossing edge sets of maximum cardinality.

Note that by 2.18. the first four items(i.e.the maximum cardinality edge sets) can also be computed using longest directed path-algorithms.

We also have the corresponding min-max theorems from 1.5-7.We present these for non-crossing matchings;similar equalities hold for non-crossing edge sets,crossing edge sets and weakly crossing edge sets.

Theorem 2.3.6. Let G = (A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.

• The size of the largest non-crossing matching equals the minimum number of weakly crossing edge sets needed to cover E.

• The minimum number of non-crossing matchings needed to cover E equals the size of the largest weakly crossing edge set.

• The maximum number of edges coverable by k non-crossing matchings

equals min{qk + |E − ⋃_{i=1}^{q} A_{i}| : A_{1}, … A_{q} are weakly crossing edge sets}

• The size of the largest family of disjoint non-crossing matchings of maximum cardinality equals the size of the smallest edge set that intersects every non-crossing matching of maximum cardinality.

By 2.17. in the equalities above non-crossing matchings and non-crossing edge sets of Ḡ can be substituted for crossing and weakly crossing edge sets of G.For example,we get

• The size of the largest non-crossing matching in G equals the minimum number of non-crossing edge sets needed to cover E in Ḡ.

• The minimum number of non-crossing matchings in needed to cover E in G equals the size of the largest non-crossing edge set in Ḡ, etc.

We remark that the results on the optimal partition of E into non-crossing matchings and algorithms for the maximum non-crossing matching problem also appeared at [15] and [16],respectively,but without reference to the underlying poset structure. We conclude this section by noting that while the cited results on chains and antichains were selected somewhat arbitrarily,using the framework established above other properties of partially ordered sets can also be interpreted as results on bipartite graphs in the plane.

2.4 Common subwords of two given words

A naturally arising problem in the combinatorics of words is to find the shortest subword distinguishing two given words(i.e. to find a word of minimum length that is a subword of one of the words,but not of the other).Another natural question is to determine a longest common subword of two given words.Using the results of the previous section we will give an algorithmic solution and state and solve some more general problems.We first give the basic definitions of this section.

Definition 2.4.1. Let x and y be two words over the alphabet X with lengths |x| = p and |y| = q.The i^{th} letter of x is denoted by x(i).The reverse of x is x̄ := x(p)x(p − 1) … x(1).A word is a subword of x if it is of the form z = x(i_{1})x(i_{2}) … x(i_{r}) where 1 ≤ i_{1} ≤ i_{2} ≤ ⋯ ≤ i_{r} ≤ p. A word is a common subword of x and y if it is a subword of both x and y.A word is a reversed common subword of x and y if it is a common subword of x and ȳ(note that this definition is asymmetric). A set C ⊂ {1, …, p} × {1, …, q} is a realized common subword of x and y if it is of the following form: C = {(i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{r}, j_{r})}, i_{1} < ⋯ < i_{r}, j_{1} < ⋯ < j_{r} : x(i_{1})x(i_{2}) … x(i_{r}) = y(j_{1})y(j_{2}) … y(j_{r}) =: u(C). We say that C realizes the common subword u(C);the latter is also called the underlying common subword of C.|C| = |u(C)| is called the length of C.The set of realized common subwords of length 1 is denoted by 𝔼(x, y) = {(i, j) : x(i) = y(j)}. A set R ⊂ {1, …, p} × {1, …, q} is a realized reversed common subword of x and y if it is of the following form: R = {(i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{r}, j_{r})}, i_{1} < ⋯ < i_{r}, j_{1} > ⋯ > j_{r}: x(i_{1})x(i_{2}) … x(i_{r}) = y(j_{1})y(j_{2}) … y(j_{r}) =: ū(R).We say that R realizes the reversed common subword ū(R).|R| = |ū(R)| is the length of R. A set C ⊂ {1, …, p} × {1, …, q} is a generalized common subword of x and y if it is of the following form: C = {(i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{r}, j_{r})}, i_{1} ≤ ⋯ ≤ i_{r}, j_{1} ≤ ⋯ ≤ j_{r}: x(i_{1})x(i_{2}) … x(i_{r}) = y(j_{1})y(j_{2}) … y(j_{r}) =: u(C) (note that we defined C as a set,so for k ≠ l i_{k} = i_{l} implies j_{k} ≠ j_{l}).u(C) is called the underlying word of C.We say that C contains a word z if z is a subword of u(C).|C| is called the length of C. A set R ⊂ {1, …, p} × {1, …, q} is a generalized reversed common subword of x and y if it is of the following form: R = {(i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{r}, j_{r})}, i_{1} ≤ ⋯ ≤ i_{r}, j_{1} ≥ ⋯ ≥ j_{r} : x(i_{1})x(i_{2}) … x(i_{r}) = y(j_{1})y(j_{2}) … y(j_{r}) =: ū(R).|R| is called the length of R. Note that the sets of realized reversed common subwords and generalized (reversed) common subwords of length 1 are also all equal to 𝔼(x, y),therefore all these objects can be considered as subsets of 𝔼(x, y).

Realized common subwords are closely related to the notion of the spectrum of words introduced by Milner(see [1]).While this connection is not relevant to our current topic,we mention the following:

Remark. The k-spectrum of a word x is defined as the function s_{k} that associates with each word of length k its number of occurences in x.It is easy to verify that for a word z of length k s_{k}(z) = |{C ∈ ℂ^{1}(x, x) : u(C) = z}|.

The next obvious proposition means that to answer problems related to common subwords it suffices to deal with realized subwords.

Proposition 2.4.2. Let x and y be two arbitrary words.I. A word z is a common subword of x and y if and only if there exists a realized common subword C such that u(C) = z. II. A word z is a reversed common subword of x and y if and only if there exists a realized reversed common subword R such that ū(R) = z.

This also implies that a subword of x is a common subword if and only if it is the underlying subword of a realized common subword;similarly for reversed subwords.The connection between the subword problem and bipartite graphs in the plane can be established via the following construction:

Definition 2.4.3. Let x and y be two words of lengths p and q,respectively. The bipartite graph in the plane associoted with these words is defined as G(x, y) := (A, B, E, f_{A}, f_{b}),where A = {A_{1}, …, A_{p}}, B = {B_{1}, …, B_{q}}, f_{A}(i) = A_{i}, f_{B}(j) = B_{j}, E = {(A_{i}, B_{j}) : (i, j) ∈ 𝔼(x, y)},i.e (A_{i}, B_{j}) ∈ E ⟺ x(i) = y(j).For a subset X ⊂ 𝔼(x, y) let X̃ := {(A_{i}, B_{j}) : (i, j) ∈ X}

Our results are based on the following correspondences which can easily be verified by referring to the definitions 2.3. and 2.5..

Proposition 2.4.4. Let x and y be two arbitrary words. I. C is a realized common subword of x and y if and only if C̃ is a noncrossing matching in G(x, y). II. C is a generalized common subword of x and y if and only if C̃ is a non-crossing edge set in G(x, y). III. R is a realized reversed common subword of x and y if and only if R̃ is a crossing edge set in G(x, y). IV. R is a generalized reversed common subword of x and y if and only if R̃ is a weakly crossing edge set in G(x, y). V. For any subset {A_{i_{1}}, …, A_{i_{r}}} ⊂ A (where i_{1} ≤ … i_{r}) x(i_{1}) … x(i_{r}) is a subword of x and every subword of x is obtainable this way.

Thus we can apply our results from the previous sections.By 2.18. we have

Theorem 2.4.5. Let x and y be two arbitrary words.Then we can effectively compute the following:

• A longest common subword of x and y.

• A longest generalized common subword of x and y.

• A shortest subword of x that is not a subword of y.

• A shortest subword of x that is not contained by a generalized common subword.

It is proved in [19] that a shortest distinguishing subword can in fact be found in linear time.This result is based on some deeper results on subwords including the fact that if two words have the same subwords of length m,they can be merged into a word also having the same subwords of length m.Our algorithm,however,is very elementary,as the following remark shows.

Remark. A shortest subword of x that is not a subword of y and a longest common subword of x and y and can both be found by finding the the shortest directed S − T path and the longest directed path,respectively,in the following acyclic digraph:D_{G(x,y)} = (V, E),where V = {(i, j) : x(i) = y(j)}, E = {((i, j), (k, l)) ∈ V × V | i < k, j < l, ∀j < l′ < l x(k) ≠ x(l′)}, S = {(i, j) ∈ V | ∀j′ < j : x(i) ≠ y(j)}, R = {(i, j) ∈ V | ∀j′ > j : x(i) ≠ y(j)} and T = {(i, j) ∈ V | ∃(k, l) ∈ R : i < k, j ≥ l}.

¿From the poset-related results in 3.5. we also get

Theorem 2.4.6. Let x and y be two arbitrary words.Then we can effectively compute the following(note that by considering ȳ instead of y we can also compute these for reversed subwords:

• A longest common subword of x and y.

• A longest generalized common subword of x and y.

• A partition of 𝔼(x, y) into a minimal number of realized common subwords.

• A partition of 𝔼(x, y) into a minimal number of generalized common subwords.

• For every k : k disjoint realized common subwords of maximum overall length.

• For every k : k disjoint generalized common subwords of maximum overall length.

• A smallest subset of 𝔼(x, y) such that it intersects every realized common subword of maximum length.

• A smallest subset of 𝔼(x, y) such that it intersects every generalized common subword of maximum length.

• A largest family of pairwise disjoint realized common subwords of maximum length.

• A largest family of pairwise disjoint generalized common subwords of maximum length.

Note that by 4.5. the longest (generalized) common subword can also be found using the longest path-algorithm.We also note that finding the longest common subword is equivalent to finding the longest common subseries of two finite series(of lengths n and m),which is a well-studied problem;an algorithm of time O (\frac{mn}{log n}) can be found at [14].

The corresponding min-max theorems will also hold(we only give the results on common subwords;the equalities for generalized common subwords can be obtained similarly):

Theorem 2.4.7. Let x and y be two arbitrary words.The following equalitites hold:

• The length of the longest common subword equals the minimum number of generalized reversed common subwords needed to cover 𝔼(x, y).

• The minimum number of realized common subwords needed to cover 𝔼(x, y) equals the length of the longest generalized reversed common subwords.

• The maximum overall length of k pairwise disjoint realized common sub-

words equals min{qk+|𝔼(x, y)− ⋃_{i=1}^{q} R_{i}| : R_{1}, …, R_{q} are generalized reversed

common subwords}.

• The minimal cardinality of a subset of 𝔼(x, y) intersecting every realized common subword of maximum length equals the size of the largest family of pairwise disjoint realized common subwords.

In this framework theorems on bipartite graphs in the plane can be interpreted as results on the subword problem.We conclude this section by showing that in some sense we have a two-way connection.

Definition 2.4.8. We call a G = (A, B, E, f_{A}, f_{B}) bipartite graph in the plane special if the bipartite graph (A,B,E) can be partitioned into complete bipartite graphs.

Subword-related results can be interpreted as results on special graphs:

Proposition 2.4.9. Let G = A, B, E, f_{A}, f_{B}) be a bipartite graph in the plane.Then G is special if and only if there exist two words x and y over some alphabet X such that G = G(x, y).

Proof. I. If G is special with components G_{1}, …, G_{k};let X := {a_{1}, …; a_{k}}.For every 1 ≤ i ≤ |A| there exists an unique value of j for which A_{i} belongs to G_{j};let x(i) := G_{j} For every 1 ≤ i ≤ |B| there exists an unique value of j for which B_{i} belongs to G_{j};let y(i) := G_{j}.It is easy to verify that G = G(x, y). II. Let x and y be two words over the alphabet X = {a_{1}, …; a_{k}}.Then the j^{th} component of G(x, y) will be the one spanned by the vertex sets {A_{i} : x(i) = a_{j}} and {B_{i} : y(i) = a_{j}}.

We show how this connection works on two examples: According to the result from [19] cited earlier,given two words a shortest distinguishing subword can be found in linear time.This means that for a special graph we can find a minimal subset of a shore not coverable by a non-crossing matching in linear time. Also,it is well known(see for example [11]) that if two words of length n over an alphabet X have the same subwords of length ⌈\frac{n+1}{2}⌉ then they are equal(we can even restrict ourselves to subwords of the form a^{i}b^{j} where a, b ∈ X are two arbitrary letters).By comparing this result with the previous proposition we get

Theorem 2.4.10. Let G = A, B, E, f_{A}, f_{B}) be a special bipartite graph in the plane,|A| = |B| = n.If for every vertex set X of size |X| = ⌈\frac{n+1}{2}⌉ such that either X ⊂ A or X ⊂ B there exists a non-crossing matching covering X then there also exists a non-crossing matching of size n(we can even restrict ourselves to subsets of A or B of the following form:some vertices from a single component of G followed by some vertices from another component).

Note that the previous theorem does not hold for arbitrary bipartite graphs in the plane:let us consider the graph obtained by deleting the first edge (i.e.(A_{1}, B_{1}) ) from the complete bipartite graph K_{n,n};it is easy to see that while every subset of A or B with cardinality n − 1 can be covered by a non-crossing matching there does not exist a non-crossing matching of cardinality n. We conclude by returning to the topic of partial orderings on edge sets of bipartite graphs in the plane and proving an interesting result not strictly connected to the main topics of the paper.

2.5 Dual partial orderings

We have seen that the partial orderings we defined in 3.1. on the edges of a bipartite graph in the plane have dual partial orderings in the following sense:

Definition 2.5.1. The partial orderings ≺^{0} and ≺^{1} are called dual partial orderings if the following property holds: two elements are ≺^{0}-comparable if and only if they are ≺^{1}-incomparable (or,equivalently,if ℂ(≺^{0}) = 𝔸(≺^{1}); note

that this implies 𝔸(≺^{0}) = ℂ(≺^{1})).

By comparing this definition with 3.4. we get

Proposition 2.5.2. Let G be a bipartite graph in the plane.Then I.≺^{0}_{G} and ≺^{1}Ḡ are dual partial orderings. II.≺^{1}_{G} and ≺^{0}Ḡ are dual partial orderings.

It is easy to observe that the partial orderings ≺^{0}_{G} and ≺^{1}_{G} coincide in the following special case:

Proposition 2.5.3. If G is a matching in the plane (that is,it is a bipartite

graph in the plane where every vertex has degree 1),then ≺^{0}_{G}=≺^{1}_{G};in this case

let ≺_{G}:=≺^{0}_{G}=≺^{1}_{G}.

Our aim is to show that if a partial ordering ≺ has a dual partial ordering then it must be of the form ≺=≺_{G} for some G matching in the plane.We need some new notations and definitions:

Definition 2.5.4. We can view a partial ordering ≺ on a set P as the edge set of the directed graph D_{≺} = (P, ≺),where (a, b) is a directed edge if and only if a ≺ b.Let G_{≺} be the undirected graph obtained by making the edges of D_{≺} undirected (i.e.(a, b) is an edge if and only if a and b are ≺-comparable).An undirected graph G is called a comparability graph if G = G_{≺} for some partial ordering ≺.

With this terminology the duality of partial orderings can be described as follows:

Proposition 2.5.5. A partial ordering ≺ has a dual partial ordering if and only if the complementing graph of G_{≺} is a comparability graph (where for a graph G = (V, E) its complementing graph is defined as Ḡ = (V, V × V \ E)).

Note that since comparability graphs can be recognized in polynomial time (see [7]),partial orderings with duals can also be recognized.We need the following concept:

Definition 2.5.6. The dimension dim(≺) of a partial ordering ≺ is the min-

imum number t of linear orderings <_{i} (i = 1 … t) such that ⋂_{i=1}^{t} <_{i}=≺.

Consider the following simple construction:

Proposition 2.5.7. Let ≺ be a partial ordering on the set P with dim(≺) ≤ 2. Then there exists a matching in the plane G such that ≺=≺_{G}.

Proof. If dim(≺) ≤ 2 then there exist two (not necessarily different) linear orderings <_{1} and <_{2} such that <_{1} ∩ <_{2}=≺.Let us suppose that P = {p_{1}, p_{2}, …, p_{n}}, p_{1} <_{1} p_{2} <_{1} ⋯ <_{1} p_{n}.We define G on vertices A = {A_{1}, …, A_{n}}, B = {B_{1}, …, B_{n}} with edges {e_{i} = (A_{i}, B_{j}) : P_{j} is the i^{th} element according to <_{2} }. It is easy to verify that ≺=≺_{G}.

The following theorem gives a characterization of partial orderings with dimension at most 2.A simple and elementary proof can be found at [3].

Theorem 2.5.8. (Dushnik-Miller)Let ≺ be a partial ordering.Then dim(≺) ≤ 2 if and only if the complementing graph of G_{≺} is a comparability graph(i.e. if ≺ has a dual partial ordering).

Comparing this with 5.2. and 5.7. we get

Corollary 2.5.9. Let ≺ be a partial ordering.Then the following are equivalent: I.≺ has a dual partial ordering. II.There exists a bipartite matching in the plane G such that ≺=≺_{G}. III.There exists a bipartite graph in the plane G such that ≺=≺^{0}_{G}. IV.There exists a bipartite graph in the plane G such that ≺=≺^{1}_{G}.

Note that this result implies that for a bipartite graph in the plane G there exist matchings in the plane G′ and G′′ such that ≺^{0}_{G}=≺_{G′} and ≺^{1}_{G}=≺_{G′′}.These matchings can easily be constructed by separating each vertex C of G into deg(C) new vertices of degree 1 each,assigning the edges of C to the new vertices in the natural order to obtain G′ and in reverse order to obtain G′′.This construction also shows that throughout section 3 we can restrict ourselves to matchings in the plane.

References

[1] Choffrut,C. and Karhumaki,J., Combinatorics of words, a chapter in Rozenberg,G. and Salomaa,A.(ed.), Handbook of Formal Languages, Springer-Verlag,Berlin,1997

[2] Dilworth,R.P., A decomposition theorem for partially ordered sets, Ann.of Math.,Vol.51,1950

[3] Dushnik,B. and Miller,E.W., Partially Ordered Sets, Amer.J.Math.63,1941

[4] Fine,N.J. and Wilf,H.S., Uniqueness theorems for periodic functions, Proc.AMS.Vol.16,1965

[5] Ford,L.R. and Fulkerson,D.R., Flows in Networks, Princeton Univ.Press,Princeton,N.J.,1962

[6] Frank,A., On Chain and Antichain Families of a Partially Ordered Set, J.Combinatorial Theory Ser.B,Vol.29,No.2,October 1980

[7] Golumbic,M.C.,The complexity of comparability graph recognition and coloring, Computing 18,1977

[8] Greene,C., Some partitions associated with a partially ordered set, J.Combinatorial Theory Ser.A,Vol 20,1976

[9] Greene,C. and Kleitman,D., The structure of a Sperner k-family, J.Combinatorial Theory Ser.A,Vol 20,1976

[10] Harrison,M.A., Introduction to Formal Language Theory, Addison-Wesley Publ.Co.Reading,Mass.,1978

[11] Lothaire,M., Combinatorics on words, Cambridge Univ.Press,1983

[12] Horváth,S., Fine and Wilf’s theorem is sharp, talk given at 4^{th} Joint Conference on Mathematics and Computer Science,Felix Bath,Romania,2001

[13] Lentin,A., Equations dans les Monoides Libres, Gauthier-Villars,1972

[14] Masek,W.J. and Paterson,M.S., A faster algorithm computing string edit distances, J.Computer and System Sciences,20(1),1980

[15] Malucelli,F. and Nicoloso,S., Optimal partition of a bipartite graph into non-crossing matchings, talk given at Comb’01,Barcelona,2001 [16] Malucelli,F.,Otmann,T. and Pretolani,D., Effective Labelling Algorithms

for the Maximum Non-crossing Matching Problem, Discrete Applied Mathematics Vol.47,1993

[17] Rudolf,G., On the sharpness and generalizations of the Fine-Wilf periodicity theorem, Pure Mathematics and Applications,to appear

[18] Shyr,H.J., Free Monoids and Languages, Hon Min Book Co.,Taichung,Taiwan

[19] Simon,I., An Algorithm to Distinguish Words Efficiently by Their Subwords, manuscript,1983

Contents

1 On the sharpness and generalizations of the Fine-Wilf periodicity theorem 3 1.1 The Fine-Wilf Periodicity Theorem . . . . . . . . . . . . . . . 4 1.2 Bipartite graphs and periodic words . . . . . . . . . . . . . . . 4 1.3 Characterizations of the Fine-Wilf sets . . . . . . . . . . . . . 5 1.4 Minimal Fine-Wilf sets and sharpness

results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Bipartite graphs in the plane and the subword problem 12 2.1 Chains and antichains in partially ordered sets . . . . . . . . . 12 2.2 Bipartite graphs in the plane . . . . . . . . . . . . . . . . . . . 14 2.3 Poset-structures on the edges of a bipartite graph in the plane 21 2.4 Common subwords of two given words . . . . . . . . . . . . . 24 2.5 Dual partial orderings . . . . . . . . . . . . . . . . . . . . . . 29