Valeri T Stefanov
email: stefanov@maths.uwa.edu.au

Wojciech Szpankowski

Waiting Time Distributions for Pattern Occurrence in a Constrained Sequence

Keywords: pattern, probability generating function, (d, k)-sequence

A binary sequence of zeros and ones is called a (d, k)-sequence if it does not contain runs of zeros of length either less than d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d < k. Such sequences find an abundance of applications in communications, in particular for magnetic and optical recording. Occasionally, one requires that (d, k)-sequences do not contain a specific pattern w. Therefore, distribution results concerning pattern occurrence in (d, k)-sequences are of interest. In this paper we study the distribution of the waiting time until the r-th occurrence of a pattern w in a random (d, k)-sequence generated by a Markov source. Numerical examples are also provided.

Introduction

In many communication systems, including magnetic and optical recording ones, one must restrict the structure of a bit stream (binary sequence) to a class of sequences satisfying certain constraints. The simplest constrained binary sequences are those in which runs of zeros (between two consecutive 1's) must have length at least d and at most k, where d < k. Such sequences are called (d, k)-sequences (cf. [START_REF] Lothaire | Applied Combinatorics on Words[END_REF][START_REF] Marcus | Constrained systems and coding for recording channels[END_REF][START_REF] Zehavi | On runlength codes[END_REF]). For example, in (1, 4)-sequence 11 and 00000 are forbidden runs. In some situations, as observed in [START_REF] Moision | On codes that avoid specific differences[END_REF], one needs to avoid certain patterns in (d, k)-sequences. In this paper, for a given pattern (word) w (w = w 1 w 2 . . . w m ) we study the exact distribution of the waiting time until the r-th occurrence of the pattern w in a random (d, k)-sequence generated by a Markov source.

Pattern matching is a well studied problem. It is motivated by applications in communication theory as well as computational biology where one looks for over-represented or under-represented patterns in order to find useful signals. In general, for a given set of patterns W = {W 1 , . . . , W K }, where the W i are words of the same length, one searches for all W occurrences in a text of length n. (In this paper we only consider a single pattern of length m that we denote by w.) In computer science literature several fast algorithms (e.g., Knuth-Morris-Pratt and Boyer-Moore algorithms) were designed to search for such patterns. Here, we are rather interested in the distribution theory associated with the number of W occurrences in a probabilistic framework where the (constrained) text is generated randomly (a Markov source in our case).

The pattern matching problem (in a probabilistic framework) goes back, at least, to Feller. The number of word occurrences in a random text has been intensively studied over the last two decades, with significant progress in this area being reported [START_REF] Bender | The distribution of subword counts is usually normal[END_REF][START_REF] Biggins | Markov renewal processes, counters and repeated sequences in Markov chains[END_REF][START_REF] Blom | How many random digits are required until given sequences are obtained?[END_REF][START_REF] Chadjiconstantinidis | Joint distributions of successes, failures and patterns in enumeration problems[END_REF][START_REF] Chryssaphinou | The occurrence of a sequence of patterns in repeated dependent experiments[END_REF][START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF][START_REF] Fu | On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials[END_REF][START_REF] Gerber | The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain[END_REF][START_REF] Guibas | Periods in strings[END_REF][START_REF] Li | A martingale approach to the study of occurrence of sequence patterns in repeated experiments[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF][START_REF] Nicodème | Motif Statistics[END_REF][START_REF] Reinert | Probabilistic and statistical properties of words: an overview[END_REF][START_REF] Robin | Exact distribution of word occurrences in a random sequence of letters[END_REF][START_REF] Robin | Exact distribution of the distances between any occurences of a set of words[END_REF][START_REF] Stefanov | On some waiting time problems[END_REF][START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF][START_REF] Stefanov | Explicit distributional results in pattern formation[END_REF][START_REF] Waterman | Introduction to Computational Biology[END_REF]. For instance, Guibas and Odlyzko [START_REF] Guibas | Periods in strings[END_REF] revealed the fundamental role played by autocorrelation sets and their associated polynomials. Li [START_REF] Li | A martingale approach to the study of occurrence of sequence patterns in repeated experiments[END_REF] and Gerber and Li [START_REF] Gerber | The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain[END_REF] introduced martingale techniques to the area and combined the latter with a relevant Markov chain embedding. Markov chain embeddings have been widely used by a number of authors (see [START_REF] Chadjiconstantinidis | Joint distributions of successes, failures and patterns in enumeration problems[END_REF][START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF][START_REF] Fu | On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials[END_REF] and the references in [START_REF] Balakrishnan | Runs and Scans with Applications[END_REF][START_REF] Fu | Distribution Theory of Runs and Patterns and its Applications[END_REF]). Blom and Thorburn [START_REF] Blom | How many random digits are required until given sequences are obtained?[END_REF] made connections with Markov renewal theory and Biggins and Cannings [START_REF] Biggins | Markov renewal processes, counters and repeated sequences in Markov chains[END_REF] elaborated on these. Stefanov and Pakes [START_REF] Stefanov | Explicit distributional results in pattern formation[END_REF] introduced exponential family methodology to the area and Stefanov [START_REF] Stefanov | On some waiting time problems[END_REF] extended it in combination with suitable Markov renewal embeddings. Régnier and Szpankowski [START_REF] Régnier | On the Approximate Pattern Occurrences in a Text[END_REF][START_REF] Régnier | On pattern frequency occurrences in a Markovian sequence[END_REF] established that the number of occurrences of a word is asymptotically normal under a diversity of models that include Markov chains. Nicodème, Salvy, and Flajolet [START_REF] Nicodème | Motif Statistics[END_REF] showed generally that the number of places in a random text at which a 'motif' (i.e., a general regular expression pattern) terminates is asymptotically normally distributed. Bender and Kochman [START_REF] Bender | The distribution of subword counts is usually normal[END_REF] studied a generalized pattern W occurrences using (in nutshell) the deBruijn graph representation that allowed the authors to establish the central limit theorem, but without explicit mean and variance. Recent surveys on pattern matching can be found in Lothaire [START_REF] Lothaire | Applied Combinatorics on Words[END_REF] (Chaps. 6 and 7). To the best of our knowledge, the distribution theory associated with pattern occurrence in a constrained sequence, such as a (d, k)-sequence, has not been treated in the literature.

A brief description of our problem and methodology follows. Let N n be the number of w (w = w 1 . . . w m ) occurrences in a binary sequence, of length n, generated by a two-state Markov chain X. Throughout the paper such sequences will be called unconstrained sequences whereas (d, k)-sequences will be called constrained sequences. By Y r we define the waiting time until the r-th occurrence of the pattern w in an unconstrained sequence. Bearing in mind that the initial symbol at time zero counts to the sequence length we have

P (N n ≥ r) = P (Y r ≤ n -1) (1)
for all r, n ≥ 1. This basic renewal equation is the starting point of two different approaches to the analysis of pattern occurrences, on finite alphabets, in unconstrained sequences as surveyed in Chaps. 6 and 7 of [START_REF] Lothaire | Applied Combinatorics on Words[END_REF]. For example, [START_REF] Bender | The distribution of subword counts is usually normal[END_REF][START_REF] Guibas | Periods in strings[END_REF][START_REF] Nicodème | Motif Statistics[END_REF][START_REF] Régnier | On the Approximate Pattern Occurrences in a Text[END_REF][START_REF] Régnier | On pattern frequency occurrences in a Markovian sequence[END_REF] analyze N n , whereas the authors of [START_REF] Reinert | Probabilistic and statistical properties of words: an overview[END_REF][START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF][START_REF] Waterman | Introduction to Computational Biology[END_REF] study the waiting time Y r , for unconstrained sequences. In the case of constrained sequences we may be interested in either the distribution of N n given the sequence is constrained up to time n, or the distribution of Y r given the sequence is constrained up to time Y r . In other words, denoting by

N (d,k) n
the number of runs of zero of length either less than d or greater than k in an unconstrained sequence of length n, the probabilities of interests are

P (N n ≥ r| N (d,k) n = 0) (= P (Y r ≤ n -1| N (d,k) n = 0)) and P (Y r ≤ n -1| N (d,k) Yr = 0) (= P (N n ≥ r| N (d,k) Yr = 0)). Clearly P (N n ≥ r| N (d,k) n = 0) is not equal to P (Y r ≤ n -1| N (d,k) Yr = 0
). Also the evaluation of each of these two conditional probabilities lead to two different problems. For the latter probability we also have

P (Y r ≤ n -1| N (d,k) Yr = 0) = n-1 i=0 P (Y r = i, N (d,k) i = 0) ∞ i=0 P (Y r = i, N (d,k) i = 0) .
In the present paper we deal with P (Y r ≤ n -1| N (d,k) Yr = 0), whereas in a forthcoming paper we will

treat P (N n ≥ r| N (d,k) n = 0).
Of course, the latter probability is of relevance in situations when the constrained sequence has been observed up to time n whereas the former is such when the constrained sequence is observed up to an r-th occurrence of the pattern of interest.

Stefanov [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] provides an original approach for a recursive evaluation of the generating functions of the waiting time conditioned on seeing a portion of the pattern in an unconstrained sequence. Also the approach provides the joint generating functions of the aforementioned waiting time Y r together with the associated counts of relevant events. This paper extends the analysis of [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] to constrained sequences. The case of constrained sequences, when the probability of interest is

P (Y r ≤ n -1| N (d,k)

Yr

= 0), leads to more general type of events, associated with the above waiting time, than those considered in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF]. The key points of that extension are explained in Idea of the Proof inserted immediately after Theorem 1 in the next section.

The paper is organized as follows. In the next section we present our main theoretical results. These provide recursive formulae for computing the joint generating function of the waiting time until seeing the r-th occurrence of a pattern and the associated count of runs of zero of length either less than d or greater than k (the so called forbidden patterns). In the last section we provide numerical examples.

Main Results

We assume that the binary sequences are generated by a a two-state Markov chain X, (X(n), n = 0, 1, . . .). Its transition probabilities are denoted by

P (X(k) = j|X(k -1) = i) = p i,j , i, j = 0, 1.

Recall that N (d,k)

n counts the number of the so called forbidden patterns up to time n. Denote by

G Y (s) r (z 1 , z 2 ) = E[z Y (s) r 1 z N (d,k) Y (s) r 2 ]
the joint generating function of the waiting time, Y r , until seeing the r-th occurrence of the pattern w = w 1 w 2 . . . w m , given the initial symbol of the sequence is s, and the associated count,

N (d,k) Y (s) r
, of occurrences of runs of zeros of length either less than d or greater than k up to that waiting time.

Note that if G Z1,Z2 (z 1 , z 2 ) is the joint generating function of two nonnegative integer random variables, then for the generating function G Z1|Z2=0 (z) of the conditional distribution of Z 1 , given Z 2 = 0, we have

