Guy Louchard
email: louchard@ulb.ac.be

Helmut Prodinger
email: hproding@sun.ac.za

A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations

In words, generated by independent geometrically distributed random variables, we study the lth descent, which is, roughly speaking, the lth occurrence of a neighbouring pair ab with a > b. The value a is called the initial height, and b the end height. We study these two random variables (and some similar ones) by combinatorial and probabilistic tools.

We find in all instances a generating function Ψ(v, u), where the coefficient of v j u i refers to the jth descent (ascent), and i to the initial (end) height. From this, various conclusions can be drawn, in particular expected values.

In the probabilistic part, a Markov chain model is used, which allows to get explicit expressions for the heights of the second descent. In principle, one could go further, but the complexity of the results forbids it. This is extended to permutations of a large number of elements.

Methods from q-analysis are used to simplify the expressions. This is the reason that we confine ourselves to the geometric distribution only. For general discrete distributions, no such tools are available.

Introduction

Let X be a random variable (RV), distributed according to the geometric distribution with parameter p (geom(p)): P(X = k) = pq k-1 , with q = 1p. We consider a sequence X 1 X 2 . . . X n of independent RVs. We also speak about words a 1 . . . a n ; there is some interest in combinatorial parameters of such words, generated by independent geometric random variables.

The two most prominent examples are Skip lists and Probabilistic counting (8; 5; 4). In this paper we continue the study of descents.

In a word w 1 abw 2 we say that ab is the lth descent, if a > b (strict model) or a ≥ b (weak model), and the initial word w 1 a has l -1 descents. Furthermore, we refer to a as the initial height and to b as the end height. Equivalently, we use the notions initial value and end value.

In [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF], these random variables were studied, but only for l = 1, i.e., the first descent. Here, we are able to deal with the general case.

This paper uses a generating functions approach and a probabilistic approach. The results complement each other, but are not disjoint. Of course, both are very useful and interesting.

The generating function approach is as follows: First, we construct a generating function F (z, v, u) in 3 variables, z, v, u, where z marks the length of the word, v the number of descents, and u the last letter of the word. In other words,

F (z, v, u) = n,j≥1, l≥0
P[a word of length n has l descents and last letter j]z n v l u j .

Occasionally, it is clearer to write F (u) only.

Once this is achieved, we construct a new generating function (G for initial height, H for end height), by attaching a descent (which is a simple substitution, since the variable u "remembers" the last letter) and an arbitrary rest. In this way, we have a generating function, where the variable u no longer codes the last letter, but the initial height (resp. end height) of the lth descent.

The quantities that we get for l = 1 coincide (of course!) with the older paper; however, they come out in different forms. To show formally that they are the same, one uses identities from q-analysis, such as Heine's transformation formula. This was demonstrated extensively in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF].

We also consider the analogous questions for ascents; the motivation is that, in [START_REF] Knopfmacher | The last descent in samples of geometric random variables and permutations[END_REF], the last descent was studied. In the reversed word, the last descent becomes the first ascent, and now we have developed the machinery to deal in general with the lth ascent.

The probabilistic approach works as follows. We start from an infinite sequence of geometric random variables, with parameter p (geom(p)). First, we consider the successive descents as a Markov chain, related to initial and end values of each descent. Next, we use this Markov chain to obtain the distribution of initial and end values of first and second descents. Then, the first moments of the first and second descents initial values are analyzed by intensive use of some combinatorial identities. Next, we obtain the asymptotic distribution of the number of descents initial values in some interval. Finally, starting from n geom(p) RV, as q → 1, we can derive the asymptotic properties of first and second descents, in a large permutation.

In this part, only the strict model and the descents will be considered. The explicit forms of the distribution of the descents become very complicated when going from first to second etc. descent. However, a stationary distribution, which is very simple, is rapidly approached. It is given by

1 + q q pq i-1 (1 -q i-1 )
for the initial height, and by 1 + q q pq 2i-1

for the end height. There is an intuitive explanation of them: The first one is the conditional probability that we have a pair ij, given that it is a descent, and the second one that we have a pair ji, again given that it is a descent.

Several useful combinatorial identities, derived from Heine's formula, are given in the Appendix.

We will need notation from q-analysis; the most important ones are (x) n := (1x)(1qx) . . . (1xq n-1 ), and n k = (q)n (q) k (q) n-k (Gaussian coefficients). The relevant formulae can be found in [START_REF] Andrews | The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications[END_REF]. Although one could think about performing the present analysis for general discrete distributions,we refrain from doing so. The reason is this: Methods from q-analysis are used to simplify the expressions, and this is very special to the geometric distribution. In general, no such tools are available.

Part I Combinatorial Analysis

2 Descents: the weak model Let f i (u) be the generating function with [z n u j ]f i (u) is the probability that a word of length n ≥ 1 has i descents, and that the last letter is j. (Only the dependency on the variable u has been made explicit.)

Here is the recursion for i ≥ 1.

f i (u) = puz 1 -qu f i-1 (1) - puz 1 -qu f i-1 (uq) + puz 1 -qu f i (uq).
This is a typical application of the adding-a-new slice technique: The variable u keeps track of the last letter in the word. So, if we replace u m by

1≤j≤m pq j-1 u j = pu 1 -(qu) m 1 -qu ,
it means that we gain one descent, and if we replace it by

j>m pq j-1 u j = pu (qu) m 1 -qu ,
we stay with the same number of descents. Translating this principle to the generating functions f i (u), gives the indicated recursion. We will use this principle in various places again. Now let

F (u) = F (z, v, u) = i≥0 f i (u)v i .
Then we get, by summing up,

F (u) -f 0 (u) = puvz 1 -qu F (1) - puvz 1 -qu F (uq) + puz 1 -qu F (uq) - puz 1 -qu f 0 (uq). But f 0 (u) = puz 1 -qu + puz 1 -qu f 0 (uq)
and so

F (u) = puz 1 -qu + puvz 1 -qu F (1) + puz(1 -v) 1 -qu F (uq).
This functional equation can be solved by iterating it: (Technically, this iteration leads to an equation involving F (u) and F (1); after plugging in u = 1, the quantity F (1) can be found, and thus in the next step F (u).

) (i) F (z, v, u) = k≥1 (puz) k (1-v) k q ( k 2 ) (qu) k 1 -v k≥0 (pz) k (1-v) k q ( k 2 ) (q) k . (2.1)
Now we turn to the end heights. We want to obtain the generating function

H(z, v, u) = n,j,i≥1
P[in a word of length n, the jth descent has end height i]z n v j u i .

As indicated already, it can be obtained from F (z, v, u) by substitution: we make one down step, record its height with the u-variable, (u j → pu + pqu 2 + • • • + pq j-1 u j ) and then attach anything (1/(1z)). This gives the generating function

H(z, v, u) = puvz 1 -qu [F (z, v, 1) -F (z, v, uq)] 1 1 -z + pzu 1 -qu .
The next step is to look at the behaviour for n → ∞. Intuitively, it is quite clear, there should be a limit, since what happens at the lth descent must become independent of letters very far to the right. Indeed, we see that there is a simple pole at z = 1, and the generating function

Ψ(v, u) = puv 1 -qu [F (1, v, 1) -F (1, v, uq)], (2.2)
is obtained from H(z, v, u) by dropping the factor 1/(1-z), and the irrelevant additive term and replacing z = 1. Thus, considering u and v as parameters, there is a dominant simple pole, and its residue (that we call Ψ(v, u)) corresponds to the the limit n → ∞, or, what amounts to the same, to an infinite word.

One could perhaps avoid dealing with n and z and deal with an infinite word directly, as we will do in the second part of this paper, but we would lose information in that way that we can have for free. -The coefficient of v l in Ψ(v, u) is a probability generating function in the variable u alone. Indeed, it is easy to check that Ψ(v, 1) = v 1-v . Explicit expressions become very messy, but at least the instance l = 1 (which was studied in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF]) is manageable:

[v 1 ]Ψ(v, u) = pu 1 -qu [F (1, 0, 1) -F (1, 0, uq)] = pu 1 -qu k≥1 p k q ( k 2 ) (q) k - k≥1 (pqu) k q ( k 2 ) (q 2 u) k .
(i) As a referee has pointed out, such functional equations are not always as "smooth" as this one.

From a probability generating function, all moments (of the underlying random variable) can be derived by differentiations, followed by u = 1. Let us just do this for the average (first moment):

E[first descent] ∼ 1 p - ∂ ∂u k≥1 (pqu) k q ( k 2 ) (q 2 u) k u=1 ∼ 1 p - k≥1 k(pq) k q ( k 2 ) (q 2 ) k - k≥1 (pq) k q ( k 2 ) (q 2 ) k k+1 i=2 q i 1 -q i ∼ 1 p - k≥2 (k -1)p k q ( k 2 ) (q) k - k≥2 p k q ( k 2 ) (q) k k i=2 q i 1 -q i .
(2.3)

