Overlap number

    A collection S:=(S1, S2, ..., Ss) of subsets of RP1 is disjoint if there are disjoint intervals I1, I2, ..., Is of RP1 such that Si is a subset of Ii, for each i =1, ..., s. A flag F. is a sequence F1, F2, F3, ..., Fn of nested subspaces of Cn where Fi has dimension i. We fix a real rational normal curve g : P1 --> Cn and identify points of RP1 with their images in Rn. A flag F. is secant (to g) if each of its subspaces Fi is generated by its intersections with g(RP1). A collection F.1, F.2, ..., F.s of secant flags are disjoint if the collection of sets Si where the flags F.i meet g(RP1) are disjoint. The secant conjecture asserts that if a Schubert problem on a Grassmannian is given by disjoint secant flags, then all solutions (points of intersection of the corresponding Schubert varieties) are real.
    The overlap number is a measure of the degree of disjointness of a collection S:=(S1, S2, ..., Ss) of subsets of RP1 (or of secant flags). Given a collection I:=(I1, I2, ..., Is) of intervals of RP1 such that Si is a subset of Ii, for each i =1, ..., s, the overlap of (I, S) counts the number of pairs (x,Ii) where x lies in both Ii and in Sj and i is different than j.
[Make Picture]
The overlap number of the collection S is the minimal overlap of any collection I of intervals covering S, where we also require that the union of the intervals in I is not all of RP1. It is not hard to see that a collection S of subsets is disjoint if and only if it has overlap number 0.

    In addition to testing the secant conjecture (Schubert problems given by disjoint flags), we intend to investigate Schubert problems given by secant flags which are not disjoint. Based on Table 1 in Section 2.3.1 of [RSSS], we expect to observe some dependence of the number of real solutions on the degree of lack of disjointness of the secant flags, and will use the overlap number to measure this.
    Even though a secant flag F. is generated by n-1 ordered points of the rational normal curve RP1 (the nth point is unimportant), any given Schubert variety XwF. will not necessarily depend upon all these points, but only a subset of them corresponding to the essential conditions imposed by w. Let n(w) be the number of points of RP1 needed for the Schubert variety Xw. Given a Schubert problem w=(w1, w2, ..., ws), these numbers of points give a composition
a=a(w)=(a1, a2, ..., as):= (n(w1), n(w2), ..., n(ws))
of the number |a|:= a1 + a2 + ... + as. Secant flags for this Schubert problem requre a total of |a| points of RP1 grouped into a set composition S=(S1, S2, ..., Ss) of type a (that is, Si consists of ai of the points).
    Since the overlap number of the collection S of points does not depend upon the actual points of RP1, but rather upon their relative order along RP1, we can compute the overlap number from a pointer from S to such a relative order, which amounts to a set composition of the numbers 0, 1, ..., |a|-1. The overlap number also does not depend upon the order in which the different parts of S occur, and so in fact we need only consider partitions a and set partitions S.
    Since we are using this overlap number to measure how far from disjoint a given set partition S is, it would be good to see how it is distributed among all set partitions, say of a given type. The table below gives bar graphs (with normalized area 1) of the distribution of overlap number among all set compositions of a given type, for some small types.

type = [22222]
type = [2222]
type = [3222]

type = [3322]
type = [4222]
type = [4322]
There are 69,300 set partitions of type [4,3,2,2]. We also computed the overlap number of 5-10 million random instances each of set partitions of other types. Here are their normalized frequency tables.

type = [3322]
type = [333222]
type = [33332222]

type = [3333]
type = [33333]
type = [333333]

type = [3333333]
type = [33333333]
type = [333333333]

type = [4444422222]
type = [5555]
type = [5555555]

type = [666666]
type = [66666666]
type = [65544332]
    Observe that these (particularly those with many parts) are strongly peaked. While overlap number zero is the smallest overlap number, it is not clear what is the largest possible overlap number for a given partition, in general. If all of the parts are the same, say the partition has the form pm := [p,p,p, ... ,p] (repeated m times), then it is an easy exercise that the maximum crossing number is (p-1)m(m-1). Here is a table of these numbers.

m
4 5 6 7 8 9 10
  p     3   24 40 60 84 112 144 180
4 366090 126168216 270
5 48 80120 168 224288 360
6   60   100   150   210   280   360   450

    Challenge Question: for a given partition, what is the maximum overlap number? For example, what is it for [6,5,5,4,4,3,3,2] ?