G Z1|Z2=0 (z) = ∞ n=0 z n P (Z 1 = n, Z 2 = 0) P (Z 2 = 0) = G Z1,Z2 (z, 0) G Z1,Z2 (
Y (s) r = 0, is equal to that of Y (s) 1 + i≥2 Y i
and of course its generating function equals G Y (s)

1 (z)(G Y2 (z)) r-1
, where

G Y (s) 1 (z) = G (s) m (z, 0) G (s) m (1, 0) G Y2 (z) = G (intersite) m (z, 0) G (intersite) m (1, 0)
and by G (z 1 , z 2 ) we denoted the joint generating function of the intersite distance between two consecutive occurrences of the pattern w and the associated count of occurrences of the forbidden patterns.

The remaining part of the paper is devoted to a method for an explicit derivation of the joint generating functions G (s) m (z 1 , z 2 ) and G (intersite) m (z 1 , z 2 ). Recall that these generating functions are associated with unconstrained sequences.

Let ν i,j be the transition time from state i to state j in the two-state Markov chain X introduced earlier, that is, ν i,j = inf{n : X(n) = j|X(0) = i}, ; i, j = 0, 1, and let I νi,j be the associated indicator function of the event "a run of zeros of length either less than d or greater than k has occurred during the transition time ν i,j ." It is assumed that ν i,i = 0.

Introduce the functions g i,j (z 1 , z 2 ) for i, j = 0, 1, as follows: Let

g i,j (z 1 , z 2 ) = E[z νi,j 1 z Iν i,j 2
], (i, j) = (1, 0)

be the joint generating function of (ν i,j , I νi,j ), if i, j = 0, 1 and (i, j) = (1, 0). Of course

g 0,0 (z 1 , z 2 ) = g 1,1 (z 1 , z 2 ) = 1,
because ν 0,0 = ν 1,1 = 0, and subsequently I ν0,0 = I ν1,1 = 0. We define g 1,0 (z 1 , z 2 ) to be the generating function G ν1,0 (z 1 ) of ν 1,0 , that is,

g 1,0 (z 1 , z 2 ) = G ν1,0 (z 1 ) = z 1 p 1,0 1 -p 1,1 z 1 . (2)
The second identity comes from noticing that ν 1,0 is a geometrically distributed random variable with probability of success p 1,0 and support {1, 2, . . .}. In other words, the meaning of g 1,0 (z 1 , z 2 ) is the same as that for the other g i,j (z 1 , z 2 ) with the convention that I ν1,0 = 0. The reasons for defining g 1,0 (z 1 , z 2 ) as if ignoring a possible occurrence of the event of interest within the passage time ν 1,0 , will become clear in the proof of Theorem 1 below. Another generating function of relevance is the joint generating function of (ν 0,1 , I ν0,1 ), given that exactly r zeros are preceding the starting state zero; it is assumed that these zeros are allowed to be counted towards the formation of the event marked by the indicator function I ν0,1 . Denote this joint generating function by g r-0,1 (z 1 , z 2 ). Clearly, g r-0,1 (z 1 , z 2 ) equals the joint generating function of ν 0,1 and the indicator function of the event "a run of zeros of length either less than d -r or greater than k -r has occurred within that transition time".

Lemma 1

The following explicit expressions hold for the joint generating functions g 0,1 (z 1 , z 2 ) and g r-0,1 (z 1 , z 2 ) :

g 0,1 (z 1 , z 2 ) = p 0,1 z 1   z 2 1 -p 0,0 z 1 + (1 -z 2 ) k i=max(1,d) (p 0,0 z 1 ) i-1   (3) g r-0,1 (z 1 , z 2 ) = p 0,1 z 1   z 2 1 -p 0,0 z 1 + (1 -z 2 ) max(0,k-r) i=max(1,d-r) (p 0,0 z 1 ) i-1   (4)
where max(i, j) is the maximal of the two integers i and j, and the convention 0 i=1 = 0 applies. Proof: Denote by p i = P (ν 0,1 = i) and note that p i = p 0,1 p i-1 0,0 because ν 0,1 is geometrically distributed with probability of success p 0,1 and support {1, 2, . . .}. Also note that I ν0,1 = 0 if and only if d ≤ ν 0,1 ≤ k. Thus, for the joint generating function g 0,1 (z 1 , z 2 ) we get

g 0,1 (z 1 , z 2 ) = d-1 i=1 z 2 z i 1 p i + k i=d z i 1 p i + ∞ i=k+1 z 2 z i 1 p i = d-1 i=1 z 2 z i 1 p 0,1 p i-1 0,0 + k i=d z i 1 p 0,1 p i-1 0,0 + ∞ i=k+1 z 2 z i 1 p 0,1 p i-1 0,0 .
Simplifying the above expression leads to (3) above. Similar arguments apply for the derivation of the expression for g r-0,1 (z 1 , z 2 ) and the details are therefore omitted. The proof of Lemma 1 is complete. ✷

We will derive simple recurrence relations leading to an exact evaluation of the joint generating function

G (s) m (z 1 , z 2 ) and G (intersite) m (z 1 , z 2 )
, which have been introduced above. For the pattern of interest w = w 1 w 2 . . . w m , denote

I(s 1 , s 2 , . . . , s r ) = 1 if (s 1 , s 2 , . . . , s r ) = (w 1 , w 2 , . . . , w r ) 0 otherwise, I(s 1 , s 2 , . . . , s r ) = 1 -I(s 1 , s 2 , . . . , s r ), r = 1, 2, . . . , m, (5)
that is, I(s 1 , s 2 , . . . , s r ) = I w1 (s 1 )I w2 (s 2 ) . . . I wr (s r ), where I (•) (•) is an indicator function. For the sake of brevity we introduce the following notation. For each j, j = 2, 3, . . . , m -1, and each a, a = 0, 1, let

L 1 (1, a) = 1 L 1 (j,
where it is assumed that I(w i , w i+1 , . . . , w j , a) = 1 if i > j. Note that L r (j, a) = 1 for r < j if and only if none of w i w i+1 . . . w j a for i = 2, 3, . . . r, is a prefix to w 1 w 2 . . . w m , whereas w r+1 w r+2 . . . w j a is such. Also, L j (j, a) is equal to one if and only if none of w i w i+1 . . . w j a for i = 2, 3, . . . j, is a prefix to w 1 w 2 . . . w m . In other words, the L i (j, a) are relevant indicator functions related to the self-overlapping structure of the pattern w = w 1 w 2 . . . w m . In passing we observe that our definition of L r (j, a) is related to the autocorrelation set and polynomial of Guibas and Odlyzko [START_REF] Guibas | Periods in strings[END_REF] (cf. also [START_REF] Lothaire | Applied Combinatorics on Words[END_REF][START_REF] Régnier | On pattern frequency occurrences in a Markovian sequence[END_REF]).

Let now Y (s)

1 (w j 1 ) be the waiting time to see the pattern w j 1 = w 1 w 2 . . . w j , given the initial state is s. Then we define by

G (s) j (z 1 , z 2 ) = E[z Y (s) 1 (w j 1 ) 1 z N (d,k) Y 1 (w j 1 ) 2 ]
the joint generating function of Y (s)

1 (w j 1 ) and the associated count,

N (d,k) Y1(w j 1 )
, of forbidden patterns (runs of zeros of length either less than d or greater than k). Here we allow the first symbol, that is, s, to contribute to the pattern (of course this matters if s = w 1 ). Recall that for j = m the joint generating function

G (s) m (z 1 , z 2 ) has been introduced earlier. Let G (r-0) j (z 1 , z 2 )
be the joint generating function of the same quantities as above, given the initial state (assumed to be zero) is preceded by exactly r zeros and the latter zeros are allowed to count towards the formation of the relevant event concerning the forbidden patterns (in other words the length of the first zero run within the waiting time Y (0) 1 (w j 1 ) is increased by r); also the initial state zero is allowed to contribute to the pattern. Further, let G (w1w2...w h ) j (z 1 , z 2 ) be the joint generating function of the same quantities as above, given the sub-pattern w 1 w 2 . . . w h (h ≤ j) has been reached.

Throughout the article it is assumed that the pattern of interest w = w 1 w 2 . . . w m does not contain forbidden patterns. Each pattern of zeros and ones can be viewed as a sequence of alternating blocks of ones and zeros where the length of the i-th block is denoted by k i and k i > 0 for i = 2, 3, . . . and k 1 > 0 if the initial symbol of the pattern is one whereas k 1 = 0 if the initial symbol is zero. For example, for the pattern 11100001100000 we have k 1 = 3, k 2 = 4, k 3 = 2, k 4 = 5, and for the pattern 001111100011 we have

k 1 = 0, k 2 = 2, k 3 = 5, k 4 = 3, k 5 = 2.
Denote by J 1 and J 2 the following subsets of {1, 2, . . . , m}, which are associated with the pattern w = w 1 w 2 . . . w m :

J 1 = b n=1 {j : n i=1 k 2i-1 + 1 ≤ j ≤ n i=1 k 2i-1 + d -1}, J 2 = b n=1 {j : j = n i=1 k 2i },
where b is the number of zero blocks of the pattern w. For example, if the pattern of interest is 001111100011 and d = 2, k = 5 we get J 2 = {2, 10}, and

J 1 = {1, 8}. Note that G ( * ) 1 (z 1 , z 2 ) = g * ,w1 (z 1 , z 2 ), (7)
where * stands for either 0 or 1, or r -0. Actually, G ( * )

1 (z 1 , z 2 ) has the same meaning as that of g * ,w1 (z 1 , z 2 ) unless w 1 = 0 and * = 1 (recall our definition of g 1,0 given in (2) above). For the latter case we formally assume that (7) holds and the reason for that assumption will become clear in the Idea of Proof of Theorem 1 below. Closed explicit expressions for g i,j (z 1 , z 2 ) and g r-0,1 (z 1 , z 2 ) are found in Lemma 1 and prior to its statement. The formal proof is presented in the next section.

Theorem 1

The following recurrence relations hold for the joint generating functions

G (•) j (z 1 , z 2 ) : (i) For j / ∈ (J 1 ∪ J 2 )
, and h = 1, 2, . . . , j, and r = 1, 2, . . . , we have

G (s) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (s) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 A j , (8)
G (w1w2...w h ) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (w1w2...w h ) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 A j , (9)
G (r-0) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (r-0) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 A j , (10)
where

A j = j-1 i=1 L i (j, 1 -w j+1 )G (w1,w2,...,wj-i+1) j (z 1 , z 2 ) + L j (j, 1 -w j+1 )G (1-wj+1) j (z 1 , z 2 ), (11)
with the convention 0 i=1 = 0, and the L i (j, a) have been introduced in ( 6). (ii) For j ∈ J 1 , and h = 1, 2, . . . , j, and r = 1, 2, . . . , we have

G (s) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (s) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 z 2 A j , (12)
G (w1w2...w h ) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (w1w2...w h ) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 z 2 A j , (13)
G (r-0) j+1 (z 1 , z 2 ) = p wj ,wj+1 z 1 G (r-0) j (z 1 , z 2 ) 1 -p wj ,1-wj+1 z 1 z 2 A j , (14)
where A j is as above.

(iii) For j ∈ J 2 , and h = 1, 2, . . . , j, and r = 1, 2, . . . , the same relations as those for j / ∈ (J 1 ∪ J 2 ) above hold after replacing A j by B j , where

B j = j-1 i=1 L i (j, 1 -w j+1 )G (w1,w2,...,wj-i+1) j (z 1 , z 2 ) + L j (j, 1 -w j+1 )G (k2n-0) j (z 1 , z 2 ), ( 15
)
and n is associated with

j through j = n i=1 k 2i . Recall that j ∈ J 2 if and only if j = k 1 + k 2 + . . . + k 2n for some n, n = 1, 2, . . . .

Idea of the Proof:

The proof is based on a suitable extension of the methodology introduced in Stefanov [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF]. The latter treated patterns formed on finite alphabets in strings generated by general discreteand continuous-time models. In particular, Theorem 4.1 (cf. [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] p. 890) provides recurrence relations leading to exact evaluation of the joint generating function of the waiting time until reaching a pattern together with the associated counts of occurrences of the corresponding symbols of the alphabet. In this paper we deal with a simpler model (binary alphabet and discrete-time parameter) but the joint generating function of interest is that of the waiting time until reaching a pattern together with the associated count of occurrences of an event which is not as simple as the events considered in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF]. A careful scrutiny of [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] proofs reveals that the recurrence relations provided there are applicable to the joint generating function of the waiting time till reaching a pattern together with the associated count of occurrences of an 'event' if the following two conditions are satisfied concerning that 'event':

(i) the joint generating functions for the following quantities are available: the waiting time to reach a letter from another (or the same) letter of the alphabet together with the associated count of occurrences of the 'event' of interest.

(ii) All occurrences of the 'event' of interest are captured within the passage times between the states, that is, occurrence or non occurrence of the 'event' does not depend on the history prior to a passage time or the future after that passage time.

Note that nominating the event of interest to be a run of zeros of length either less than d or greater than k we get that condition (ii) is not satisfied in general. For example, in a passage time from state zero to state one the occurrence or non occurrence of our event of interest (a constrained zero-run) depends on the number of zeros just preceding the starting state zero. As for a passage time from state one to state zero, note that, on one hand, the occurrence or non occurrence of the event of interest is not affected by the outcomes preceding the initial state one. On the other hand, within that passage time a run of zeros of length 1 occurs (the last observation within such passage time is zero which is preceded by one), that is, the event of interest occurs if d > 1 and given we stop observing the generated random sequence with such passage time. If we do not stop observing the generated sequence at such passage time then the occurrence or non occurrence of the event of interest depends on the future outcomes (that is, on how many zeros will follow after the first zero achieved from sate one). Note that we stop observing the generated random sequences at occurrences of the pattern of interest, which we assume does not contain constrained zero-runs. That is, we do not stop observing the generated random sequence at a passage time from state one to state zero if d > 1. Therefore, within a passage time from state one to state zero we should not account for a possible occurrence of the event of interest, because such occurrence will be accounted for within the following passage time from state zero to state one. This is the reason for defining g 1,0 (z 1 , z 2 ) to be equal to the generating function of ν 1,0 , as if assuming that within a passage time from state one to state zero a constrained zero-run does not occur. By the same reason we assumed that G

(1) 1 (z 1 , z 2 ) = g 1,w1 (z 1 , z 2 ) if w 1 = 0 (cf. the comment prior to Theorem 1). In particular, we may assume that condition (i) above is satisfied for our problem because the relevant joint generating functions are provided in Lemma 1 and prior to it.

Further we show how the methodology in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] can be extended to derive relevant recurrence relations for the case of the waiting time until reaching a pattern and the associated count of occurrences of constrained zero-runs.