Note that this average was given as

1 p - h≥0 (h + 1)pq 2h+1 (-p) h (2.4)
in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF].

For the limiting behaviour of this, as q → 1, we should consider lim q→1 (1q)E[first descent]. It turns out that this tends to a constant, and thus the expectation of the end height of the first descent goes to infinity as constant 1-q :

1 -

k≥1 1 k! k i=2 1 i = 1 - k≥1 H k k! + k≥1 1 k! = e - k≥1 H k k! .
A similar computation can be done for general l:

∂ ∂u Ψ(v, u) u=1 = v p [F (1, v, 1) -F (1, v, q)] -v ∂ ∂u F (1, v, uq) u=1 = v p 1 1 -v k≥0 p k (1-v) k q ( k 2 ) (q) k k≥1 p k (1 -v) k q ( k 2 ) (q) k - k≥1 (pq) k (1 -v) k q ( k 2 ) (q 2 ) k -v 1 1 -v k≥0 p k (1-v) k q ( k 2 ) (q) k k≥1 k(pq) k (1 -v) k q ( k 2 ) (q 2 ) k - k≥1 (pq) k (1 -v) k q ( k 2 ) (q 2 ) k k+1 j=2 q j 1 -q j .

And now

lim q→1 (1 -q) ∂ ∂u Ψ(v, u) u=1 = v 1 -ve 1-v e 1-v -1 - 1 1 -v e 1-v -1 -(1 -v) + v 1 -ve 1-v k≥1 (1 -v) k (H k+1 -1) (k + 1)! = -1 + 1 1 -ve 1-v - v 1 -ve 1-v k≥1 H k (1 -v) k-1 k! .
(The coefficient of v 1 is the previous expression).

Now we turn to the initial heights. The same approach applies, but the substitution is even simpler. We get

G(z, u, v) = vz[F (z, v, u) -F (z, v, uq)] 1 1 -z + pzu 1 -qu .
The limit for n → ∞ leads then to the generating function

Φ(v, u) = v[F (1, v, u) -F (1, v, uq)]. (2.5)
Let us compute again the instance l = 1; the coefficient of v 1 is particularly simple:

[v 1 ]Φ(v, u) = F (1, 0, u) -F (1, 0, uq).
From this, we find that the average is asymptotic to

∂ ∂u k≥1 (pu) k q ( k 2 ) (qu) k - k≥1 (pqu) k q ( k 2 ) (q 2 u) k u=1 .
(2.6)

This checks with the expression

h≥0 (h + 1)pq h+1 (-p) h - h≥0 (2h + 1)pq h+1 (-p) h , (2.7)
given in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF].

For the limit lim q→1 (1q)E we get the generating function

1 v(1 -ve 1-v ) - 1 v(1 -v) - v 1 -ve 1-v k≥1 H k (1 -v) k-1 k! . The coefficient of v in this is e -1 - k≥1 H k k! .
3 Descents: the strict model

Computations are similar; we only give the key steps. The functional equation is

F (u) = puz 1 -qu + puvz 1 -qu F (1) + pz(1 -v) q(1 -qu) F (uq).
Thus

F (z, v, u) = u k≥1 (pz) k (1 -v) k-1 (uq) k 1 + vF (z, v, 1) = u k≥1 (pz) k (1-v) k (uq) k 1 -v k≥0 (pz) k (1-v) k (q) k . (3.1)
Also,

H(z, v, u) = puvz 1 -qu F (z, v, 1) - pvz q(1 -qu) F (z, v, uq) 1 1 -z + pzu 1 -qu . Hence Ψ(v, u) = puv 1 -qu F (1, v, 1) - pv q(1 -qu) F (1, v, uq). (3.2)
And

[v 1 ]Ψ(v, u) = pu 1 -qu F (1, 0, 1) - p q(1 -qu) F (1, 0, uq) = pu 1 -qu k≥1 p k (q) k - pu 1 -qu k≥1 p k (uq 2 ) k .
The expectation can be obtained by differentiation, followed by u = 1:

1 p - k≥1 p k (q) k k i=2 q i 1 -q i . (3.3)
The formula given in ( 6) is

1 p - h≥1 hq 2h-1 (pq) h . (3.4)
Now, let us compute the limit of (1q)E, q → 1:

1

- k≥1 H k -1 k! = e - k≥1 H k k! .
And in general:

1 1 -ve 1-v - 1 1 -v - v 1 -ve 1-v k≥2 H k (1 -v) k-1 k! .
Now, for the initial heights, we must consider

G(z, v, u) = vz[F (z, v, u) - 1 q F (z, v, qu)] 1 1 -z + pz 1 -qu , and
Φ(v, u) = v[F (1, v, u) -1 q F (1, v, qu)]. (3.5)
Furthermore, to look at the first descent,

[v 1 ]Φ(v, u) = F (1, 0, u) -1 q F (1, 0, qu) = u k≥1 p k (qu) k -u k≥1 p k (q 2 u) k .
From this, the average, obtained by differentiation, is

1+ k≥1 p k (q) k k i=1 q i 1 -q i - k≥1 p k (q 2 ) k k+1 i=2 q i 1 -q i = 1 + k≥1 p k (q) k k i=1 q i 1 -q i - k≥2 p k (q) k k i=2 q i 1 -q i = 1 + q p k≥1 p k (q) k = 1 + q p -1 + 1 (p) ∞ . (3.6)
The last simplification was by (A.6). The version given in ( 6) is

1 + h≥1 hpq h-1 (pq) h - h≥1 hpq 2h-1 (pq) h . (3.7)
The limiting function

lim q→1 (1 -q)E is v 1 -ve 1-v k≥1 (1 -v) k H k k! - k≥1 (1 -v) k (H k+1 -1) (k + 1)! .
4 Ascents: the strict model First, we consider the case where only a < b is an ascent. Again, the treatment is very similar to before, so we only give the key steps. Let f i (u) be the generating function with [z n u j ]f i (u) is the probability that a word of length n ≥ 1 has i ascents, and that the last letter is j.

Here is the recursion for i ≥ 1:

f i (u) = puz 1 -qu f i (1) - puz 1 -qu f i (uq) + puz 1 -qu f i-1 (uq).
The explanation is similar to before: The variable u keeps track of the last letter, and thus, if we replace

u m by 1≤j≤m pq j-1 u m = pu 1 -(qu) m 1 -qu ,
we stay with the same number of ascents, but if we replace u m by

j>m pq j-1 u m = pu (qu) m 1 -qu ,
we gain one descent.

Now let

F (u) = F (z, v, u) = i≥0 f i (u)v i .
Then we get

F (u) = puz 1 -qu + puz 1 -qu F (1) + puz(v -1) 1 -qu F (uq).
This functional equation can be solved by iterating it:

F (z, v, u) = k≥1 (puz) k (v-1) k-1 q ( k 2 ) (qu) k 1 -k≥1 (pz) k (v-1) k-1 q ( k 2 ) (q) k . (4.1)
Further,

H(z, v, u) = puzv 1 -qu F (z, v, uq) 1 1 -z + puz 1 -qu , and
Ψ(v, u) = puv 1 -qu F (1, v, uq). (4.2)
The case of the first accent, i.e., the coefficient of v 1 , is thus

[v 1 ]Ψ(v, u) = pu 1 -qu F (1, 0, uq) = pu 1 -qu k≥1 (pqu) k (-1) k-1 q ( k 2 ) (q 2 u) k 1 -k≥1 p k (-1) k-1 q ( k 2 ) (q) k = k≥2 (pu) k (-1) k q ( k 2 ) (qu) k k≥0 p k (-1) k q ( k 2 ) (q) k . Notice that k≥0 p k (-1) k q ( k 2 ) (q) k = (p) ∞ .
And therefore the average of the end height of the first ascent tends to

1 (p) ∞ k≥2 kp k (-1) k q ( k 2 ) (q) k + 1 (p) ∞ k≥2 p k (-1) k q ( k 2 ) (q) k k i=1 q i 1 -q i . (4.3)
This quantity appears in [START_REF] Knopfmacher | The last descent in samples of geometric random variables and permutations[END_REF] in the form

q p + 1 (p) ∞ h≥0 (h + 2)pq 2h+1 (p) h . (4.4) Furthermore, G(z, v, u) = vzF (z, v, uq) 1 1 -z + puz 1 -qu , and Φ(v, u) = vF (1, v, uq). (4.5)
Also,

[v 1 ]Φ(v, u) = F (1, 0, uq) = 1 (p) ∞ k≥1 (pqu) k (-1) k-1 q ( k 2 ) (q 2 u) k .
And therefore the average of the initial height of the first ascent tends to

1 (p) ∞ k≥2 (k -1)p k (-1) k q ( k 2 ) (q) k + 1 (p) ∞ k≥2 p k (-1) k q ( k 2 ) (q) k k i=2 q i 1 -q i . (4.6)
The version given in the paper ( 6) is