Markov stepping

    Since we will want to test secant flags with different overlap numbers, the strength of the peaks observed in these data, as well as the mass being concentrated at a moderate overlap number presents a challenge: How to generate set compositions, and thus secant flags, whose overlap numbers are reasonably distributed?
    Chris Hillar suggested one solution: Start with a set composition having zero overlap number, and then run a Markov walk, sampling along the way to the general set composition. More specifically, given a partition and a permutation, we may `cut' the permutation according to the partition to get a set composition. For example,

The partition [4,3,2,2] and permutation (0,9,2,6, 3,1,8, 5,4, 7,10) give the composition [ [0,2,6,9], [1,3,8], [4,5], [7,10] ].

Our Markov chain is simple: apply a random simple transposition to the permutation. Applying some fixed number, N such Markov steps to the identity permutation gives a probability distribution on set compositions, and thus on overlap numbers. We expect that these distributions converge to the actual overlap number distribution as N tends to infinity.
    We display these distributions for the partition [4,3,2,2] in the table below. There, the frequency is always in black. It appears to converge fairly well by N=15 steps, but for all intents and purposes, it has converged by N=5.

One Markov Step
Two Markov steps
Three Markov steps
Four Markov steps

Five Markov steps
Six Markov steps
Seven Markov steps
Eight Markov steps

Ten Markov steps
Twelve Markov steps
Fifteen Markov steps
Twenty Markov steps
    The behaviour of this Markov process is easier to see for the partition [3,3,3,3, 2,2,2,2]. Here are the distributions given by the first four steps. Again, the frequency distribution is in black.

one Markov step
two Markov steps
three Markov steps
four Markov steps

Notice that in the fourth step, the distribution begins to settle down. In steps 4-7, the distribution evens out a little more and begins to move right. (The vertical scale has changed.)

four Markov steps
five Markov steps
six Markov steps
seven Markov steps

It is helpful to overlay these four distributions with the frequency distribution, and also overlay the distributions with 8, 10, 12, 15, and 20 steps with the frequency distribution.

four, five, six, and seven Markov steps
eight, ten, twelve, fifteen, and twenty Markov steps

Note that 20 Markov steps is nearly equal to the frequency distribution.
Here is the Markov process for the partition [5,5,5,5,5,5,5].

one, two, three, four, and five Markov steps
six, seven, eight, nine, and ten Markov steps

eleven, twelve, thirteen, fourteen, and fifteen Markov steps
20, 25, 30, 35, and 40 Markov steps

Evolution of the full Markov process

Now we begin with a set partition having the largest overlap number for the partition [5,5,5,5,5,5,5].

one Markov step
two Markov steps
three Markov steps
four Markov steps

five, six, seven, eight, and ten Markov steps
12, 14, 16, 18, and 20 Markov steps

25, 30, 35, and 40 Markov steps

Here is the Markov process for the partition [3,3,3,3, 2,2,2,2], beginning with a set partition with highest overlap number 81, namely: [ [0,7,14], [2,9,15], [4,10,17], [5,12,19], [1,11], [3,13], [6,16], [8,18] ]

one Markov step
two Markov steps
three Markov steps
four Markov steps

five, six, seven, eight, and ten Markov steps
12, 14, 16, 18, and 20 Markov steps

25, 30, 35, and 40 Markov steps

We now look at the Markov process for the partition [6, 5,5, 4,4, 3,3, 2].

one Markov step
two Markov steps
three Markov steps

one, two, three, four, and five Markov steps
six, seven, eight, ten, and twelve Markov steps

14, 16, 18, 20, and 25 Markov steps
30, 35, 40, 50, and 60 Markov steps


    Here is the Markov process beginning with a partition having overlap number 157, namely [[6,15,16,22,29,31], [0, 4,25,18,10], [1, 8,14,21,27], [3,11,17,26], [5,12,20,28], [9,30,19], [2,13,24], [7,23]]

one Markov step
two Markov steps
three Markov steps

one, two, three, four, and five Markov steps
six, seven, eight, ten, and twelve Markov steps

14, 16, 18, 20, and 25 Markov steps
30, 35, 40, 50, and 60 Markov steps



    Lastly, we diaplay a plot of the Markov process, where we begin with a partition having overlap number 70. It still takes about 40 steps to converge.

Bibliography

[RSSS]   J. Ruffo, Y. Sivan, J. Soprunova, and F. Sottile, Experimentation and conjectures in the real Schubert calculus for flag manifolds, Experimental Mathematics, 15, No. 2 (2006), 199-221.

Modified since: 16 March 2008.