Recall that we consider a pattern w = w 1 w 2 . . . w m whose consecutive blocks of ones and zeros are of lengths k 1 , k 2 , k 3 , . . . , respectively.

Assume first the pattern of interest consists of the first k 1 + 1 symbols of w. Note that in this case condition (ii) is satisfied because there are no zeros preceding an initial zero state at a passage time from state zero to state one. Therefore, the relations given by ( 8), ( 9), [START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF] for j, such that 1 ≤ j ≤ k 1 are a special case of the recurrence relations in Theorem 4.1 of [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF]. Since the model treated in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] is more general and the uninitiated reader may find it not quite transparent how to write the relations for our special model here we provide the following hint. Delete the entries of t wj+1 and t n , and replace φ wj ,wj+1 (z 0 ) by z 1 in the corresponding recurrence relations in Theorem 4.1 of [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] to get the relations ( 8), ( 9), [START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF].

Assume now that the pattern of interest consists of the first k 1 + 2 (< k 1 + k 2 ) symbols. Then note that from the time epoch at which we have reached the subpattern w 1 w 2 . . . w k1+1 till reaching the pattern w 1 w 2 . . . w k1+2 one may miss counts of the event of interest (a run of zeros of length less than d) due to the following observation. Upon reaching w 1 w 2 . . . w k1+1 assume that in the next step the pattern w 1 w 2 . . . w k1+2 is not reached (that is, a mismatch occur at this stage). Thus, a run of zeros of length 1 (< d, of course given d > 1) has occurred and it will not be accounted for by the recurrence relations provided in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF]. To account for such occurrences one should multiply by z 2 the relevant joint generating functions each time such mismatch occurs. It is achieved by replacing the denominator 1 -p wj ,1-wj+1 z 1 A j by 1-p wj ,1-wj+1 z 1 z 2 A j in the recurrence relations. Therefore, relations ( 12), ( 13), ( 14) hold for j = k 1 +1.

Similarly, if the pattern consists of the first k 1 + 3 (< k 1 + k 2 ) symbols then upon reaching the subpattern w 1 w 2 . . . w k+2 on the following step one may miss a count of the event of interest. More specifically, this is a run of zeros of length 2 (< d, of course given d > 2). To account for such occurrences of the event of interest again the denominator 1-p wj ,1-wj+1 z 1 A j is to be replaced by 1-p wj ,1-wj+1 z 1 z 2 A j . Clearly, the same argument applies if the pattern consists of the first k 1 + j -1 (< k 1 + k 2 ) symbols of w, where j ≤ d. Therefore, the recurrence relations ( 12), ( 13), ( 14) hold for j such that k 1 + 1 ≤ j ≤ k 1 + d -1 (these j's belong to J 1 ). Further, note that for larger j, such that k 1 + d ≤ j ≤ k 1 + k 2 -1 (note that such j's do not belong to J 1 ∪ J 2 ) the recurrence relations given by ( 8), ( 9), [START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF] hold, because in mismatch situations constrained zero-runs do not occur.

Assume now that the pattern consists of the first k 1 +k 2 +1 symbols of w. Then note that in a mismatch situation at the next step after reaching the sub-pattern consisting of the first k 1 + k 2 symbols, we are at state zero with exactly k 2 zeros preceding it. The method in [START_REF] Stefanov | The intersite distances between pattern occurrences in strings generated by general discrete-and continuous-time models: an algorithmic approach[END_REF] implies that G (1-wj+1) j (z 1 , z 2 ) (this is the generating function, in the expression for A j , which accounts for the evolution of the sequence after such a mismatch situation, and given no overlap occurred after that mismatch) from the expression for A j , given in [START_REF] Fu | On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials[END_REF], is to be substituted by G (k2-0) j (z 1 , z 2 ) in order to account for all occurrences of the event of interest. That is, for j = k 1 + k 2 , the relations (8), ( 9), [START_REF] Fu | Distribution theory of runs and patterns associated with a sequence of multistate trials[END_REF]

hold with G (1-wj+1) j (z 1 , z 2 ) replaced by G (k2-0) j (z 1 , z 2 )
in the expressions for the A j ; that is, A j is replaced by B j . For larger j (j > k 1 + k 2 ) similar arguments to those above apply.

Proof of Theorem 1

First, recall that the g.f., G(z), of the geometric distribution on {0, 1, . . .}, with probability of 'success' p, is given by p/(1 -qz), where q = 1 -p. Also recall that for the g.f. of the random sum

Y = ν i=1 Y i we have G Y (z) = G ν (G Yi (z)), (16)
where z = (z 1 , z 2 , . . . , z n ) and the Y i are independent and identically distributed (i.i.d.) random vectors with g.f. G Yi (z) and ν is a non-negative r.v., independent of the Y i , with g.f. G ν (z). If the distribution of ν is geometric then the random sum Y is called a geometric sum.

The following quantity is called briefly the first return time to the pattern w 1 w 2 . . . w j :

inf{n ≥ 1 :

X(n + 1) . . . X(n + 1 + j) = w 1 . . . w j |X(1) . . . X(j) = w 1 . . . w j }.
Recall that the pattern of interest is denoted by w = w 1 w 2 . . . w m . Note that j / ∈ J 1 ∪ J 2 if and only if either w j+1 = 1, or w j w j+1 = 10, or w j+1 = 0 and the number of zeros preceding w j+1 , in the block of zeros to which w j+1 belongs, is less than d (recall that d pertains to the term (d,k)-sequence).

We will prove the validity of ( 8), ( 9) and ( 10) first for j = 1, 2, . . . , k 1 . Recall that k 1 is the length of the first block of ones of the pattern of interest w. Of course these j's do not belong to the set (J 1 ∪ J 2 ). Now consider the subpattern w 1 w 2 consisting of the first two symbols of the pattern w, of course assuming that k 1 ≥ 1. Note that the joint generating function of the first return time to state w 1 and the associated count of the forbidden patterns within that return time, conditional on not entering state w 2 at the first step, is

H 1 (z 1 , z 2 ) = p w1,1-w2 z 1 g 1-w2,w1 (z 1 , z 2 ) 1 -pw 1 , w 2 . (17)
Actually, ( 17) is derived via conditioning on the first step. It is easy to see, using the strong Markov property and applied to the consecutive entry times to state w 1 , that the joint distribution of the waiting time to reach the pattern w 1 w 2 from state s and the associated count of forbidden patterns up to that waiting time, is the same as the joint distribution of

K 1 + e 1 + ν1 i=0 Y i,1
where e 1 is the unit vector (1, 0), the Y i,1 are i.i.d. (two-dimensional) random vectors, also independent of K 1 , and ν 1 is a geometric random variable, independent of the Y i,1 and K 1 with a probability of 'success' p w1,w2 . Further, the (two-dimensional) random vector K 1 has the same joint distribution as that of the waiting time to reach w 1 from state s, and the associated count of forbidden patterns, that is, its joint g.f. G K1 (z 1 , z 2 ) is equal to g s,w1 (z 1 , z 2 ). The random vector Y i,1 has a joint generating function given by H 1 (z 1 , z 2 ). Thus, in view of ( 16) and ( 17) and recalling that G

(s) 1 (z 1 , z 2 ) = g s,w1 (z 1 , z 2 ) we get that G (s) 2 (z 1 , z 2 ) = g s,w1 (z 1 , z 2 ) p w1,w2 z 1 1 -(1 -p w1,w2 )H 1 (z 1 , z 2 ) = p w1,w2 z 1 G (s) 1 (z 1 , z 2 ) 1 -p w1,1-w2 z 1 G (1-w2) 1 (z 1 , z 2 )
.

Using the same arguments as those above we get that for r = 1, 2, . . .

G (w1) 2 (z 1 , z 2 ) = p w1,w2 z 1 G (w1) 1 (z 1 , z 2 ) 1 -p w1,1-w2 z 1 G (1-w2) 1 (z 1 , z 2 ) , G r-0) 2 (z 1 , z 2 ) = p w1,w2 z 1 G r-0) 1 (z 1 , z 2 ) 1 -p w1,1-w2 z 1 G (1-w2) 1 (z 1 , z 2 ) .
That is, noting that 11)), we get that ( 8), ( 9) and ( 10) hold for j = 1. Now consider the subpattern w 1 w 2 w 3 assuming that k 1 ≥ 2 (that is j = 2). Similarly to the preceding case (when j = 1), conditioning on the first step, note that the joint generating function of the first return time to the subpattern w 1 w 2 and the associated count of the forbidden patterns within that return time, conditional on not entering state w 3 at the first step, is given by