1 (p) ∞ h≥0 (h + 1)pq 2h+1 (p) h . (4.7)
5 Ascents: the weak model

For completeness, we only collect the relevant formulae here. This brief section is for reference only, and can be skipped, as the methods are the same as before.

F (u) = puz 1 -qu + puz 1 -qu F (1) + pz(v -1) q(1 -qu) F (uq), F (z, v, u) = u k≥1 (pz) k (v-1) k-1 (qu) k 1 -k≥1 (pz) k (v-1) k-1 (q) k . H(z, v, u) = pzv q(1 -qu) F (z, v, uq) 1 1 -z + pz 1 -qu , Ψ(v, u) = pv q(1 -qu) F (1, v, uq), (5.1)
G(z, v, u) = zv q F (z, v, uq) 1 1 -z + pz 1 -qu , Φ(v, u) = v q F (1, v, uq). (5.2)

Summary of results from combinatorial analysis

For the reader's convenience, we list where the generating function Ψ(v, u), that we consider to be the most important finding, as it contains all the information, can be found: (Recall that the coefficient of v j u i refers to the jth descent (ascent), and the probability that the end height (initial height) is i, in an infinitely long string.) The auxiliary functions and the averages can be found in the text.

Part II

Probabilistic Analysis

We will analyze the descents in the strict model with probabilistic tools. We start from an infinite sequence of geom(p) RVs.

Markov chains

In this section, we consider the successive descents as a Markov chain, related to initial and end values of each descent. Let

π(i) := pq i-1 , P (i) := j≥i π(j) = q i-1 ,
I k := beginning of the kth descent (initial height),

J k := end of the kth descent (end height),

I k > J k , I k+1 ≥ J k , I k ≥ 2.
By convention, J 0 is the first geom(p) RV. We have

P[I 2 = i 2 , J 2 = j 2 |I 1 = i 1 , J 1 = j 1 ] = l≥0 j1≤k2≤•••≤k l ≤i2 π(k 2 ) . . . π(k l )π(i 2 )π(j 2 ),
with the conventions

l = 0 : i 2 ≡ j 1 , l = 1 : i 2 ≥ j 1 .
This is independent of i 1 . Set

A(a, b, t) := a≤k1≤•••≤kt≤b q k1+•••+kt , and
B(a, b) := t≥0 p q t A(a, b, t).
Then

P[I 2 = i 2 , J 2 = j 2 |J 1 = j 1 ] = [[i 2 = j 1 ]]π(j 2 ) + B(j 1 , i 2 )π(i 2 )π(j 2 ).
But we know that

0≤k1≤•••≤kt≤n q k1+•••+kt = 1 (q) t t j=0 (-1) j t j q jn+( j+1 2 ) = n + t t .
Recall that n m denotes the q-binomial (Gaussian) coefficients. Therefore

A(a, b, t) := a≤k1≤•••≤kt≤b q k1+•••+kt = q at 0≤k1≤•••≤kt≤b-a q k1+•••+kt = q at b -a + t b -a .
We will use

t≥0 α t m + t m = 1 (α) m+1 . Then B(a, b) := t≥0 p q t A(a, b, t) = (p) a-1 (p) b ,
and

P[I 2 = i 2 , J 2 = j 2 |J 1 = j 1 ] = [[i 2 = j 1 ]]π(j 2 ) + (p) j1-1 (p) i2 π(i 2 )π(j 2 ), (7.1)
P[I 2 = i 2 |J 1 = j 1 ] = [[i 2 = j 1 ]](1 -q i2-1 ) + (p) j1-1 (p) i2 π(i 2 )(1 -q i2-1 ). (7.
2)

The transition matrix between I 1 and I 2 is given by

P[I 2 = i 2 |I 1 = i 1 ] = j1<i1 π(j 1 ) 1 -P (i 1 ) P[I 2 = i 2 |J 1 = j 1 ] = [[i 2 < i 1 ]] π(i 2 ) 1 -P (i 1 ) (1 -q i2-1 ) + j1<i1,j1≤i2 π(j 1 ) 1 -P (i 1 ) (p) j1-1 (p) i2 π(i 2 )(1 -q i2-1 ). (7.3) Let us first check that i2≥2 P[I 2 = i 2 |I 1 = i 1 ] = 1.
We have, using (A.8)

i1-1 i2=2 pq i2-1 1 -q i1-1 (1 -q i2-1 ) + i2≥2 j1<i1,j1≤i2 pq j1-1 1 -q i1-1 (p) j1-1 (p) i2 pq i2-1 (1 -q i2-1 ) = i1-1 i2=2 pq i2-1 1 -q i1-1 - i1-1 i2=2 pq i2-1 1 -q i1-1 q i2-1 + i2≥2 p 1 -q i1-1 1 (p) i2 pq i2-1 (1 -q i2-1 ) + i1-1 j1=2 i2≥j1 pq j1-1 1 -q i1-1 (p) j1-1 (p) i2 pq i2-1 (1 -q i2-1 ) = 1 1 -q i1-1 [1 -p -q i1-1 ] - i1-1 i2=2 pq i2-1 1 -q i1-1 q i2-1 + p 1 -q i1-1 + 1 1 -q i1-1 i1-1 j1=2 pq j1-1 q j1-1 = 1.
Now we compute the stationary measure ϕ(i) of this matrix. (see, for instance, Chung (3)). We must have

i1 ϕ(i 1 )P[I 2 = i 2 |I 1 = i 1 ] = ϕ(i 2 ), which leads to i1>i2 ϕ(i 1 ) pq i2-1 1 -q i1-1 (1 -q i2-1 ) + i1≥2 ϕ(i 1 ) j1<i1,j1≤i2 pq j1-1 1 -q i1-1 (p) j1-1 (p) i2 pq i2-1 (1 -q i2-1 ) = ϕ(i 2 ),
or, setting

ψ(i) = ϕ(i) pq i-1 (1 -q i-1 ) , we have i1>i2 pq i1-1 ψ(i 1 ) + i1≥2 pq i1-1 ψ(i 1 ) j1<i1,j1≤i2 pq j1-1 (p) j1-1 (p) i2 = ψ(i 2 ).
After some algebra, we will find that ψ(i) = constant is a solution of this equation. But it is probabilistically obvious: the stationary distribution is proportional to pq i-1 (1q i-1 ). We have, setting ψ ≡ 1,

i1>i2 pq i1-1 + i1≥2 pq i1-1 j1<i1,j1≤i2 pq j1-1 (p) j1-1 (p) i2 = q i2 + 1 (p) i2 i2 j1=1 pq j1-1 (p) j1-1 q j1 = q i2 + 1 (p) i2 pq m≥0 q 2m (p) m - 1 (p) i2 pqq 2i2 (p) i2 v≥0 q 2v (pq i2 ) v = q i2 + (pq i2 ) ∞ + 1 -q i2 -(pq i2 ) ∞ = 1,
as expected. (We used (A.5) twice.)

The stationary distribution is given by f stationary (i) = 1 + q q pq i-1 (1q i-1 ).

(7.4)

The stationary distribution generating function is given by

G(z) = p 2 (1 + q)z 2 (1 -qz)(1 -q 2 z) ,
from which the stationary moments are easily derived:

E(I) = 2 + q 1 -q 2 , E(I 2 ) = q 3 + 4q 2 + 5q + 4 (1 -q 2 ) 2 .
The stationary distribution of the end value is given by

1 + q q ∞ i1=i2+1 pq i1-1 (1 -q i1-1 )pq i2-1 /(1 -q i1-1 ) = (1 + q)pq 2i2-2 , i 2 ≥ 1,
which sums correctly to 1.

Another transition matrix of interest is given by

P[J 2 = j 2 |J 1 = j 1 ] = π(j 2 )[[j 2 < j 1 ]] + i2≥j1,i2>j2
(p) j1-1 (p) i2 π(i 2 )π(j 2 ). (7.5)

Descent distributions

In this section, we use the Markov chain derived in the previous section to obtain the distribution of initial and end values of first and second descents. For the first descent initial value I 1 , for example, with (A.9), we have

f 1 (i 1 ) := P[I 1 = i 1 ] = i1 j0=1 pq j0-1 P[I 1 = i 1 |J 0 = j 0 ] = pq i1-1 (1 -q i1-1 ) + i1 j0=1 pq j0-1 (p) j0-1 (p) i1 pq i1-1 (1 -q i1-1 ) = pq i1-1 (1 -q i1-1 ) 1 (p) i1 . (8.1)
A graph of f 1 (i), q = 0.7 is given in Figure 1 Fig. 1:

f1(i), q = 0.7 ∞ i=2 f 1 (i) = 1. Indeed i≥2 pq i-1 (1 -q i-1 ) 1 (p) i = 1, by (A.4).
A comparison between f 1 (i) and the stationary distribution f stationary (i), q = 0.7 is given in Figure 2.