A 1 = G (1-w2) 1 (z 1 , z 2 ) (cf. (
H 2 (z 1 , z 2 ) = p w2,1-w3 z 1 L 1 (2, 1 -w 3 ) + L 2 (2, 1 -w 3 )G (1-w3) 2 (z 1 , z 2 ) 1 -p w2,w3 , (18)
where the L i (j, a) have been introduced in (6). Again using the strong Markov property and applied to the consecutive entry times to the subpattern w 1 w 2 , we get that the joint distribution of the waiting time to reach the subpattern w 1 w 2 w 3 from state s and the associated count of forbidden patterns up to that waiting time, is the same as the joint distribution of

K 2 + e 1 + ν2 i=0 Y i,2
where e 1 is the unit vector (1, 0), the Y i,2 are i.i.d. random vectors, also independent of K 2 , and ν 2 is a geometric random variable, independent of the Y i,2 and K 2 with a probability of 'success' p w2,w3 . Further, the random vector K 2 has the same joint distribution as that of the waiting time to reach w 1 w 2 from state s, and the associated count of forbidden patterns, that is, its joint g.f. G K2 (z 1 , z 2 ) is equal to G (s) 2 (z 1 , z 2 ). The random vector Y i,2 has a joint generating function given by H 2 (z 1 , z 2 ). Therefore, similarly to the preceding case, and using [START_REF] Lothaire | Applied Combinatorics on Words[END_REF] we get that

G (s) 3 (z 1 , z 2 ) = p w2,w3 z 1 G (s) 2 (z 1 , z 2 ) 1 -(1 -p w2,w3 )H 2 (z 1 , z 2 ) = p w2,w3 z 1 G (s) 2 (z 1 , z 2 ) 1 -p w2,1-w3 z 1 L 1 (2, 1 -w 3 ) + L 2 (2, 1 -w 3 )G (1-w3) 2 (t) .
That is, (8) holds for j = 2. Likewise, ( 9) and ( 10) hold for j = 2. The same arguments, as those used in the cases for j = 1, 2 apply to any j such that 1 ≤ j ≤ k 1 . Therefore ( 8), ( 9) and ( 10) hold for j = 1, 2, . . . k 1 .

Now consider the case when j ∈ J 1 . First, we will consider the j's belonging to {j :

1 i=1 k 2i-1 + 1 ≤ j ≤ 1 i=1 k 2i-1 +d-1}, that is, for j = k 1 +1, k 1 +2, . . . , k 1 +d-1. Let j = k 1 +1
, that is, we consider the subpattern w 1 w 2 . . . w k1+2 . Again, conditioning on the first step, note that the joint generating function of the first return time to the subpattern w 1 w 2 . . . w k1+1 and the associated count of the forbidden patterns within that return time, conditional on not entering state w k1+2 at the first step, is given by

H k1+1 (z 1 , z 2 ) = p w k 1 +1 ,1-w k 1 +2 z 1 z 2 A k1+1 1 -p w k 1 +1 ,w k 1 +2 , (19)
where the A j and L i (j, a) have been introduced in ( 11) and ( 6), respectively. Actually, H k1+1 (z 1 , z 2 ) differs from its counterparts H j (z 1 , z 2 ), j ≤ k 1 , (cf. ( 17) and ( 18)) by the presence of z 2 in front of A k1+1 . The presence of z 2 accounts for unaccounted otherwise occurrence of a forbidden pattern (a zero run of length less than d) at the first step when one fails to reach in one step the state w k1+2 from the already reached subpattern w 1 w 2 . . . w k1+1 . Further, similarly to the preceding cases and applying the strong Markov property to the consecutive entry times to the subpattern w 1 w 2 . . . w k1+1 , one gets that

G (s) k1+2 (z 1 , z 2 ) = p w k 1 +1 ,w k 1 +2 z 1 G (s) k1+1 (z 1 , z 2 ) 1 -(1 -p w k 1 +1 ,w k 1 +2 )H k1+1 (z 1 , z 2 ) = p w k 1 +1 ,w k 1 +2 z 1 G (s) k1+1 (z 1 , z 2 ) 1 -p w k 1 +1 ,1-w k 1 +2 z 1 z 2 A k1+1 .
Thus, [START_REF] Fu | Distribution Theory of Runs and Patterns and its Applications[END_REF] holds for j = k 1 + 1. Likewise, one gets that ( 13) and ( 14) hold for j = k 1 + 1. Exactly the same arguments, as those used in the case for j = k 1 + 1 apply to any j such that k

1 + 1 ≤ j ≤ k 1 + d -1.
Therefore, ( 12), ( 13) and ( 14) hold for j

= k 1 + 1, k 1 + 2, . . . , k 1 + d -1. Consider now j = k 1 + d, k 1 + d + 1, . . . , k 1 + k 2 -1. These j's do not belong to J 1 ∪ J 2 . Note that the relevant H j (z 1 , z 2 ) is given by H j (z 1 , z 2 ) = p wj ,1-wj+1 z 1 A j 1 -p wj ,wj+1 , (20)
that is, (20) has the same form as that of ( 17) and [START_REF] Lothaire | Applied Combinatorics on Words[END_REF]. This is due to the observation that at the first step when w j+1 is not reached from the already reached subpattern w 1 w 2 . . . w j a forbidden pattern does not occur (the reached zero run is of length at least d and of course less than k). Therefore, (8), ( 9) and ( 10)

hold for j = k 1 + d, k 1 + d + 1, . . . , k 1 + k 2 -1.
Consider now the case j = k 1 + k 2 . This j belongs to J 2 . Note that the relevant H j (z 1 , z 2 ) for the joint g.f. of the first return time to the subpattern w 1 w 2 . . . w k1+k2 and the associated count of the forbidden patterns within that return time, conditional on not entering state w k1+k2+1 at the first step, is given by

H k1+k2 (z 1 , z 2 ) = p w k 1 +k 2 ,1-w k 1 +k 2 +1 z 1 B k1+k2 1 -p w k 1 +k 2 ,w k 1 +k 2 +1 , (21)
where B j is given in [START_REF] Li | A martingale approach to the study of occurrence of sequence patterns in repeated experiments[END_REF]. More specifically, note first that B j differs from A j only through the generating function associated with the indicator function L j (j, 1 -w j+1 ) (cf. ( 6)). This g.f. is G

(1-wj ) j

for A j and G (k2n-0) j (n = 1 for j = k 1 + k 2 ) for B j , and it accounts for what happens after the first step given L j (j, 1 -w j+1 ) = 1. Further, note that conditioning on not entering state w k1+k2+1 at the first step means that a run of zeros of length exactly k 1 + k 2 + 1 has been reached, that is after the first step the current state zero is preceded by exactly k 1 + k 2 zeros. After that first step is made one waits until subpattern w 1 w 2 . . . w k1+k2 is reached. Therefore, noticing that after the first step no overlap occurs, that is

L k1+k2 (k 1 + k 2 , 1 -w k1+k2+1 ) = 1,
one can see that the relevant generating function which will capture all occurrences of forbidden patterns up to this waiting time is given by G (k2-0) k1+k2 (z 1 , z 2 ). Therefore, it is clear now that (8), ( 9) and ( 10) with A j replaced by B j hold for j = k 1 + k 2 . Note that for the other j's from J 2 , such as say j = k 1 + k 2 + k 3 + k 4 , an overlap may occur (for example if k 4 < k 2 ) after the first step but then the relevant g.f.

(G (w1w2...w k 1 +k 2 ) k1+k2+k3+k4 ) in the expression for B j will capture all occurrences of forbidden patterns. Recall that the indicator functions appearing in the expressions for A j and B j sum to 1.

It is easy to see that the same arguments as those used for j = 1, 2, . . . , k 1 + k 2 apply for j > k 1 + k 2 .

The proof of Theorem 1 is complete. ✷ Remark 3.1 Note that the generating functions G (r-0) j (z 1 , z 2 ) play a pivotal role, through the relevant entry in the expression for B j , in the process of evaluating the relevant generating functions G (s) j (z 1 , z 2 ) and G (w1w2...w h ) j (z 1 , z 2 ). Therefore, only G (k2i-0) j (z 1 , z 2 ) for i = 1, 2, . . . , are to be evaluated for each j.

Theorem 1 provides a route for exact evaluation of the G (z 1 , z 2 ) for h such that w 1 w 2 . . . w h is the longest prefix, which is also a suffix, to the pattern w.

Numerical Analysis

In this section, we present some numerical results. Using Maple 9, we derived explicit expressions for the joint generating functions given in Theorem 1 for the patterns in our numerical examples. These provided us with explicit expressions for the probability generating function G Y (z)/(1 -z). We used the numerical procedure introduced by Abate and Whitt [START_REF] Abate | Numerical inversion of probability generating functions[END_REF]. This procedure is very ! fast and computes the exact probabilities with any given, in advance, accuracy. The computation was implemented on Powerbook G4 using Maple 9. The derivation of the expression for G Y (s) r (z)/(1 -z) is almost instantaneous.

In the example presented in Table 1 we compute the probabilities P (N n ≥ r| N (d,k) Yr = 0), r = 1, 2, . . . , with initial symbol X 1 = 0 or 1, for w = 100100100, for d = 1 and k = 4 and transition probabilities p 0,0 = 0.4, p 0,1 = 0.6, p 1,0 = 1, p 1,1 = 0. Note that if d > 0 then p 1,0 = 1 because runs of 1's are not allowed in such sequences. Runs of 1's are allowed only in (0, k)-sequences.

Tab. 1: Probabilities for the number of occurrences, Nn, of w = 100100100 in a random (1, 4)-sequence of length n = 500 with p0,0 = 0.4, p0,1 = 0.6, p1,0 = 1, p1,1 = 0.

m (z 1 , z 2 )

 12 we denoted the joint generating function of the waiting time, Y 1 , until the first occurrence of the pattern w = w 1 w 2 . . . w m ,with initial symbol s, and the associated count, N (d,k) Y1 , of occurrences of the so-called forbidden patterns, and with G (intersite) m

  a) = I(w 2 , w 3 , . . . , w j , a) L 2 (j, a) = I(w 2 , w 3 , . . . , w j , a)I(w 3 , w 4 , . . . , w j , a) . . . = . . . L r (j, a) = I(w 2 , w 3 , . . . , w j , a) . . . I(w r , w r+1 , . . . , w j , a)I(w r+1 , w r+2 , . . . , w j , a) . . . = . . . L j (j, a) = I(w 2 , w 3 , . . . , w j , a)I(w 3 , w 4 , . . . , w j , a) . . . I(w j , a),

j

  (z 1 , z 2 ) and G (w1w2...w h ) j (z 1 , z 2 ). In particular, these contain the generating functions of interest, that is G (s) m (z 1 , z 2 ) and G (intersite) m (z 1 , z 2 ). More specifically, note that G (intersite) m (z 1 , z 2 ) is equal to G (w1w2...w h ) m

r

  and subsequently explicit expressions for the cumulative generating function of Y (s) r , since the latter g.f. is equal toG Y (s) r (z)/(1-z). Recall that the distribution of Y (s)r , is equal to the conditional distribution of the waiting time until the r-th occurrence of the pattern of interest given there were no forbidden patterns up to time Y (s) r . The relevant probabilities, that is P (Y r ≤ n -1| N (d,k) Yr = 0), (= P (N n ≥ r| N (d,k) Yr = 0)), are computed via a numerical inversion of the cumulative generating function G Y (s) r

  Y 2 , Y 3 , . . . are independent random variables such that Y 2 , Y 3 , . . . are identically distributed with the following distributions. The distribution of Y

	Therefore, the joint generating function G Y (s) r distribution of Y r given N (d,k) Y (s) r = 0. Further assume that Y (z 1 , z 2 ) renders the generating function of the conditional (s) 1 , (s) 1 is equal to the conditional distribution of the waiting time Y 1 to see for the first time the pattern w,
	if the starting symbol is s (s = 0 or 1) and given no forbidden pattern has occurred up to time Y 1 , that is, given N (d,k) (s) = 0. The distribution of Y 2 is equal to the conditional distribution of the intersite distance Y 1 between two consecutive occurrences of the pattern w given no forbidden pattern has occurred within that
	intersite distance. Then, in view of the strong Markov property, the conditional distribution of Y r given
	N (d,k)
	1, 0)	.

The work of this author was supported in part by the NSF Grants CCR-0208709, CCF-0513636, DMS-0503742, and NIH Grant R01 GM068959-01.

1365-8050 c 2007


Sandi Klavžar

Sergey Shpectorov

Tribes of cubic partial cubes