For the end height of the first descent, we have, with (A.9) and (A.10),

γ 1 (j 1 ) := P[J 1 = j 1 ] = j0>j1 pq j0-1 pq j1-1 + i1>j1 i1 j0=1 pq j0-1 (p) j0-1 (p) i1 pq i1-1 pq j1-1 = pq j1-1 1 (p) ∞ - 1 (p) j1 . (8.2)
Of course j≥1 γ 1 (j) = 1, by (A.10).

Note that we also have, with (A.10),

γ 1 (j 1 ) = ∞ i1=j1+1 f 1 (i 1 ) π(j 1 ) 1 -P (i 1 ) = ∞ i1=j1+1 pq i1-1 (1-q i1-1 ) 1 (p) i1 pq j1-1 1 -q i1-1 = pq j1-1 1 (p) ∞ - 1 (p) j1 .
The distribution of the second descent (I 2 , J 2 ) is given by the square of the Markov matrix, i.e.

γ 2 (i 2 , j 2 ) = j0≥1 pq j0-1 j1≥1 P[J 1 = j 1 |J 0 = j 0 ]P[I 2 = i 2 , J 2 = j 2 |J 1 = j 1 ]. 0
• : f 1 (i) line : f stationary (i)
Fig. 2: Comparison between f1(i) and fstationary(i), q = 0.7

The distribution of the next descents is related to successive powers of the transition matrix.

A compact form for γ 2 (i 2 , j 2 ) is given below. Now, the distribution of the initial value of the second descent I 2 is given by (we use (A.3), (A.9), (7.3))

f 2 (i 2 ) := P[I 2 = i 2 ] = ∞ i1=2 f 1 (i 1 )P[I 2 = i 2 |I 1 = i 1 ] = ∞ i1=2 pq i1-1 (1 -q i1-1 ) 1 (p) i1 P[I 2 = i 2 |I 1 = i 1 ] = i1>i2 pq i1-1 (1 -q i1-1 ) 1 (p) i1 pq i2-1 1 -q i1-1 (1 -q i2-1 ) + i1≥2 pq i1-1 (1 -q i1-1 ) 1 (p) i1 j1<i1,j1≤i2 pq j1-1 1 -q i1-1 (p) j1-1 (p) i2 pq i2-1 (1 -q i2-1 ) = pq i2-1 (1 -q i2-1 ) 1 (p) i2-1 (1 -pq i2-1 ) 1 (pq i2 ) ∞ -1 + pq i2-1 (1 -q i2-1 ) 1 (p) i2 i2 j1=1 pq j1-1 (p) j1-1 i1>j1 pq i1-1 1 (p) i1 = pq i2-1 (1 -q i2-1 ) 1 (p) i2-1 (1 -pq i2-1 ) 1 (pq i2 ) ∞ -1 + pq i2-1 (1 -q i2-1 ) 1 (p) i2 i2 j1=1 pq j1-1 1 1 -pq j1-1 1 (pq j1 ) ∞ -1 = pq i2-1 (1 -q i2-1 ) 1 (p) i2 1 (pq i2 ) ∞ -1 + pq i2-1 (1 -q i2-1 ) 1 (p) i2 i2 j1=1 pq j1-1 1 (pq j1-1 ) ∞ - 1 1 -pq j1-1 = pq i2-1 (1 -q i2-1 ) 1 (p) ∞ - 1 (p) i2 + p 2 q i2-1 (1 -q i2-1 ) 1 (p) i2 1 (p) ∞ i2-1 j1=0 q j1 (p) j1 -p 2 q i2-1 (1 -q i2-1 ) 1 (p) i2 i2-1 j1=0 q j1 1 -pq j1 = pq i2-1 (1 -q i2-1 ) 1 (p) ∞ - 1 (p) i2 + pq i2-1 (1 -q i2-1 ) 1 (p) i2 1 (p) ∞ [1 -(p) i2 ] -p 2 q i2-1 (1 -q i2-1 ) 1 (p) i2 i2-1 j1=0 q j1 1 -pq j1 = pq i2-1 (1 -q i2-1 ) 1 (p) i2 1 (p) ∞ -1 -p 2 q i2-1 (1 -q i2-1 ) 1 (p) i2 i2-1 j1=0 q j1 1 -pq j1 .
Note that this gives an explicit expression for γ 2 (i 2 , j 2 ):

γ 2 (i 2 , j 2 ) = f 2 (i 2 ) π(j 2 ) 1 -P (i 2 )
.

A comparison between f 2 (i) and f stationary (i), q = 0.7 is given in Figure 3. The convergence to the stationary distribution is quite fast. Let us check that ∞ i=2 f 2 (i) = 1. We have, using (A.8) and (A.1)

∞ i=2   pq i-1 (1 -q i-1 ) 1 (p) i 1 (p) ∞ -1 -p 2 q i-1 (1 -q i-1 ) 1 (p) i i-1 j1=0 q j1 1 -pq j1   = 1 (p) ∞ -1 - j1≥1 p 2 q j1 1 -pq j1 i≥j1+1 q i-1 (1 -q i-1 ) 1 (p) i -p 2 1 1 -p i≥2 q i-1 (1 -q i-1 ) 1 (p) i = 1 (p) ∞ -1 - j1≥1 p 2 q j1 1 -pq j1 q j1 p(p) j1 -p 2 1 1 -p 1 p = 1.

The moments of descent parameters

The first moments of the first and second descents initial values are analyzed here by intensive use of some combinatorial identities. We derive the mean of the initial value of the first descent I

• : f 2 (i) line : f stationary (i)
Fig. 3: Comparison between f2(i) and fstationary(i), q = 0.7

E(I 1 ) = ∞ i=2 f 1 (i)i = i≥2 pq i-1 (1 -q i-1 ) 1 (p) i i = p i≥1 q i-1 i (pq) i -p i≥1 q 2i-1 i (pq) i + p i≥1 q i (p) i+1 (1 -q i ) = p i≥1 q i-1 i (pq) i -p i≥1 q 2i-1 i (pq) i + 1 by (A.4). (9.1)
This is Theorem 3 in (6). However, we want to show now independently that this coincides with the closed form obtained earlier as (3.6). This is done in Appendix (B).

More generally higher moments are given by

E(I k 1 ) = h≥1 pq h (1 -q h )(h + 1) k + ∞ i1=2 i1 j0=1 pq j0-1 (p) j0-1 pq i1-1 (p) i1 (1 -q i1-1 )i k 1 .
Let us look at the modified second moment of I 1 (again we use (A.3), (A.1) for simplifications):

EE(I 1 ) = ∞ i=2 f 1 (i)i(i + 1)/2 = p i≥0 q i (p) i+1 (1 -q i )(i + 1)(i + 2)/2 = p 0≤k≤h i≥h q i (p) i+1 (1 -q i ) = 1 q 0≤k≤h q h (pq) h - p q 0≤k≤h q 2h (pq) h = 1 q k≥0 q k (pq) k h≥0 q h (pq k+1 ) h - p q k≥0 q 2k (pq) k h≥0 q 2h (pq k+1 ) h = 1 q k≥0 q k (pq) k 1 pq k (pq k+1 ) ∞ + 1 - 1 pq k - p q k≥0 q 2k (pq) k 1 pq 2k 1 (pq k+1 ) ∞ - 1 pq 2k - 1 pq k-1 + 1 = 1 q k≥0 1 (pq) k 1 p(pq k+1 ) ∞ + q k - 1 p - 1 q k≥0 1 (pq) k 1 (pq k+1 ) ∞ -1 -q k+1 + pq 2k = 1 q k≥0 1 (pq) k 1 p(pq k+1 ) ∞ + q k - 1 p - 1 (pq k+1 ) ∞ + 1 + q k+1 -pq 2k = 1 q k≥0 1 (pq) k q p(pq k+1 ) ∞ - q p + q k (1 + q) -pq 2k = 1 p k≥0 1 (pq) k 1 (pq k+1 ) ∞ -1 + 1 + q q k≥0 q k (pq) k - p q k≥0 q 2k (pq) k = 1 p k≥0 1 (pq) ∞ - 1 (pq) k + 1 + q q 1 p(pq) ∞ + 1 - 1 p - p q 1 p 1 (pq) ∞ - 1 p - q p + 1 = 1 p k≥0 1 (pq) ∞ - 1 (pq) k + 2 p(pq) ∞ + 3 - 2 p = 1 p lim t→1 1 (pq) ∞ 1 1 -t - k≥0 t k (pq) k + 2 p(pq) ∞ + 3 - 2 p .
In Appendix (C), we show that

lim t→1 1 (pq) ∞ 1 1 -t - k≥0 t k (pq) k = 1 (pq) ∞ k≥1 [1 -(p) k ]q k 1 -q k .
So finally:

EE(I 1 ) = 1 p(pq) ∞ k≥1 [1 -(p) k ]q k 1 -q k + 2 p(pq) ∞ + 3 - 2 p .
From this, the variance can be stated as:

2EE(I 1 ) -2E(I 1 ) -E 2 (I 1 ).
Now we turn to the second descent. The mean E(I 2 ) of the initial value of the second descent is given by (we use (3.6) and (9.1)

E(I 2 ) = ∞ i=2 f 2 (i)i = p 1 (p) ∞ -1 i≥1 iq i-1 (1 -q i-1 ) 1 (p) i - i≥1 ip 2 q i-1 (1 -q i-1 ) 1 (p) i i-1 j=0 q j 1 -pq j = p 1 (p) ∞ -1 i≥0 (i + 1)q i (1 -q i ) 1 (p) i+1 -p 2 j≥0 q j 1 -pq j i≥j (i + 1)q i (1 -q i ) 1 (p) i+1 = 1 (p) ∞ -1 1 - q p + q p(p) ∞ -p j≥0 pq j 1 -pq j i≥j (i + 1)q i (1 -q i ) 1 (p) i+1 = 1 (p) ∞ -1 - j≥0 pq j 1 -pq j 1 - q p + q p(p) ∞ + p j≥0 pq j 1 -pq j 0≤i<j (i + 1)q i (1 -q i ) 1 (p) i+1 .
The last inner sum is computed in Appendix (D) as S 0 . This gives a first expression for the mean:

E(I 2 ) = 1 p 1 (p) ∞ -1 - j≥0 pq j 1 -pq j 2p -1 + q (p) ∞ + 1 p j≥0 pq j 1 -pq j 2p -1 + q (p) j+1 - p(1 + q)q j q(p) j+1 + p 2 q 2j q(p) j - pjq j (p) j+1 + jp 2 q 2j (p) j+1 = 1 p 1 (p) ∞ -1 2p -1 + q (p) ∞ + 1 p j≥0 pq j 1 -pq j q (p) j+1 - q (p) ∞ - p(1 + q)q j q(p) j+1 + p 2 q 2j q(p) j - pjq j (p) j+1 + jp 2 q 2j (p) j+1 = 1 p 1 (p) ∞ -1 2p -1 + q (p) ∞ + 1 p j≥0 pq j 1 -pq j q (p) j+1 - q (p) ∞ - p(1 + q)q j q(p) j+1 - pjq j (p) j+1 + jp 2 q 2j (p) j+1 + 1 p j≥0 p 3 q 3j q(p) j+1 .
The last sum can be simplified, using S 3 from Appendix (D). Hence

E(I 2 ) = 1 p 1 (p) ∞ -1 2p -1 + q (p) ∞ + 1 p j≥0 pq j 1 -pq j q (p) j+1 - q (p) ∞ - p(1 + q)q j q(p) j+1 - 1 p j≥0 jp 2 q 2j (p) j+1 + 1 p (q) 3 q 2 (p) ∞ -q(q -p)(q) 3 -(q -p)(q) 3 - p 2 (q -p)(1 -q 3 ) q .
Again, using S 4 from Appendix (D), we obtain

E(I 2 ) = 1 p 1 (p) ∞ -1 2p -1 + q (p) ∞ + 1 p j≥0 pq j 1 -pq j q (p) j+1 - q (p) ∞ - p(1 + q)q j q(p) j+1 - 1 p 2 q 1 (pq) ∞ k≥1 [1 -(p) k ]q k 1 -q k + 1 p 2 1 p(pq) ∞ + 1 - 1 p - 1 pq 1 p(pq) ∞ - 1 p - q p + 1 + 1 p (q) 3 q 2 (p) ∞ -q(q -p)(q) 3 -(q -p)(q) 3 - p 2 (q -p)(1 -q 3 ) q .
Although this computation was already quite involved, we could get all cross-moments from (7.3), but only with considerable effort.

Markov Chains and Sojourn times

In this section, we obtain the asymptotic distribution of the number of descents initial values in some interval.

General asymptotic distribution

Let X i , i = 1, . . . , m be an ergodic Markov chain (MC) and A be a subset of states. Assume that the MC is stationary and set x i := [[X i ∈ A]], with M := E(x i ). The number D of times the MC is in A on 1, . . . , m is such that, by standard theory of ergodic Markov chains,

E(D) = mM, V(D) = E m i=1 (x i -M ) 2 + 2 m-1 i=1 m j=i+1 (x i -M )(x j -M ) . If E[(x i -M )(x j -M )] = 0, j ≥ i + 2,
then, setting B := E(x i x i+1 ), we obtain

V(D) = mM (1 -M ) + 2(m -1)(B -M 2 ).
But we have a central limit theorem for MC (again, see Chung,(3)). This gives

D -E(D) V(D) ∼ N (0, 1), m → ∞.

Number of descents values in some interval

Here, the states of the MC are couples Y t Y t+1 with geometric distribution. Also the MC starts with the stationary distribution pq i-1 pq j-1 , hence m = n -1. And the couples Y t Y t+1 , Y u Y u+1 are independent as soon as u > t + 1.

If we are interested in the asymptotic (gaussian) distribution of the number of descents initial values in some interval [τ, τ + ∆], we compute

M = τ +∆ i=τ pq i-1 (1 -q i-1 ), B = τ +∆ i=τ +1 pq i-1 i-1 j=τ pq j-1 (1 -q j-1 ).
Of course, an explicit formula could be written for M resp. B.

Permutations

Starting from n geom(p) RVs, as q → 1, we can derive the asymptotic properties of first and second descents, in a large permutation. We will consider large size (n → ∞) permutations of {1, . . . , n}, or n-permutations for short. It is well known that all rank statistics of an n-permutation can be derived from the corresponding ones of a sequence of n geom(p) RVs as q → 1. But, of course, it is not possible to directly deduce the moments of the beginning (initial height) of the first descent of a n-permutation from the corresponding moments of the geometric variables statistic, as q → 1. However, the asymptotic distribution of this RV can be derived as follows. Let q = 1ε. This gives an asymptotic distribution function for each geom RV K (ε → 0)

1 -q i ∼ F (i) := 1 -e -iε .
Set U = F (K); U is asymptotically distributed as a uniform[0, 1] RV. Let us consider n geom(p) RVs K 1 , . . . , K n . If we scale the corresponding U variables with n (i.e. multiply by n), take the integer part, we have asymptotically a permutation on n, for large n. More precisely the rank of U i is the value of the ith element of the permutation. This gives (asymptoticaly, we consider u as a continuous variable)

u = 1 -e -iε , du = ε(1 -u)di, i = -ln(1 -u)/ε.
Set g(u) := f 1 (i) as given by (8.1). Using n geometric RVs instead of an infinite sequence of ones introduces only an exponentially small error.

For instance, this leads for the initial height of the first descent in a large permutation, using Euler-Maclaurin, to

E(I 1 ) ∼ n 1 0 g(u)u du ε(1 -u) , ε → 0.
We have by simple algebra,

g(u) ∼ ε(1 -u)u + e u u(1 -e -u )ε(1 -u), ε → 0
and the asymptotic density of I 1 /n is given by (we multiply by di = du/(ε(1u)))

h 1 (u) = u[1 + e u (1 -e -u )] = ue u = u ∞ j=0 u j j! .
But this has a clear direct probabilistic interpretation: if U j+1 = u, the probability

P[U 1 ≤ U 2 ≤ • • • ≤ U j ≤ U j+1 ≥ U j+2 ] = u u j j! . (11.1)
Again, as n is large, we can use an infinite summation on j, with exponentially small error terms. Note that

1 0 h 1 (u)du = 1,
as expected, and

E(I 1 ) ∼ n 1 0 h 1 (u)udu = n(e -2) := nE 1,0 , n → ∞,
which conforms to Theorem 9 of (6). All moments can be derived. For instance

E(I 2 1 ) ∼ n 2 1 0 h 1 (u)u 2 du = n 2 (6 -2e) := n 2 E 2,0 , E(I 3 1 ) ∼ n 3 E 3,0 , with E 3,0 = 9e -24.
A general expression can be derived as follows. We have (we drop the second index)

E k = 1 0 h 1 (u)u k du = e -(k + 1)E k-1 , E 0 = 1.
This first order recursion can be solved by iteration:

E k = (k + 1)!(-1) k e k i=1 (-1) i (i + 1)! + 1 . (11.2) By convention, E -1 = 1 0 e u du = e -1.
Note that E k is a linear function of e, that we will write as

E k := D k,0 + D k,1 e.
We could derive similar expressions for J 1 .

The errors terms, as n → ∞ can be derived as follows. The rank and similarly for h 3 (u). This gives eventually The convergence to the stationary distribution h(u) = 2u is very fast. It would be interesting to have a precise rate of convergence, but we have not pursued this approach so far. h(u) can be derived from (7.4), or directly by considering two successive RVs U k . Figure 4 gives h(u), h 1 (u), h 2 (u) The difference h 3 (u)h(u) is given in Figure 5.

R of U j+1 is such that R -(j + 2) is Binomial(n -(j + 2), u), if U j+1
h 3 (u) =

Conclusion

In this paper, we have made a combinatorial and probabilistic study of initial and end heights of first, second, . . . descents in samples of geometrically distributed random variables and in permutations. Several other (similar) models can be analyzed with our tools, let us mention: the weak model and/or ascents with the probabilistic approach, k-descents, size d or more descents, (see (2)), last descents, (see [START_REF] Knopfmacher | The last descent in samples of geometric random variables and permutations[END_REF]), k-ascents with a combinatorial approach (see (2)), etc.

We leave these topics to future work (or to the interested reader), in order to keep the length of the paper within reasonable limits.

1 n 6 - 1 0h 1

 1611 has value u and corresponds to the first descent. Indeed, j values are already below u (on the left) and one on the right. If d values among the n -(j + 2) remaining ones are below u, then U j+1 possesses the rank d + j + 2. So the (conditioned on u, j) moments of R/n are given by the characteristic function F := 1 + u e iθ/n -2e e 2 + 32e/3 -36 -2e 2 -235e/3 + 228 Tab. 1: E k,l Let us denote by h i (u) the asymptotic density of I i /n. For instance, h 2 (u) = (u 1 )h(u, u 1 )du 1 = u[e 1+uue ue u ] = ue u [-1u + e],

1 0h 2

 12 (u 2 )h(u 3 , u 2 )du 2 = ue u [(u + u 2 /2) + e(-u -2) + e 2 ].

• : h 1 Fig. 4 :

 14 Fig. 4: h(u), h1(u), h2(u)

Fig. 5 : 1 0 1 0PP

 511 Fig. 5: h3(u) -h(u)A general expression for h i (u) can be computed as follows: we observe that h i (u) is of the form

Acknowledgements

The insight of two anonymous referees is gratefully acknowledged.

† This material is based upon work supported by the National Research Foundation under grant number 2053748 1365-8050 c 2007

from which we derive E(R/n|j) ∼ u + -u(u -1)(j + 2) n ,

With (11.1), we multiply by u u j j! , and sum on j, this gives

Hence, integrating on u ∈ [0..1], we finally obtain

The first expression fits with Theorem 9 in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF]; the second moment wasn't computed in this paper.