Keywords: partial cube, hypercube, isometric embedding, algorithm, tribe

Partial cubes are graphs isometrically embeddable into hypercubes. Three infinite families and a few sporadic examples of cubic partial cubes are known. The concept of a tribe is introduced as means to systematize the known examples and establish relations among them. Efficient methods of computation of tribes are developed and several concrete tribes, that include known, as well as new cubic partial cubes, are computed by hand and with the use of a computer.

Introduction

Graphs that admit isometric embeddings into hypercubes are known as partial cubes. They were introduced by Graham and Pollak (22) as a model for interconnection networks and were extensively studied afterwards, see, for instance, (1; 6; 13; 15; 18; 22; 30; 36; 37) and the books (12; 25). Partial cubes also found several other applications. They are used in mathematical chemistry (27; 28), computational biology (5; 14), media theory [START_REF] Falmagne | Media theory[END_REF], and psychology [START_REF] Ovchinnikov | Hyperplane arrangements in preference modelling[END_REF]. The variety of partial cubes is surprisingly rich, a fact that can in particular be justified by the variety of median graphs. The latter graphs form a very special subclass of partial cubes (cf. [START_REF] Mulder | The Interval Function of a Graph[END_REF]), yet it has been demonstrated in [START_REF] Imrich | Median graphs and triangle-free graphs[END_REF] that there are, roughly speaking, as many median graphs as triangle-free graphs. More precisely, it is proved that a given graph G on n vertices and m edges is triangle-free if and only if its associated graph G is a median graph, where G is a graph on n + m + 1 vertices and n + 2m edges. A related result due to Bandelt and van de Vel [START_REF] Bandelt | Superextensions and the depth of median graphs[END_REF] asserts that the simplex graph of an arbitrary graph is always median. Note however that the size of the simplex graph can be exponential with respect to the original graph.

It is therefore surprising that it is not easy to find regular partial cubes. This has first been encountered by Weichsel (35) who proved that among distance regular graphs only hypercubes, even cycles, and the middle-level graphs are partial cubes. Since the Cartesian product of (regular) partial cubes is again a (regular) partial cube, there are of course several infinite series of regular partial cubes. For instance, as even cycles are partial cubes, so are the toroidal graphs C 2k C 2n , k, n ≥ 2.

The problem of classifying cubic partial cubes is around for about a decade. As far as we know, the problem has been explicitly written down for the first time in [START_REF] Klavžar | Partial cubes as subdivision graphs and as generalized Petersen graphs[END_REF], where it is proved among other statements that P (10, 3) is the only partial cube among the generalized Petersen graphs. Some other examples of cubic partial cubes were known before, cf. [START_REF] Deza | Scale-Isometric Polytopal Graphs in Hypercubes and Cubic Lattices[END_REF], while in [START_REF] Bonnington | On cubic and edge-critical isometric subgraphs of hypercubes[END_REF] and in [START_REF] Brešar | Cubic inflation, mirror graphs, regular maps, and partial cubes[END_REF] several new examples were constructed. It has been recently proved that among the cubic plane graphs whose faces are squares and hexagons there are precisely 5 partial cubes, all of them known before, see [START_REF] Deza | Graphs 4 n that are isometrically embeddable in hypercubes[END_REF].

Clearly, even prisms K 2 C 2n form an infinite series of cubic partial cubes. Besides this series, only a few sporadic examples have been known until recently (i) , cf. Table 1. In the present paper we continue the search for cubic partial cubes and for this sake we introduce tribes of partial cubes. Using this concept, the related theory, and computational methods, we determine the tribes of all previously known cubic partial cubes. Among the graphs in these tribes we find 21 new cubic partial cubes. The computations were performed partly by hand and partly in the computer algebra system GAP, see [START_REF]GAP-Groups, Algorithms, and Programming[END_REF].

We proceed as follows. In the remainder of this section basic definitions are given. Then, in Section 2, we present the list of previously known cubic partial cubes. In the subsequent section we revisit the well-known concepts of expansion and contraction and in particular introduce superconvex partitions.

In Section 4 our central concept-tribe-is introduced. Then we consider the tribe of the generalized Petersen graph P (10, 3) and show that it consists only of P (10, 3) itself. The remaining known cubic partial cubes are planar, hence in Section 6 we restrict our investigations to the planar case and prepare the necessary theory for our computations. We also show that the even prisms K 2 C 2n form a tribe. Finally, in Section 7, we presents the results of the explicit computations of the tribes of the remaining graphs from Table 1.

A subgraph H of G is called isometric if d H (u, v) = d G (u, v) for all u, v ∈ V (H), where d G (u, v)
denotes the usual shortest path distance. Also, H is convex, if for all u, v ∈ V (H), all shortest u, v paths from G belong to H. A convex subgraph is isometric but the converse need not be true. We call a subgraph H superconvex if for all u, v ∈ H, all paths between u and v of length ≤ d G (u, v) + 1 are contained in H. In general superconvexity is a stronger property than convexity. For bipartite graphs, however, the two properties are equivalent. A graph G is a median graph if there exists a unique vertex x to every triple of vertices u, v, and w such that x lies simultaneously on a shortest u, v-path, shortest u, w-path, and shortest w, v-path.

The Cartesian product G H of graphs G and H is the graph with vertex set V (G) × V (H) where the vertex (a, x) is adjacent to the vertex (b, y) whenever ab ∈ E(G) and x = y, or a = b and xy ∈ E(H). The Cartesian product is commutative and associative, the product of k copies of K 2 is the k-dimensional hypercube or k-cube Q k . A graph is called prime (with respect to the Cartesian product) if it cannot be written as the Cartesian product of two nontrivial graphs. It has been observed in (3) that a cubic partial cube is either an even prism or it is a prime graph. (i) In September 2005, when this paper was in preparation, David Eppstein informed us of his discovery of a connection between cubic partial cubes and simplicial arrangements of lines. This leads to two more infinite series and a number of new sporadic examples of cubic partial cubes, see [START_REF] Eppstein | Cubic partial cubes from simplicial arrangements[END_REF]. We briefly discuss this development in Section 8.

Known cubic partial cubes

In Table 1 the list of known sporadic cubic partial cubes is presented, where n stands for the number of vertices and dim for the dimension of the smallest hypercube into which the graph embeds isometrically.

n dim graph ref [START_REF] Gedeonova | Constructions of S-lattices[END_REF] Let us have a closer look at the table. There we find two short series of graphs and 6 additional examples. The latter examples are the generalized Petersen graph P (10, 3), the truncated octahedron B 1 , the chamfered cube, the twisted chamfered cube, the truncated cuboctahedron CI(Q 3 ), and the truncated icosidodecahedron CI(Icosahedron). The truncated octahedron is also known as the permutahedron Π 3 and has appeared elsewhere, cf. [START_REF] Gedeonova | Constructions of S-lattices[END_REF].

The first short series B 1 , B ′ 1 , B ′′ 1 , B ′′′ 1 , B 2 with 4 new examples has been constructed in (3) by means of expansion procedures. It follows from the investigations in the present paper that this series cannot be extended.

In further search for new cubic partial cubes the following operation turned out to be useful. Let G be a graph without vertices of degree one embedded into some closed surface. Then the cubic inflation CI(G) is defined as follows, see [START_REF] Brešar | Cubic inflation, mirror graphs, regular maps, and partial cubes[END_REF]. Replace each vertex v ∈ V (G) of degree d by a 2d-cycle Q v , and then replace every edge uv of G by two edges joining Q u and Q v in such a way that an embedded cubic graph on the same surface is obtained in which all cycles Q v are facial and all edges of G give rise to 4-faces in that embedding. CI(G) can also be described as the dual of the barycentric subdivision of G (4; 31) or the truncation of the medial graph of G (21) that can in turn be described as the {0, 1, 2}-Wythoffian (7; 8). Note that the truncated octahedron B 1 can also be represented as CI(K 4 ).

The graphs G 1 , . . . , G 5 that appear in Table 1 are shown in Fig. 1. The cubic inflations of these graphs provided the last series of five cubic partial cubes. We conclude this section by pointing out that it has been verified by a computer search that Table 1 is complete up to 30 vertices (3). In other words, there are just three prime cubic partial cubes on at most 30 vertices: P (10, 3), B 1 , and

B ′ 1 . G G G G G 1 2 3 4 5 B' B B'' B''' B 1 1 1 1 1 2
Fig. 1: Graphs from Table 1.

Expansion and contraction