As the first and second descent I 1 , I 2 are not independent, their joint moments are of some interest. They can be asymptotically computed as follows. First, from (7.3), u1,u2) ).

This leads to the Markov kernel

This can also be derived from the uniform[0, 1] random variables properties. The joint moment E(I k 1 I l 2 ) is asymptotically given given by n 2 E k,l , with

The first values of E k,l are given in Table 1.

Appendix

A Some combinatorial identities

We will use intensively Heine's formula:

Several q-combinatorial relations are deduced from Heine.

Heine with t = q, a = 0, b = q, c = pzq, and (A.2).

. This is (6) in [START_REF] Knopfmacher | The first descent in samples of geometric random variables and permutations[END_REF]. (A.5)

. By (A.3). (A.10)

B Identification of (9.1) and (3.6)

We need also this (use(A.1)):

We now plug these two results in:

we established the formula (3.6)

To compute this limit, we use (A.7):

We do two auxiliary calculation (with (A.3)):

and with (A.1):

Therefore

Recalling the expressions for S 1 and S 2 that we just derived, we get

.

Next, we want to compute S 3 := j≥0 p 3 q 3j q(p) j+1 .

We will use Heine with t = pq h , a = 0, c = q, b = q:

From this we derive (set h = -1)

p/q)(q) 3 p 3 q -2 -(1p/q)(1q 3 ) p/q = p 3 q (q) 3 q 3 p 3 1 (p) ∞ -q 2 (qp)(q) 3 p 3 -q(qp)(q) 3 p 3 -(qp)(1q 3 ) p = (q) 3 q 2 (p) ∞ q(qp)(q) 3 -(qp)(q) 3 -p 2 (qp)(1q 3 ) q .

Now we compute (we use S 2 )

S 4 := j≥0 jq 2j (p) j+1 = h≥0 j≥h q 2j (p) j+1 = h≥0 q 2h (p) h+1 j≥0 q 2j (pq h+1 ) j = h≥0 q 2h (p) h+1 -1 pq 2h -


Bill Rosgen

Lorna Stewart

Complexity results on graphs with few cliques

Keywords: graphs, few cliques, Helly property, intersection representation, complexity

A graph class has few cliques if there is a polynomial bound on the number of maximal cliques contained in any member of the class. This restriction is equivalent to the requirement that any graph in the class has a polynomial sized intersection representation that satisfies the Helly property. On any such class of graphs some problems that are NP-complete on general graphs, such as the maximum clique problem and the maximum weighted clique problem, admit polynomial time algorithms. Other problems, such as the vertex clique cover and edge clique cover problems remain NP-complete on these classes. Several classes of graphs which have few cliques are discussed, and the complexity of some partitioning and covering problems are determined for the class of all graphs which have fewer cliques than a given polynomial bound.

Introduction

All graphs we consider are finite, simple, and undirected, and for a graph G = (V, E) we use n = |V | and m = |E| to refer to the number of vertices and edges of the graph. The distance between any two vertices u and v of a graph is the length of a shortest path between them, and is denoted d(u, v). We set d(u, v) = ∞ if there is no path from u to v. A clique in a graph is a subgraph in which every two vertices are adjacent. A clique is maximal if it is not contained in a larger clique. We use K n to denote the graph consisting of a single clique on n vertices and K(G) to denote the set of all maximal cliques in G. For graphs G 1 and G 2 with disjoint vertex sets, we define the graph union of G 1 and G 2 , denoted G 1 ∪ G 2 , as the graph consisting of G 1 and G 2 , without any connecting edges between them. For a graph G, and t ∈ N we define, for t > 1, tG = G ∪ (t -1)G, where 1G = G. For any positive integer t, we refer to the graph tK 2 as O t ; these graphs were called octahedral graphs in [START_REF] Prisner | Graphs with few cliques[END_REF].

Two sets are said to overlap if they intersect, but neither set is contained in the other. An intersection (respectively, overlap) representation of a graph is an assignment of sets to the vertices of the graph such that two vertices are adjacent if and only if the sets assigned to them intersect (respectively, overlap). The size of an intersection or overlap representation is simply the number of elements in the union of all sets in the collection. The size of a minimum intersection or overlap representation for a graph is known as the intersection number or overlap number of the graph, respectively. A family of sets has the Helly property if, for any subfamily that intersects pairwise, there is an element in common to all sets of the subfamily. We refer to an intersection or overlap representation that satisfies this property as a Helly intersection representation or a Helly overlap representation. The Helly intersection (respectively, overlap) number of a graph is the minimum size of a Helly intersection (respectively, overlap) representation.

For complete definitions of the graph classes mentioned here, see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]. An exposition of the concept of NP-completeness, as well as some of the problems and hardness results used later, can be found in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

Moon and Moser, in their 1965 paper [START_REF] Moon | On cliques in graphs[END_REF], show that 3 ⌈n/3⌉ is the maximum number of maximal cliques in a graph on n vertices, and observe that this bound is attained by the graph (n/3)K 3 .

In this paper, we study classes of graphs that have a polynomial bound on the number of maximal cliques. A graph class is said to have few cliques or to be a few-cliques graph class if there is a polynomial p(n) such that any n-vertex graph in the class has no more than p(n) maximal cliques [START_REF] Prisner | Graphs with few cliques[END_REF].

We focus on the complexities of problems on graph classes with few cliques. We are motivated in part by a connection between few-cliques graph classes and intersection and overlap graphs. It has long been known that chordal graphs [START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF], Helly circular-arc (respectively, circle) graphs [START_REF] Gavril | Algorithms on circular-arc graphs[END_REF][START_REF] Durán | Some new results on circle graphs[END_REF], and boxicity 2 graphs (see [START_REF] Spinrad | Efficient Graph Representations[END_REF]) have Helly intersection representations of size polynomial in the number of vertices in the graph. Given a Helly intersection representation of polynomial size for a class of graphs, the maximum weight clique problem can be solved in polynomial time for the intersection class [START_REF] Spinrad | Efficient Graph Representations[END_REF] as well as for the corresponding overlap graph class [START_REF] Čenek | Maximum independent set and maximum clique algorithms for overlap graphs[END_REF]. Thus since, as noted in [START_REF] Spinrad | Efficient Graph Representations[END_REF] and discussed in more detail in Section 2, a polynomial bound on the Helly intersection number turns out to be equivalent to a polynomial bound on the number of maximal cliques in a graph class, the few-cliques classes are interesting within the context of intersection and overlap graphs. An additional motivation for our work is found in the study of relationships among graph parameters and algorithms, where it is interesting to ask which problems become tractable as a result of bounding a particular parameter and which problems remain as computationally difficult as for graphs in general.

Graphs with Few Cliques

By the definition, each of the following graph classes has few cliques: any finite graph class, complete graphs, and triangle-free graphs. In addition, since chordal graphs have at most n maximal cliques [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF], graphs of boxicity k have at most (2n) k maximal cliques [START_REF] Spinrad | Efficient Graph Representations[END_REF], planar graphs have at most 7n/3 -6 maximal cliques [START_REF] Prisner | Graphs with few cliques[END_REF], and K k -free graphs have at most max{n, n∆ k-2 /2 k-2 } maximal cliques, where ∆ is the maximum degree of any vertex in the graph [START_REF] Prisner | Graphs with few cliques[END_REF], all of these graph classes have few cliques.

Balas and Yu [START_REF] Balas | On graphs with polynomially solvable maximum-weight clique problem[END_REF] prove the following bound on the number of maximal cliques a graph can have, in terms of the largest induced subgraph of the form O t .

Theorem 1 (Balas and Yu [START_REF] Balas | On graphs with polynomially solvable maximum-weight clique problem[END_REF]) For any connected graph G = (V, E), where δ is the number of pairs (u, v) ∈ V × V with d(u, v) = 2, and t is the largest integer such that G contains an induced subgraph isomorphic to O t , the number of cliques in the graph is bounded by

2 t ≤ |K(G)| ≤ δ t + 1.
Note that if t is bounded by some constant for a class of graphs, this theorem implies a polynomial bound on the number of maximal cliques in graphs in the class.

Another partial characterization of the graph classes with few cliques is shown by Prisner in [START_REF] Prisner | Graphs with few cliques[END_REF], where he considers classes of graphs having O t as a forbidden induced subgraph, and derives upper bounds on the number of cliques in such graphs. A corollary to these bounds characterizes the hereditary classes of graphs which have few cliques.

Theorem 2 (Prisner [START_REF] Prisner | Graphs with few cliques[END_REF]) A hereditary class of graphs C has few cliques if and only if for some constant t, O t ∈ C.

A further characterization of graph classes with few cliques relies on the following notions related to hypergraphs, from [START_REF] Berge | Graphs and Hypergraphs[END_REF] and [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]. A hypergraph H = (V, E) is a set of vertices V and hyperedges (or edges) E, where each element of E is a nonempty subset of V . The dual of a hypergraph

H = (V, E) is hypergraph H * = (E, {E v : v ∈ V }), where E v is the set of hyperedges in E that contain the vertex v. The 2-section, (H) 2 , of a hypergraph H = (V, E) is the graph G = (V, E)
, where (u, v) ∈ E if and only if there is an edge e ∈ E such that u, v ∈ e. We say that a hypergraph H = (V, E) is Helly when the edge set E satisfies the Helly property. A hypergraph H is conformal if each clique of (H) 2 is contained in an edge of H. Note that the 2-section of the dual of a hypergraph H is the intersection graph of the hyperedges of H. Now, the following theorem can be found in [START_REF] Berge | Graphs and Hypergraphs[END_REF], where it is attributed to Gilmore.

Theorem 3 (see Berge [2, page 396]) A hypergraph is Helly if and only if its dual is conformal.

Let G = (V, E) be a graph and, for each vertex v ∈ V , let S v be the set of all maximal cliques of G that contain v. {S v : v ∈ V } is an intersection representation for G since vertices are adjacent if and only if they appear together in some maximal clique; it satisfies the Helly property since pairwise intersecting sets represent a clique and all vertices of any clique are contained in some maximal clique. Since the size of the representation is |K(G)|, we have that the Helly intersection number of G is at most |K(G)|.

Furthermore, for an arbitrary Helly intersection representation of graph

G = (V, E), consider the hypergraph H = (X, {S v : v ∈ V }) where, for each v ∈ V , S v is the set representing v, and X = ∪ v∈V S v . By Theorem 3, each maximal clique of G = (H * ) 2 is
contained in an edge of H * and, combined with the fact that each edge of H * corresponds to a clique in G, this implies that H * has a unique edge for each maximal clique of G. Therefore, |K(G)| is less than or equal to the Helly intersection number of G.

Thus the next result, which has previously been observed, for example in [START_REF] Spinrad | Efficient Graph Representations[END_REF], is an immediate corollary of Theorem 3.

Corollary 4

For any graph G, the number of maximal cliques in G is equal to the Helly intersection number of G.

Complexity Observations

The problem of recognizing a few-cliques graph class is, given some polynomial bound p(n), does the input graph have no more than p(n) maximal cliques? This problem is solvable in polynomial time by using an algorithm that enumerates all maximal cliques in a graph, such as one of the algorithms of [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] or [START_REF] Johnson | On generating all maximal independent sets[END_REF]. Both of these algorithms have what is referred to in [START_REF] Johnson | On generating all maximal independent sets[END_REF] as the polynomial delay property, that is, the length of time before the first clique is generated and the length of time between the algorithm generating any two successive cliques are each bounded by a polynomial in the size of the graph. Thus, we run the algorithm to enumerate the cliques, and within a polynomial amount of time the algorithm either generates too many cliques, whence we stop the computation and reject, or enumerates all of the cliques in the input graph, at which time the algorithm accepts. Thus, given a graph G and a polynomial p(n), the questions: does G have no more than p(n) maximal cliques? and does G have Helly intersection number at most p(n)? can be answered in polynomial time. Furthermore, for yes instances of the problems, all maximal cliques can be enumerated, as described above, and a minimum Helly intersection representation can be constructed in polynomial time. As discussed in Section 2, a minimum Helly representation can be produced by generating all maximal cliques and then identifying the set of cliques that each vertex is contained in.

Note that polynomial time algorithms for graphs with few cliques can be made robust (that is, when given input not in the class of graphs the algorithm is designed for, the algorithm either rejects or continues computing the correct output [START_REF] Spinrad | Efficient Graph Representations[END_REF]) by generating at most p(n) + 1 cliques and indicating that the input was not in the class of graphs if more than p(n) cliques are found.

In addition, the maximum clique and weighted maximum clique problems are trivially polynomially solvable for few-cliques graph classes. We first apply the algorithm in [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] to find all maximal cliques in time O(nmp(n)). Then, to solve the maximum clique problem we iterate over the list of all maximal cliques, selecting the largest one. A similar algorithm solves the vertex-weighted maximum clique problem, since a maximum weighted clique is some maximal clique with the negative weight vertices removed.

Our NP-completeness results are provided for the class of all graphs containing not more than p(n) maximal cliques, for a given polynomial p(n). Since the graph classes we have observed to have few cliques are contained in the class of graphs with not more than p(n) cliques, for some p(n), NP-completeness results for these classes directly imply the NP-completeness of the same problem on the class of graphs with not more than p(n) cliques.

Spinrad [START_REF] Spinrad | Efficient Graph Representations[END_REF] observed that boxicity-2 graphs have no more than 4n 2 cliques and, therefore, since COLOURABILITY, INDEPENDENT SET, and VERTEX COLOUR are NP-complete [START_REF] Lee | On the 2-dimensional channel assignment problem[END_REF][START_REF] Rim | On rectangle intersection and overlap graphs[END_REF] for boxicity-2 graphs, they are NP-complete for those graphs with no more than 4n 2 maximal cliques.

The NP-completeness of the Hamiltonian cycle and Hamiltonian path problems on planar graphs is shown in [START_REF] Garey | The planar Hamiltonian circuit problem is NPcomplete[END_REF] and the dominating set problem on planar graphs is shown NP-complete in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Thus, by the bound in [START_REF] Prisner | Graphs with few cliques[END_REF] which limits the number of maximal cliques in a planar graph to 7n/3 -6 we know that these problems are NP-complete for the class of graphs with no more than 7n/3 -6 maximal cliques.

Covering and Partitioning Problems

In this section we consider the complexity of covering and partitioning problems under the restriction that the input graph has few cliques. Our results reveal that the hardness of many of these problems lies not only in choosing the cliques in a cover from an exponential collection, but in choosing those cliques that lead to a minimum cover.

In Section 3, we saw that having a polynomial bound on the number of maximal cliques does not help to solve the problem of finding the minimum colouring of a graph; in this section, we consider the problem of colouring a graph with no more than some constant number of colours, k, where k ≥ 3.

Problem. k-COLOURABILITY

Instance: A graph, G = (V, E). Question: Can the vertices of G be coloured with k or fewer colours such that adjacent vertices are assigned distinct colours? Theorem 5 k-COLOURABILITY, for k ≥ 3, is NP-complete on the class of graphs with no more than 7n/3 -6 maximal cliques.