The concept of expansion is due to Mulder (32;[START_REF] Mulder | The Interval Function of a Graph[END_REF] in the context of median graphs and Chepoi [START_REF] Chepoi | d-Convexity and isometric subgraphs of Hamming graphs[END_REF] in the context of partial cubes (and partial Hamming graphs). We say that two nonempty isometric subgraphs H 0 and H 1 form an isometric cover of a graph H provided that H = H 0 ∪ H 1 , by which we mean that We next describe the operation of contraction. We say that superconvex subgraphs G 0 and

V (H) = V (H 0 ) ∪ V (H 1 ) and E(H) = E(H 0 ) ∪ E(H 1 ). If H is connected then H 0 ∩ H 1 = ∅
G 1 form a superconvex partition of G if G 0 and G 1 partition G. (More precisely, V (G 0 ) and V (G 1 ) partition V (G).) When G is partitioned by subgraphs G 0 , G 1 , we let M (G 0 , G 1 ) denote the set of edges of G connecting G 0 with G 1 . If G is connected and G 0 , G 1 are nonempty then M (G 0 , G 1
) is also nonempty. For e ∈ M (G 0 , G 1 ), we let e 0 and e 1 denote the end vertices of e that are in G 0 and G 1 , respectively.

Proposition 3.1 Suppose subgraphs G 0 and G 1 partition G. Then G 0 , G 1 is a superconvex partition if and only if d G0 (e 0 , f 0 ) = d G1 (e 1 , f 1 ) for all e, f ∈ M (G 0 , G 1 ).
Proof: Suppose G 0 and G 1 are superconvex. In particular, for i = 0, 1,

d Gi (u, v) = d G (u, v) for all u, v ∈ G i .
Suppose by way of contradiction that, say, d G (e 0 , f 0 ) < d G (e 1 , f 1 ). This means that the length of a shortest path from e 1 to f 1 passing through e 0 and f 0 is d G (e 0 , f 0 ) + 2 ≤ d G (e 1 , f 1 ) + 1. Since G 1 , is superconvex, we get e 0 , f 0 ∈ G 1 , a contradiction. Hence, d G (e 0 , f 0 ) ≥ d G (e 1 , f 1 ), and we get equality by symmetry. Now suppose d G0 (e 0 , f 0 ) = d G1 (e 1 , f 1 ) for all e, f ∈ M (G 0 , G 1 ). Suppose by contradiction that, say, G 0 is not superconvex. Then, for some u, v ∈ G 0 , there exists a path between u and v of length at most d G (u, v) + 1, that is not fully contained in G 0 . Let e be the first edge on this path, that crosses from G 0 to G 1 , and let f be the first edge on the path, crossing back in G 0 . The part of the path between e 0 and f 0 has length at most d G (e 0 , f 0 ) + 1. Furthermore, every intermediate vertex on this subpath lies in

G 1 . Thus, d G (e 0 , f 0 ) + 1 ≥ d G1 (e 1 , f 1 ) + 2, that is, d G (e 0 , f 0 ) > d G1 (e 1 , f 1 ). This yields a contradiction, since d G0 (e 0 , f 0 ) ≥ d G (e 0 , f 0 ).
✷ Suppose G 0 and G 1 form a superconvex partition of G. The contraction of G with respect to G 0 , G 1 is the graph H obtained from G by removing from it all edges e ∈ M (G 0 , G 1 ) and by identifying e 0 with e 1 for each e. Notice that it follows from Proposition 3.1 that e 0 = f 0 for e, f ∈ M (G 0 , G 1 ) implies e 1 = f 1 , and vice versa. If e i is adjacent with f i then also e 1-i is adjacent with f 1-i . In this case, the edge e 0 f 0 is identified with the edge e 1 f 1 .

The subgraphs G 0 , G 1 , and the set of edges M (G 0 , G 1 ) have already appeared in the literature on partial cubes. For an edge ab of a graph G let

W ab = {u | u ∈ V (G), d G (u, a) < d G (u, b)} , W ba = {u | u ∈ V (G), d G (u, b) < d G (u, a)} , F ab = {uv ∈ E(G) | u ∈ U ab , v ∈ U ba }.
The first characterization of partial cubes is due to Djoković (13): A graph G is a partial cube if and only if it is bipartite and if for every edge ab of G the subgraphs W ab and W ba are (super)convex.

Proposition 3.2 If G 0 , G 1 is a superconvex partition of a graph G then G 0 = W e0e1 , G 1 = W e1e0 , and M (G 0 , G 1 ) = F e0e1 for every e ∈ M (G 0 , G 1 ).
Proof: Set a = e 0 and b = e 1 . It suffices to show that G 0 ⊆ W ab and, symmetrically,

G 1 ⊆ W ba . Suppose d G (u, b) ≤ d G (u, a)
for some u ∈ G 0 . Then there exists a path from a to u via b, that has length

d G (u, b) + 1 ≤ d G (u, a) + 1. By superconvexity of G 0 , we get that b ∈ G 0 , a contradiction.
✷ We end this section with a remark that if a graph G is obtained from a graph H via expansion with respect to an isometric cover H 0 , H 1 then the images of H 0 and H 1 in G (that is, H ′ 0 and H ′ 1 ) form a superconvex partition of G. Consequently, H can be recovered from G via the corresponding contraction. Reversely, if a graph H is obtained from a graph G via contraction with respect to a superconvex partition G 0 , G 1 then the images of G 0 and G 1 in H form an isometric cover, and G can be recovered from H via the expansion with respect to this isometric cover. In this sense, expansion and contraction are inverse to each other.

Tribes

The graphs, on which we now focus our attention, are regular partial cubes, especially, cubic partial cubes. The class of partial cubes is closed with respect to expansions and contractions. This is, in essence, the result of ( 6). Let us now investigate conditions, under which expansion and contraction preserve regularity. The following two propositions are applicable to arbitrary regular graphs (not necessarily partial cubes).

Suppose H is a regular graph of degree n. Suppose further that G is an expansion of H with respect to an isometric cover H 0 , H 1 . For v ∈ H 0 ∩ H 1 let a v be the number of neighbors of v outside of H 0 , b v the number of neighbors outside of H 1 , and c v the number of neighbors in H 0 ∩ H 1 .

Proposition 4.1 Under the above assumptions, G is regular if and only if one of the following is true:

(1) H 0 = H 1 = H, and G = H K 2 is of degree n + 1; or (2) G has degree n and, furthermore,

a v = b v = 1 and c v = n -2 for all v ∈ H 0 ∩ H 1 . Proof: If H 0 = H 1 = H then, clearly, (1) holds. Otherwise, there is a vertex outside of H 0 ∩ H 1 . The corresponding vertex of G has degree n. Therefore, if G is regular, it must be of degree n. Let v ∈ H 0 ∩ H 1 . Clearly, a v + b v + c v = n. Since the degree of v 0 in G is 1 + b v + c v and the degree of v 1 is a v + 1 + c v , we get the claim. ✷ In the cubic case, G is again cubic if and only if a v = b v = c v = 1.
In particular, H 0 ∩ H 1 must be a disjoint union of edges. We will call such an expansion a cubic expansion.

Suppose now that H is obtained from G by contraction with respect to a superconvex partition G 0 , G 1 .

For i = 0, 1, set U i = {e i | e ∈ M (G 0 , G 1 )}.
According to Proposition 3.1, the mapping sending e 0 to e 1 for all e ∈ M (G 0 , G 1 ), establishes an isomorphism between distance spaces U 0 and U 1 . In particular, this mapping is also an isomorphism of the graphs induced on U 0 and U 1 .

Suppose G is regular of degree n.

Proposition 4.2 The contraction H is regular if and only if one of the following holds:

(1) U 0 = G 0 and U 1 = G 1 ; in this case H has degree n -1;

(2) the graph on U 0 is regular of degree n -2; here H has degree n.

Proof: If U 0 = G 0 and U 1 = G 1 then, clearly, (1) holds. If there is a vertex in G outside of U 0 ∪ U 1 then the corresponding vertex of H has degree n. So H must be of degree n. For e ∈ M (G 0 , G 1 ), let a be the number of neighbors of e 0 in G 0 \ U 0 and b the number of neighbors in U 0 . Then n = a + b + 1. Since e 1 has the same number b of neighbors in U 1 , it follows that e 1 must have exactly a neighbors in

G 1 \ U 1 .
Therefore, the unified e 0 , e 1 vertex of H has degree a + b + a. This yields a = 1 and b = n -2. ✷ When G is cubic, the contraction H is also cubic if and only if the graph on U 0 is a disjoint union of edges. In this case we call the contraction a cubic contraction.

We can now introduce our central concept-tribes. If G is a cubic partial cube then every graph obtained from G by cubic expansion or cubic contraction is again a cubic partial cube. A tribe of cubic partial cubes is a minimal nonempty collection of such graphs, closed under cubic expansions and cubic contractions. The tribe containing a particular graph G will be referred to as the G-tribe. [START_REF] Bryant | Neighbor-net: An agglomerative method for the construction of phylogenetic networks[END_REF] The case of P [START_REF] Deza | A zoo of l 1 -embeddable polytopal graphs[END_REF][START_REF] Bonnington | On cubic and edge-critical isometric subgraphs of hypercubes[END_REF] In this section we prove the following Proposition 5.1 The generalized Petersen graph P (10, 3) admits no cubic expansions and no cubic contractions. Consequently, the P (10, 3)-tribe consists only of P (10, 3) itself.

We will prove this proposition in a sequence of lemmas, that also introduce some of the ideas involved in tribe computations. Lemma 5.2 If the contraction of a cubic graph G with respect to a superconvex partition G 0 , G 1 is a cubic contraction then every edge from M (G 0 , G 1 ) is contained in an isometric 4-cycle. In particular, P (10, 3) admits no cubic contractions.

Proof: Suppose e ∈ M (G 0 , G 1 ). By the comment after Proposition 4.2, the graph

U 0 = {f 0 |f ∈ M (G 0 , G 1 )} has degree one. If f ∈ M (G 0 , G 1
) is such that f 0 is adjacent to e 0 then e 1 , e 0 , f 0 , f 1 induce an isometric 4-cycle, as follows from Proposition 3.1.

Since the girth of P (10, 3) is six, this graph admits no cubic contractions. ✷ For a cycle C of a cubic graph H, an edge e of H is adjacent to C at vertex v ∈ C if e is incident to v and it does not lie on C. Recall that by the remark after Proposition 4.1, if an isometric cover H 0 , H 1 defines a cubic expansion then H 0 ∩ H 1 is a disjoint union of edges. Lemma 5.3 Suppose an isometric cover H 0 , H 1 of a cubic graph H defines a cubic expansion of H. Suppose C is a cycle of H that is convex as a subgraph of H. Suppose further that e is an edge that is adjacent to C at a vertex v. If e is contained in H 0 ∩ H 1 then the following hold:

(1) C has even length and C ∩ (H 0 ∩ H 1 ) = {v, u}, where u is the vertex opposite v on C;

(2) one of the two halves of C between v and u belongs to H 0 and the other one belongs to H 1 ;

(3) the edge adjacent to C at u lies in This also means that such a vertex u is unique. Therefore, the two edges on u, that lie on C, are not contained in H 0 ∩ H 1 . It follows that the edge that is adjacent to

H 0 ∩ H 1 . e e e
C at u is in H 0 ∩ H 1 .
✷ When edges e and f of a graph H are adjacent at opposite vertices to a convex cycle of even length, we will write e ∼ f . This relation extends by reflexivity and transitivity to an equivalence relation on E(H). This equivalence relation will be denoted by the same symbol ∼. It follows from Lemma 5.3 that if H 0 , H 1 defines a cubic expansion of H and e lies in H 0 ∩ H 1 then the entire ∼-equivalence class of e is contained in

H 0 ∩ H 1 .
Let us now see, what this gives for P (10, 3). Every 6-cycle in P (10, 3) is convex. Every edge e is adjacent to four 6-cycles, cf. Fig. 2, where the four 6-cycles are emphasized.

Each of the 6-cycles leads to a new edge in the equivalence class of e, on Fig. 2 these are the edges e 1 , e 2 , e 3 , and e 4 . Continuing by transitivity, one establishes that all edges of P (10, 3) form a single ∼-equivalence class. This means that no cubic expansion is possible for P [START_REF] Deza | A zoo of l 1 -embeddable polytopal graphs[END_REF][START_REF] Bonnington | On cubic and edge-critical isometric subgraphs of hypercubes[END_REF]. Combining this fact with Lemma 5.2 completes the proof of Proposition 5.1.

Plane graphs

The fourteen remaining examples from Table 1 are plane graphs with convex faces. (We say that a face of a plane graph is convex (respectively, isometric) if the boundary cycle of the face is a convex (respectively, isometric) subgraph.) These properties lead to a very explicit description of possible isometric covers and superconvex partitions and, as a result, to efficient algorithms for computing all cubic expansions and cubic contractions. We realized these algorithms in GAP [START_REF]GAP-Groups, Algorithms, and Programming[END_REF] and used them for the tribe computations presented in the next section.

We also prove in this section that a graph, obtained by cubic expansion from a cubic plane graph with convex faces, inherits these same properties, so that our algorithms are again applicable. Cubic contractions preserve planarity, but not necessarily convexity of the faces. However, as we show in this Fig. 3: A straight-ahead walk in Q3, the corresponding isometric cover and cubic expansion. section, non-convex faces can only arise in a very special situation that never occurs for our graphs.

Let H be a plane cubic partial cube and ab an edge of H. Let W be the edge-face walk on H that starts from ab and continues as follows. Going along an edge uv from u to v, we enter the face at v that is not incident with u. (The edge uv is adjacent to this face at v.) In this face we proceed to the opposite vertex v ′ and exit the face along the edge adjacent to the face at v ′ . We call W a straight-ahead walk; see Fig. 3 where a straight-ahead walk in Q 3 is shown. Proposition 6.1 Suppose H is a plane cubic graph with convex faces. If H 0 , H 1 form an isometric cover of H, defining a cubic expansion, then there exists a straight-ahead walk W such that (1) W has no self-intersections;

(2) for i = 0, 1, H i is induced by all vertices on one side of W and on W itself;

(3) H 0 ∩ H 1 is the disjoint union of the edges lying on W .

Suppose H and H 0 , H 1 are as above. For the proof of Proposition 6.1 we need the following simple fact to be used later as well and an important lemma classifying possible intersections of faces with H 0 ∩ H 1 . Proposition 6.2 For a graph H and subgraphs H 0 and H 1 , suppose H = H 0 ∪ H 1 . Then H 0 , H 1 is an isometric cover if and only if d H0 (u, v) = d H1 (u, v) for all u, v ∈ H 0 ∩ H 1 . Lemma 6.3 Suppose F is a face of H. Then one of the following holds:

(1) F fully lies in H i for some i = 0, 1, and meets H 0 ∩ H 1 trivially;

(2) F fully lies in H i for some i = 0, 1, and meets H 0 ∩ H 1 in an edge; or (3) F meets H 0 ∩ H 1 in two opposite vertices v and u, the two edges adjacent to F at v and u are contained in H 0 ∩ H 1 , and the two halves of F between v and u are contained in different H i .

Proof:

If F meets H 0 ∩ H 1 trivially then, clearly, (1) holds. Suppose v ∈ F ∩ (H 0 ∩ H 1 )
and let e be the unique edge on F that is contained in H 0 ∩ H 1 . If e is adjacent to F then (3) holds by Lemma 5.3, since F is convex. It remains to consider the case where e lies on F . We claim that in this case (2) holds. Suppose by way of contradiction that there is a third vertex w in F ∩ (H 0 ∩ H 1 ). Let f be the edge on w that is contained in H 0 ∩ H 1 . If f is adjacent to F then (3) must holds, a contradiction. Hence, f lies on F . Taking, if necessary, the other end of f as w, we can assume that w is not opposite v. Since F is convex and v and w are not opposite, there exists a unique shortest path between v and w. However, by Proposition 6.2, this shortest path should be contained in both H 0 and H 1 , a contradiction, since H 0 ∩ H 1 is a disjoint union of edges. ✷ We are now ready to prove Proposition 6.1.

Proof of Proposition 6.1. Suppose e is an edge in H 0 ∩ H 1 and let W be the corresponding straightahead walk. Since the faces of H are convex, Lemma 5.3 implies that all edges on W are contained in H 0 ∩ H 1 . This shows that H 0 ∩ H 1 is a disjoint union of several straight-ahead walks. Suppose W intersects another walk W ′ contained in H 0 ∩ H 1 . (We allow for the equality W ′ = W .) There are two possibilities for the intersection. If the intersection is at a vertex w then each walk has an edge on w (and this cannot be the same edge). This yields a contradiction, since the edges in H 0 ∩ H 1 are disjoint. If the intersection of W and W ′ is at a face F then Lemma 6.3 (3) gives a contradiction. Therefore, H 0 ∩ H 1 has no self-intersections. If H 0 ∩ H 1 consists of more than one walk then cutting the sphere through all these walks splits the sphere into more than two parts. However, this means that H 0 and H 1 cannot be both connected. (Notice that this topological argument also can be used to show the absence of self-intersections.) Thus, H 0 ∩ H 1 = W is a single, non self-intersecting walk. This proves (1) and [START_REF] Bonnington | On cubic and edge-critical isometric subgraphs of hypercubes[END_REF].

Considering the faces fully lying on one side of W , we see that either (1), or (2) of Lemma 6.3 must hold for each of these faces. Now connectivity implies [START_REF] Bandelt | Superextensions and the depth of median graphs[END_REF]. ✷ Proposition 6.4 If G is obtained by cubic expansion from a plane cubic graph with convex faces then G is also a plane graph with convex faces.

Proof: Topologically, in this situation the cubic expansion amounts to cutting the plane graph H along the walk W = H 0 ∩ H 1 and inserting a band with the new edges drawn across it, see Fig. 4. So G has a natural structure of a plane graph. With respect to this structure, G has three kinds of faces: (a) the faces of H, that are not affected by the expansion; (b) the faces affected by the expansion; these are the edges as in Lemma 6.3 (3); the gonality of these edges in G increases by two; and (c) the new 4-gonal faces corresponding to the edges on W . Notice that the reverse operation of contraction transforms every path γ ′ on G into a path γ on H. The length of γ is the length of γ ′ minus the number of times γ ′ crosses the inserted band.

Suppose F ′ is a face of G and let F be the corresponding face of H. (If F ′ is of type (c) then F is an edge. Notice that an edge is convex as a subgraph of H.) Let v ′ and u ′ be vertices of F ′ and let v and u be the corresponding vertices of F . Consider a shortest path γ ′ in G from v ′ to u ′ and let γ be the corresponding path in H from v to u. Suppose first that v ′ and u ′ are on the same side of the band (that is, in the same H ′ i for some i = 0, 1). If γ ′ crosses the band, then it crosses the band at least twice, so

d G (v ′ , u ′ ) ≥ d H (v, u) + 2. However, d H (v, u) = d Hi (v, u) = d H ′ i (v ′ , u ′ ), and so d G (v ′ , u ′ ) > d H ′ i (v ′ , u ′ ). This is a contradiction, since H ′ i is a subgraph of G. Thus, γ ′ is fully contained in H ′ i . Now, since H ′ i is a copy of H i , it follows that γ is a shortest path from v to u and so it is contained in F , since F is convex. Hence also γ ′ is contained in F ′ .
When v ′ and u ′ lie on different sides of the band, we similarly consider a shortest path γ ′ in G and the corresponding γ in H. In this case we show that the length of γ is one less than the length of γ ′ and that again γ is a shortest path from v to u. It follows that γ lies on F and, consequently, γ ′ lies on F ′ . ✷ Next we turn to the operation of contraction. We start with a rather general lemma. Lemma 6.5 Suppose G 0 , G 1 form a superconvex partition of a graph G and C is an isometric cycle in G. Then one of the following holds:

(1) C is fully contained in G i for some i = 0, 1; or (2) C has even length and it meets M (G 0 , G 1 ) in two opposite edges.

Proof: If none of the edges on C is in M (G 0 , G 1 ) then case (1) holds. Suppose an edge e from C belongs to M (G 0 , G 1 ). Clearly, after crossing from one part of the partition to the other via e, C must return back, so C contains a second edge, say f , from M (G 0 , G 1 ). Since both parts G i are convex, e 1 and f 1 cannot lie on a shortest path between e 0 and f 0 and, vice versa, e 0 and f 0 cannot lie on a shortest path between e 1 and f 1 . Since C is isometric, this means that the part of C between e 0 and f 0 is a shortest path between these two vertices and, similarly, the part of C between e 1 and f 1 is a shortest path between them. Finally, Proposition 3.1 forces C to have even length and e and f to be opposite.

✷ We now return to the plane graphs. Suppose G is such a graph and suppose that all faces of G are isometric. Let G 0 , G 1 form a superconvex partition of G. Since the faces are isometric, the above lemma implies that all faces, containing edges from M (G 0 , G 1 ), have even gonality and meet M (G 0 , G 1 ) in a pair of opposite edges. Let us make the edges from M (G 0 , G 1 ) the vertices of a new graph, in which two edges are adjacent whenever they are opposite each other on a face. Clearly, this is a graph of degree two and hence it is a union of cycles. Each of these cycles is called a zone (or, sometimes, a railroad). With each zone one can associate a cyclic zone walk on the sphere, in which G is imbedded. Namely, starting from the middle of an edge we go across the face on one side of the edge to the middle of the opposite edge (which is again in the zone), cross into the next face, and so on until we return to the middle of the initial edge from the other side. Proposition 6.6 Suppose G is a plane graph with isometric faces and G 0 , G 1 form a superconvex partition of G. Then M (G 0 , G 1 ) is a single zone. Furthermore, the corresponding zone walk has no selfintersections and each of G 0 and G 1 consists of all vertices on one side of the walk.

Proof: If a zone in M (G 0 , G 1 ) had a self-intersection or if there were two zones or more, then removing from G all edges from M (G 0 , G 1 ) would result in more than two connected components, which is not the case. So M (G 0 , G 1 ) is a single zone and the corresponding walk has no self-intersections. The last claim also follows, since G 0 , G 1 are the connected components of G when all edges from M (G 0 , G 1 ) are removed.

✷ Following the zone walk corresponding to the zone M (G 0 , G 1 ), let us write down the gonalities (the number of edges) of the faces that we cross. This gives a cyclic sequence g 1 , g 2 , . . . , g m , where m is the number of edges/faces in the zone. We will call this sequence the zone sequence. Proposition 6.7 Suppose a plane graph G is cubic with convex faces. Then the contraction defined by G 0 , G 1 is a cubic contraction if and only if 4 appears in the zone sequence in every other place.

Proof: First of all, we argue that every 4-cycle in G is a face. Indeed, suppose C is a 4-cycle. Let F be a face that contains two consecutive edges from C. Since F is convex, we must have F = C.

Now for e, f ∈ M (G 0 , G 1 ), we have that e 0 and f 0 are adjacent if and only if e 0 , f 0 , f 1 , e 1 is a 4-cycle (hence a 4-gonal face). So the claim follows from the remark after Proposition 4.2.

✷ Finally, we show that contractions preserve planarity and discuss under which conditions it preserves convexity of faces. Proposition 6.8 If G is a plane graph with isometric faces then the graph H resulting from the contraction with respect to G 0 , G 1 is again a plane graph with isometric faces.

Proof: By Proposition 6.6, M (G 0 , G 1 ) is a single zone and the corresponding walk has no self-intersections. This implies that the contraction amounts to cutting out a band from the sphere (cf. Fig. 4 with the reversed arrow) and gluing the two disks back together. So H has a natural plane structure. Furthermore, the faces of G that contain no edges from M (G 0 , G 1 ) retain their gonality in H, while the gonality of the faces containing edges from M (G 0 , G 1 ) goes down by two. The 4-gonal faces of this latter type disappear altogether.

Suppose F ′ is a face of H and F is the face of G from which F ′ is produced. Suppose v ′ and u ′ are vertices of F ′ , and suppose γ ′ is a shortest path between them. Let G ′ 0 and G ′ 1 be the images in H of G 0 and G 1 , respectively. Recall that each G ′ i is isomorphic to G i , and that G ′ 0 , G ′ 1 form an isometric cover. Suppose first that v ′ and u ′ are contained together in some G ′ i . Since G ′ i is isometric in H, there is a shortest path between v ′ and u ′ that is fully contained in G ′ i . Let v and u be the preimages of v ′ and u ′ in

G i . Clearly, v, u ∈ F . We have d H (v ′ , u ′ ) = d G ′ i (v ′ , u ′ ) = d Gi (v, u) = d G (v, u). Since F is isometric, d G (v, u) = d F (v, u). Also, d F ′ (v ′ , u ′ ) ≤ d F (v, u). This implies d F ′ (v ′ , u ′ ) ≤ d H (v ′ , u ′ ),
and since F ′ is a subgraph of H, the equality must hold.

Suppose now that v ′ and u ′ are in different G ′ i 's. In particular, neither of the two vertices is in

G ′ 0 ∩ G ′ 1 .
Without loss of generality we may assume that v ′ ∈ G ′ 0 and u ′ ∈ G ′ 1 . Let v and u be the preimages of v ′ and u ′ , respectively. We have that v, u ∈ F . Since every path from v to u necessarily contains an edge from M (G 0 , G 1 ), we must have d H (v ′ , u ′ ) ≤ d G (v, u) -1. To prove the reverse inequality, consider a shortest path γ ′ from v ′ to u ′ . Let x ′ 1 , x ′ 2 , . . . , x ′ k be all the vertices from this path that are contained in G ′ 0 ∩ G ′ 1 . The vertices on γ ′ that precede x ′ 1 are in G ′ 0 . The vertices that follow x ′ k are contained in G ′ 1 . Also, in view of Proposition 6.2, for every i = 1, . . . , k -1, we can substitute the subpath from x ′ i to x ′ i+1 by a subpath of equal length, that is fully contained in G ′ 0 . Thus, without loss of generality, we may assume that all vertices preceding x ′ k are in G ′ 0 . Now we can lift γ ′ to a path γ in G as follows: We lift the part of γ ′ from v ′ to x ′ k into G 0 , we lift the tail of γ ′ , from x ′ k to u ′ , into G 1 , and we connect the two parts of γ by the edge from M (G 0 , G 1 ) between the two preimages of x ′ k . Clearly, γ is a path from v to u and its length is one plus the length of γ ′ . This shows that d

G (v, u) ≤ d H (v ′ , u ′ ) + 1. Thus, d G (v, u) = d H (v ′ , u ′ ) + 1. Finally, since d F (v, u) = d F ′ (v ′ , u ′ ) + 1 and since d F (v, u) = d G (v, u), we get d F ′ (v ′ , u ′ ) = d H (v ′ , u ′ ).
✷ Unfortunately, it is not true that F ′ is convex whenever F is. However, the conditions under which F ′ is not convex are rather restrictive and they do not occur in practice very often. the remaining zones looks the same: the zone walk goes across the top, then down the side, then across the bottom in the opposite direction, and then back up the opposite side. Manifestly, each of these zones defines a superconvex partition and the resulting graph is K 2 C 2n-2 .

We now turn to expansions. When n = 2, we have the cube Q 3 , which has only one class of edges. Hence all straight-ahead walks are as in Fig. 3. Each of them defines an isometric cover and the resulting graph is the hexagonal prism. Now suppose n ≥ 3. As above, we distinguish two kinds of edges. If a straight-ahead walk contains a side edge, then this walk goes up this edge, continues across the top, goes down the opposite side edge, and then crosses the bottom face back to the origin. Such straight-ahead walks do define isometric covers; indeed, the corresponding cubic expansions are the reverse operations to the cubic contractions from the preceding paragraph.

It remains to consider the straight-ahead walks containing the edges of the 2n-gonal top and bottom faces. Suppose, say, e 1 is an edge of the top face. The straight-ahead walk starting from e 1 goes diagonally down the next side face, then along an edge f 1 of the bottom face, climbs diagonally up the next side face, goes along the top edge e 2 , and so on. If n is odd, then the walk goes around the prism and eventually self-intersects. Suppose n is even (and hence n ≥ 4). In this case the straight-ahead walk has no selfintersections. However, it still does not define an isometric cover. Indeed, let a be the second vertex on e 1 and let b be the first vertex on e 2 . (We count in the direction of the walk.) Let H 0 , H 1 be the cover defined by the walk, where H 0 contains the top face and H 1 contains the bottom. Manifestly, d H0 (a, b) = 3, while d H1 (a, b) = 5. Thus, H 0 , H 1 is not an isometric cover. ✷

Explicit tribes of partial cubes

The theory that we have developed in the previous section leads to efficient algorithms listing all cubic expansions and contractions of a given plane cubic partial cube with convex faces. Suppose H and G are such graphs. To construct all cubic expansions of H, do the following:

(1) Construct all straight-ahead walks in H. Notice that each edge lies on a unique straight-ahead walk, so the straight-ahead walks partition the edge set of H. (2) Select those straight-ahead walks W that have no self-intersections.

(3) For each such W , construct H 0 and H 1 as subgraphs induces by the vertices on one side of W and on W . (4) Select isometric covers H 0 , H 1 by verifying the distance condition as in Proposition 6.2. Notice that H 0 ∩ H 1 = W .

To determine all cubic contractions of G, do the following:

(1) Construct all zones in G. Again, the zones partition the edge set of G, and so each edge needs to be dealt with only once. (2) Select all zones Z, whose zone walks have no self-intersections and such that 4 appears in the zone sequence in every other place. (3) For each such Z, construct G 0 and G 1 as the connected components of G with all edges from Z removed. (4) Select superconvex partitions G 0 , G 1 by verifying the distance condition as in Proposition 3.1.

In the case of cubic expansions, planarity of the resulting graph and convexity of its faces is assured by Proposition 6.4. Thus, the above algorithms can immediately be applied to construct further graphs from the same tribe. In the case of cubic contractions, planarity of the resulting graph is assured by Proposition 6.8, while convexity of faces must be verified using Proposition 6.9 before the computation of the tribe can proceed. We now present computational results based on the above approach. The first graph from Table 1 to consider is B 1 . Set B 24 = B 1 to denote the size of this graph. Then the B 24 -tribe consists of 17 graphs and is schematically presented in Fig. 5.

After the complete B 24 -tribe has been determined, 9 new cubic partial cubes have been found. They are squared in the figure. The chain B 24 , B 30 , B 36 , B 42 , B ′ 48 is the chain B 1 , B ′ 1 , B ′′ 1 , B ′′′ 1 , B 2 from Table 1. The graph B 32 is the chamfered cube, B 48 is the truncated cuboctahedron CI(Q 3 ), while B ′ 96 is CI(G 4 ). The four new graphs with up to 60 vertices are depicted in Fig. 6.

The next graph from Table 1 to consider is the twisted chamfered cube. Its tribe consists of just two graphs, the second graph from the tribe is the top graph from Fig. 7. It is not isomorphic to B 40 , hence we have one more cubic partial cube. Similarly, the CI(G 1 )-tribe consists of two graphs, the second graph has 60 vertices and is the middle graph from Fig. 7. Next, the CI(G 2 )-tribe consists of three graphs, CI(G 2 ) on 80 vertices and graphs on 70 and 60 vertices. So in this case both new graphs are obtained by a cubic contraction. The one with 60 vertices is the bottom graph from Fig. 7.

Both the CI(G 3 )-tribe and the CI(G 5 )-tribe consist of a single graph. Finally, the CI(Icosahedron)tribe is shown in Fig. 8, where we have set I 120 = CI(Icosahedron) to denote the size of this graph. The known cubic partial cube (that is not an even prism).

Concluding remarks

Among the known cubic partial cubes only the generalized Petersen graph P (10, 3) is not planar. Hence it would be interesting to find more nonplanar examples. It seems that for this sake new techniques need to be developed. David Eppstein observed (( 16)) that every simplicial line arrangement in the projective plane over the real numbers leads to a (plane) cubic partial cube. Three infinite series and 91 sporadic examples of simplicial arrangements are known [START_REF] Grünbaum | Arrangements of hyperplanes[END_REF]. One of the three infinite series consists of the familiar prisms. It

Fig. 4 :

 4 Fig. 4: Cubic expansion.

Fig. 5 :

 5 Fig. 5: The B24-tribe.

Fig. 6 :

 6 Fig.6: Graphs from the B24-tribe.

Fig. 7 :

 7 Fig.7: The second graph from the twisted chamfered cube tribe, the second graph from the CI(G1)-tribe, and the graph on 60 vertices from the CI(G2)-tribe.

Fig. 8 :

 8 Fig. 8: The I120-tribe.

  for every isometric cover H 0 , H 1 , provided that H 0 and H 1 are themselves nonempty.Suppose H 0 , H 1 is an isometric cover of H. For i = 0, 1, let H ′ i be an isomorphic copy of H i , and for a vertex u ∈ H 0 ∩ H 1 , let u i be the corresponding vertex in H ′ i . The expansion of H with respect to H 0 , H 1 is the graph G obtained from the disjoint union of H ′ 0 and H ′ 1 , where for each u ∈ H 0 ∩ H 1 the vertices u 0 and u 1 are joined by a new edge in G. Chepoi[START_REF] Chepoi | d-Convexity and isometric subgraphs of Hamming graphs[END_REF] proved that a graph is a partial cube if and only if it can be obtained from K 1 by a sequence of expansions.

  Let a and b be the neighbors of v on the cycle C. Since e is contained in H 0 ∩ H 1 , we have that both a and b do not lie inH 0 ∩H 1 . Without loss of generality, a ∈ H 0 \(H 0 ∩H 1 ) and b ∈ H 1 \(H 0 ∩H 1 ).Considering the path from a to b around C (avoiding v), we see that C contains another vertex u that is contained in H 0 ∩H 1 . Since H 0 is isometric there is a shortest path between u and v that is fully contained in H 0 . Since C is convex, this path is contained in C. Similarly, there is a shortest path between u and v that is contained in H

	1	2	e 3	e 4
	Fig. 2: Relation ∼ in P (10, 3).

Proof: 1 ∩ C. Since a ∈ H 1 and b ∈ H 0 , C contains two different shortest paths between u and v. This means that C has even length and that u is opposite v on C.

† Supported in part by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with the Institute of ‡ Research partly supported by the Ministry of Science of Slovenia. 1365-8050

Suppose H is obtained from G via a cubic contraction with respect to G 0 , G 1 . For i = 0, 1, let G ′ i denote the image of G i in H. Proposition 6.9 Under the above assumptions, let F ′ be a face of H and F be the corresponding face of G. Suppose further that F is convex. Then F ′ is not convex if and only if it contains two or more edges from

Proof: Suppose the edges e ′ and f ′ from

Similarly, there is a shortest path β ′ between v ′ and u ′ that is fully contained in G ′ 1 . Let a ′ (respectively, b ′ ) denote the vertex that follows v ′ on α ′ (respectively, β ′ ). By the minimality of m, neither a ′ , nor b ′ is incident with e ′ . Since e ′ lies on F ′ , we conclude that either a ′ , or b ′ does not lie on F ′ . Hence F ′ is not convex. Now suppose F ′ is not convex, namely, there is a shortest path γ ′ between v ′ , u ′ ∈ F ′ , that is not contained in F ′ . We will assume that the length m = d H (v ′ , u ′ ) of γ ′ is minimal among all such choices of v ′ , u ′ , and γ ′ . In particular, none of the intermediate vertices from γ ′ lies on F ′ . Note that this property holds for every path between v ′ and u ′ that has length m and is not fully contained in F ′ . Let v, u ∈ F be preimages of v ′ and u ′ . Let i, j ∈ {0, 1} be defined by v ∈ G i and u ∈ G j .

Suppose some intermediate vertex

Since G ′ 0 and G ′ 1 are isometric in H, we can assume without loss of generality that the part of γ ′ from v ′ to t ′ is fully contained in G ′ i and the part from t ′ to u ′ is fully contained in G ′ j . Such a path can be lifted to a shortest path γ from v to u. (The length of γ is m if i = j, and it is m + 1 if i = j.) Since F is convex, we must have that γ lies on F , and therefore, γ ′ lies on F ′ , a contradiction. Thus, no intermediate vertex of

for some k = 0, 1. If i = k or j = k then γ ′ can be lifted to a shortest path γ from v to u, again yielding a contradiction with convexity of F . Hence i = j = 1k. In particular, this implies that v

which is an edge!), then m = 1, clearly giving a contradiction. Thus, v ′ and u ′ are incident to two different edges, say e ′ and f ′ , from