Proof: 3-COLOURABILITY is known to be NP-complete on planar graphs [START_REF] Garey | Some simplified NP-complete problems[END_REF], and thus, by the bound given in [START_REF] Prisner | Graphs with few cliques[END_REF], the problem is also NP-complete for the class of graphs with no more than 7n/3 -6 maximal cliques. However, this result does not extend, on planar graphs, to values of k larger than 3, since it is known that any planar graph can be coloured using only four colours.

We use a simple reduction from the k-colouring problem to the k + 1-colouring problem to form an inductive proof for graphs with no more than 7n/3 -6 maximal cliques. We take a graph G = (V, E), an instance of the k-colourability problem, and create a graph G ′ by adding a single universal vertex. This problem can be shown to be NP-complete, for any k ≥ 3, by a reduction similar to the one used in the proof of Theorem 5. The case k = 3 is done by Garey and Johnson in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], where the exact cover by 3-sets problem is used to show the NP-completeness of 3-CLIQUE PARTITION (which they call the triangle partition problem), but most importantly for our purposes, the reduction they use produces a K 4 free graph. Thus, this result can be immediately extended to 3-CLIQUE PARTITION on graphs with no more than p(n) cliques, for some cubic polynomial p(n), since there are no more than n 3 cliques in a K 4 free graph.

Note that |K(G)| = |K(G ′ )| and that G is k-colourable if and only if G ′ is k + 1-colourable,
Theorem 6 k-CLIQUE PARTITION, for k ≥ 3, is NP-complete for the class of graphs with no more than n k maximal cliques.

Proof: We apply a simple transformation to reach from the case k to the case k + 1. For a graph G = (V, E) on n vertices that is an instance of the k-clique partition problem, we construct the graph G ′ = (V ′ , E ′ ), where we obtain G ′ from G by adding n/k vertices, each connected to every vertex of G.

Notice that a graph cannot be partitioned into disjoint k-cliques unless k divides |V | = n, and so, if this is not the case, we can simply output a trivial no instance, such as the one vertex graph, which cannot be partitioned into k-cliques for any k > 1. If on the other hand, k divides n, we construct V ′ and E ′ as

V ′ = V ∪ {w i : 1 ≤ i ≤ n/k} E ′ = E ∪ {(w i , v) : v ∈ V, 1 ≤ i ≤ n/k}.
This can clearly be done in polynomial time. Notice first that, as long as we do not output the trivial no instance, we know that k + 1 divides

|V ′ | = n + n/k.
We prove that the reduction is correct by induction on k, the base case, for k = 3 is the triangle partition problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. For k ≥ 3, we build a graph G ′ using the transformation given above. If we take a k-clique partition for G, we can extend it to a k + 1 clique partition for G ′ , as we must use n/k cliques of size k to partition G, so we can take one of the new vertices into each k clique to form a k + 1 clique. In the other direction, any k + 1 partition of G ′ must use one of the new vertices in each clique, as no two of the new vertices are adjacent. Since there are exactly n/k new vertices, and there are (n + n/k)/(k + 1) = n/k cliques in any k + 1 clique partition of G ′ , so we will use all of the newly added vertices. Thus, we can simply remove the new vertices from the clique partition to obtain a k-clique partition of G. Thus, by induction on k, this reduction reduces the 3-clique partition problem to the k-clique partition problem for all k ≥ 3. Notice also that at each step of the induction we increase the number of maximal cliques by a factor of n/k. Hence, the number of cliques in the final graph is bounded by n k-3 p(n), if p(n) is a bound on the number of cliques in the instance of the 3-clique partition problem, and since one possible choice for p(n) is n 3 , as the initial instance of the triangle partition problem was K 4 free, the constructed instance of the k-clique partition problem has no more than n k cliques, which is polynomial in n, for fixed k. Thus we have shown the NP-completeness of the k-clique partition problem on the graphs with not more than n k maximal cliques.

✷

We now consider the vertex clique partition problem.

Problem. VERTEX CLIQUE PARTITION

Instance: A graph, G = (V, E), and a natural number k. Question: Can the vertices of graph G can be partitioned into k or fewer cliques?

Note that the vertex clique partition and vertex clique cover problems are equivalent, since any subgraph of a clique is again a clique.

In light of the preceding results, we show that vertex clique partition problem is NP-complete by reducing an n-vertex K 4 free instance G of 3-CLIQUE PARTITION to the instance (G, ⌊n/3⌋) of VERTEX CLIQUE PARTITION. G can be partitioned into at most ⌊n/3⌋ cliques if and only if it can be partitioned into triangles, since the graph is K 4 free. A potential complication arises on an instance where 3 does not divide n, but such an instance cannot be partitioned into triangles, so the reduction can output an arbitrary no instance of the clique partition problem. We conclude that VERTEX CLIQUE PARTITION for the class of graphs with no more than n 3 cliques is NP-complete.

In addition to the NP-completeness of VERTEX CLIQUE COVER, we also have the NP-completeness of EDGE CLIQUE COVER for graphs with a polynomially bounded number of maximal cliques. This result comes directly from a result in [START_REF] Kou | Covering edges by cliques with regard to keyword conflicts and intersection graphs[END_REF], where the vertex clique cover problem is reduced to the edge clique cover problem by taking an instance G of VERTEX CLIQUE COVER, and adding m + 1 vertices to the graph that are adjacent to all the vertices of G, where m is the number of edges in G. If G has no more than p(n) maximal cliques, then the resulting instance of the edge clique cover problem has no more than (m + 1)p(n) maximal cliques. Thus, using this reduction, we have the NP-completeness of the edge clique cover problem, that is, the intersection number problem, for graphs with no more than (m + 1)n 3 maximal cliques.

Finally, we encounter a problem that is solvable in polynomial time on graphs with few cliques. This problem is simply the k-colourability problem in the complement graph.

Problem. VERTEX CLIQUE k-PARTITION

Instance: A graph, G = (V, E). Question: Can the vertices of graph G can be partitioned into k or fewer cliques? Related to this problem are the problems of covering the vertices and edges of a graph with at most k cliques. These problems can once again be obtained from the previous problem by allowing the vertices of the graph to be in multiple cliques in the cover. The essential idea behind a polynomial time algorithm for these problems on a graph G with no more than p(n) maximal cliques is that if we can cover a graph with cliques, we can also cover the graph with the same number of maximal cliques, by simply enlarging each of the cliques to some maximal clique. We can thus consider only collections of k maximal cliques.

For graph G = (V, E), we first compute K(G) = {C 1 , C 2 , . . . , C r } using the algorithm in [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], which runs in O(nmr) time. Then we consider each of the r k sets of k maximal cliques of G. If any of these forms a clique cover, we output yes. If none of these are clique covers of G, we output no. Checking if each set is a clique cover can be performed in O(n 2 ) time, for a total runtime of O(n 2 r k ) = O(n 2 p(n) k ) where p(n) is a polynomial bound on the number of cliques, and so we have a polynomial time algorithm for the clique k-cover problem for graphs with a polynomially bounded number of maximal cliques.

Once again, by the equivalence of VERTEX CLIQUE COVER and VERTEX CLIQUE PARTITION, this algorithm solves the k-partitioning problem as well, and since we can form a minimum edge k-clique cover from maximal cliques by using the same approach, we have a polynomial time algorithm, for any class of graphs with few cliques, for the edge k-clique cover problem. This problem is exactly the problem of determining for a graph G whether there is an intersection representation for G of size at most k, for constant k [START_REF] Kou | Covering edges by cliques with regard to keyword conflicts and intersection graphs[END_REF].

Conclusion

We have seen that the graphs with few cliques are exactly those graphs with polynomially bounded Helly intersection number.

We have also examined several well-known NP-complete graph problems, and shown that the majority of them remain hard when restricted to the graphs with few cliques.

Table 1 lists the complexity results on the problems considered here, for graphs with few cliques. It is interesting to note that the NP-completeness of edge clique cover implies that it remains hard to find a minimum intersection representation even when given a minimum Helly intersection representation.

The problems that admit efficient algorithms on these restricted classes appear to be only those problems where the restriction allows a brute force algorithm to run efficiently. Whether there is a problem that allows this restriction to be used in the construction of a nontrivial efficient algorithm is unknown. Tab. 1: Complexity results on graphs with n vertices, m edges, and no more than p(n) maximal cliques. The NP-completeness results hold for the class of graphs that do not have more maximal cliques than the given bound.

Problem

  since a k-colouring for G together with a new colour for the universal vertex is a k + 1-colouring for G ′ and vice versa. Therefore, by induction on k, for k ≥ 3, this demonstrates the NP-completeness of the k-colourability problem on the class of graphs with not more than 7n/3 -6 maximal cliques, for any constant k ≥ 3.✷We now examine the problem of partitioning the vertices of a graph into disjoint cliques of size k, for some constant k.Problem. k-CLIQUE PARTITIONInstance: A graph, G = (V, E). Question: Can the vertices of the graph G can be partitioned into cliques of size k?

Acknowledgements

This research was partially supported by NSERC and iCORE.