It remains to show that both e ′ and f ′ lie on F ′ . However, this is clear. Indeed, by the minimality of m, the first edge along γ ′ does not lie on F ′ . Hence the other two edges on v ′ must lie on F ′ ; one of them is e ′ . By symmetry, also f ′ lies on F ′ . ✷ The condition for the non-convexity of F ′ can also be stated in terms of G, F and the zone Z = M (G 0 , G 1 ). Namely, F ′ is non-convex if and only if the zone walk corresponding to Z crosses two different quadrangular faces adjacent to F (but not F itself).

We conclude this section with the following illustration of our theory.

Proposition 6.10 The even prisms K 2 C 2n form a tribe.

Proof: It suffices to show that every cubic expansion of K 2 C 2n coincides with K 2 C 2n+2 and that every cubic contraction of

We start with contractions. First of all, the cube Q 3 = K 2 C 4 has no cubic contractions, since it has no non-quadrangular faces. Let n ≥ 3. In this case the prism has, up to symmetries, two types of edges:

(1) the edges of the two 2n-gonal faces (top and bottom of the prism); and (2) the side edges, each of which is incident with two quadrangular faces (sides of the prism). The edges of the second kind form a zone. This zone does not lead to a cubic contraction because the zone sequence is the constant 4. Each of would be interesting to systematically consider all other examples to see to which known or new partial cubes they lead, and what their corresponding tribes are.