F Thomas Bruss
email: tbruss@ulb.ac.be

Philippe Flajolet

On a Class of Optimal Stopping Problems with Mixed Constraints

Keywords: Selection Problem, multiple selection, full information, definite constraint, expectational constraint, double-recursive functions, Riccati differential equation, knapsack problem, minimal spanning tree

Let X1, X2, • • • , Xn be independent, identically distributed uniform random variables on [0, 1]. We can observe the outcomes sequentially and must select online at least r of them, and, moreover, in expectation at least µ ≥ r. Here µ need not be integer. We see X k as the cost of selecting item k and want to minimize the expected total cost under the described combined (r, µ)-constraint. We will see that an optimal selection strategy exists on the set Sn of all selection strategies for which the decision at instant k may depend on the value X k , on the number N k of selections up to time k and of the number n-k of forthcoming observations. Let σr,µ(n) be the corresponding Sn-optimal selection strategy and vr,µ(n) its value. The main goal of this paper is to determine these and to understand the limiting behavior of vr,µ(n). After discussion of the specific character of this combination of two types of constraints we conclude that the Sn-problem has a recursive structure and solve it in terms of a double recursion. Our interest will then focus on the limiting behavior of nvr,µ(n) as n → ∞. This sequence converges and its limit allows for the interpretation of a normalized limiting cost L(r, µ) of the (r, µ)-constraint. Our main result is that L(r, µ) = gr((µ -r) 2 /2) where gr is the r th iterate of the function g(x) = 1 + x + √ 1 + 2x.

Our motivation to study mixed-constraints problems is indicated by several examples of possible applications. We also shortly discuss the intricacy of the expectational part of the constraint if we try to extend the class of strategies Sn to the set of full-history-dependent and/or randomized strategies.

Introduction

Let X 1 , X 2 , • • • , X n be i.i.d. U [0, 1]-variables. We can observe the X k 's sequentially and must decide at each time (instant) k whether to select X k , or else to refuse it and to continue with further observations. The number of selections is subject to two different types of constraints. On the one hand there is a prescribed minimal number r of selections, and, on the other hand, the selection strategy should accept, 1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France in expectation, a minimum number µ of the X k 's. We interpret X i as the cost of item i. Our objective is to minimize the expected total cost of selected items under the two constraints over the set of all non-anticipative online selection strategies. Non-anticipative means that we have no prophetical skills whatsoever, and online, that each decision to select or refuse must be taken on the spot, without recall on preceding observations.

Mathematical formulation

For n ∈ N fixed let X 1 , X 2 , • • • , X n be i.i.d. uniform random variables on [0, 1] defined on the probability space (Ω, F, P ). Further let I 1 , I 2 , • • • , I n be indicator functions fully adapted to the X k in the sense that the events {I k = 0}, {I k = 1} are in the σ-field F k generated by (X 1 , X 2 , • • • , X k ). We say that X k is selected if I k = 1, and refused if I k = 0. Let T n be the set of all such stopping vectors τ := τ n = (I 1 , I 2 , • • • , I n ). Our objective is to find, provided it exists, the value

I k ≥ µ, µ ∈ R, µ ≥ r.
(1.4)

The constraints (1.3) and (1.4) will be referred to as D-constraint and E-constraint respectively, and any non-anticipative stopping rule satisfying them both as admissible. The corresponding strategy τ r,µ (n) minimizing the total cost (loss) in the class of admissible rules, provided it exists, is called optimal.

Classification of problem-type

In the terminology of optimal stopping problems, this problem is a finite-horizon i.i.d. full-information multiple stopping problem. The meaning of multiple stopping is obvious. Full-information refers to the hypothesis that the distribution of the X k 's is known to us, and that we are allowed to observe the actual values of these and not only some statistic of these as for instance in rank-based stopping problems. We should and do add the description with mixed constraints, because we have here two different types of constraints on the number of required selections: a definite constraint (D-constraint (1.3)) as well as an expectational constraint (E-constraint (1.4)).

Motivation

As far as the author is aware, this combination of constraints is new. The author's interest in this problem was instigated by David Aldous (private communication, 2006) who asked what is in general known about such problems. Aldous formulated a problem of improving a lower bound of interest for spanning trees in terms of such a stopping problem for r = 1 and µ = 2 and we will return to it later on. (See also Aldous et al. (2008)). Our motivation is now also going further because, once one thinks about it, one sees that the proposed mixed-constraints setting offers a variety of applications: In certain buying/selling problems, for instance, some contract specifications require not only a minimum number of purchases, but also a long-run average "chiffres d'affaires". In the case of buying, our proposed model fits the problem directly; in the case of selling we re-interpret the costs as benefits resulting from sales and would like to solve the equivalent maximization problem. Another example of selection problems where this setting is relevant is the online-knapsack problem: Items, each having utility one, arrive in random order. Time constraints force us to select online from a sequence of incoming different items and to pack without recall. Costs are measured in terms of weight or space, and the total combined utility is supposed to be at least r, with an average of at least µ. There are many other problems along these lines which come to our mind.

In practical problems the verifiability of the E-constraint would have clear limitations, of course. Moreover, as we shall see in Section 2, this constraint needs also special attention from the theoretical point of view. Having said this, we may all agree that the mixed-constrained objective has applicational appeal and should merit our interest.

Related work

In our problem the cost of each selection is simply the value of the variable, that is we pay for what we select. There is no cost of inspection, and the problem has its interest through the new combination of constraints. Models with a fixed inspection cost are different in their structure. Examples for related problems with cost for inspection are the classical house-selling problem studied by [START_REF] Macqueen | Optimal persistence policies[END_REF] and generalized by [START_REF] Stadje | A full-information pricing problem for the sale of several identical commodities[END_REF] as well as the multiple buying-selling problem of [START_REF] Bruss | Multiple buying and selling with vector offers[END_REF].

The literature in the domain of so-called secretary problems shows many papers on selection problems with full-information and varying single constraints as e.g. [START_REF] Chen | Optimal sequential selection of N random variables under a constraint[END_REF], [START_REF] Kurushima | Maximizing the expected duration of owning a relatively best object in a poisson process with rankable observations[END_REF], [START_REF] Mazalov | An explicit formula for the optimal gain in the full-information problem of owning a relatively best object[END_REF][START_REF] Mazalov | An explicit formula for the optimal gain in the full-information problem of owning a relatively best object[END_REF][START_REF] Tamaki | A full-information best-choice problem with finite memory[END_REF]. Sometimes selection means investment (as in [START_REF] Lebek | Optimal strategies in high risk investments[END_REF] and others) and then the cost is measured in terms of limited resources. (For a review of earlier work see e.g. [START_REF] Samuels | Secretary problems. Handbook of Sequential Analysis[END_REF].) The single constraint makes each of these problems quite different from ours. The same holds for the selection problem of [START_REF] Baryshnikov | Sequential selection of an increasing sequence from a mutidimensional random sample[END_REF] of vector-valued observations and the competitive selection problem with two decision makers studied by [START_REF] Enns | The horse game[END_REF] and [START_REF] Bruss | The complete solution of the competitive rank selection problem[END_REF]. And then there are multiple selection problems where the number of selections need not be specified such as e.g. the online monotone subsequence problem studied by [START_REF] Samuels | Optimal sequential selection of a monotone sequence from a random sample[END_REF], [START_REF] Gnedin | Sequential selection of an increasing subsequence from a random sample with geometically distributed sample size[END_REF], and [START_REF] Bruss | Optimal rules for the sequential selection of monotone subsequences of maximum expected length[END_REF]. We note that, here again, the constraint, although being a "moving constraint" for each selection, is still a singletype constraint, namely monotonicity. Our current problem combining two types of constraints seems very different in nature from all of these.

One special case of the described problem has been studied in the literature, and, interestingly, it appeared before secretary problems started to attract attention. This is the so-called Caley/Moser problem [START_REF] Moser | On a problem of cayley[END_REF]). In this problem the decision maker observes sequentially n i.i.d. U [0, 1]-random vari-ables, and exactly one selection must be made, that is r = 1. The Caley/Moser objective was to maximize the expected value of the selected observation. With X k being U [0, 1], the transformation Z k = 1 -X k stays a U [0, 1] variable, which makes it equivalent to our minimization problem. No E-constraint on the number of selections was mentioned in the Caley/Moser problem but it concurs with the implicit constraint µ = 1, of course.

Organization of this paper

In Section 2 we first analyze the problem as stated in (1.1)- (1.4) and see that the problem to find u r,µ (n) cannot be solved by separating the two constraints. We then argue that we should be somewhat restrictive by confining the optimization problem to a subclass S n of selection strategies which, at each instant k, may depend on the current observation X k , on n-k, and on the total number N k of observations selected so far. Hence we replace the problem of finding the overall optimum u r,µ (n) (see (1.1)- (1.4)) by the problem of finding the corresponding optimal value v r,µ (n) over all strategies s ∈ S n . In Section 3. we use a threshold-value argument to find a double recursion for the optimal value v r,µ (n) and prove the existence of an S n -optimal strategy σ r,µ (n) which achieves v r,µ (n). In Section 4. we collect basic properties of v r,µ (n) which will be used in the following sections. Section 5. proposes an algorithm to compute v r,µ (n) and σ r,µ (n) simultaneously. We also give preliminary estimates for the asymptotic behavior of v r,µ (n) with the purpose of preparing the Section 6. This section presents the main asymptotic result: we prove that nv r,µ (n) converges for all r ∈ N and µ ≥ r. We then show via a well defined approximation by a Riccati differential equation that each V r,µ := lim n→∞ nv r,µ (n) can be explicitly computed by the rth iterate of a function g evaluated in (µ -r) 2 /2.

Restricting the set of possible strategies

Let X 1 , X 2 , • • • , X n be i.i.d. uniform random variables on [0, 1] defined on (Ω, F, P ), and let, as before, I k be the indicator of the event that X k is selected. A closer analysis of the problem as stated in (1.1)- (1.4) shows that the E-constraint raises some questions which may be difficult to answer. (The author is indebted to the referee for drawing his attention to this point.) To indicate possible problems and to add something possibly new to the referee's discussion we consider the case r = 0. Then the problem becomes that of finding the minimal expected cost under the pure E-constraint

E n k=1 I k = n k=1 P (I k = 1) ≥ µ.
A frequentist may justifiably argue that the only way to verify that a given strategy fulfills this constraint is to apply it to a sequence of identical games, that is, to apply it consecutively to m blocks of n i.i.d.

U [0, 1]-random variables (X j 1 , X j 2 , • • • , X j n ) j=1,2,••• ,m
and to check whether for m → ∞ the lim inf of the arithmetic mean of the number of selections per block is at least µ. This raises the question whether a good strategy may allow to select in certain blocks many more observations than necessary -for instance if there is an opportunity to collect them cheaply -in order to compensate for other blocks where one may prefer a particular small value of the loss and select nothing.

Note that the problem stays the same for general r ∈ N, r > 0, because, inherently, any admissible strategy must end up in a random index k, at which the D-constraint becomes void. The author does not claim that the problem is, for such reasons, ill-posed, but he does not see how to make things precise to affirm, that an optimal strategy for (1.1)-( 1.4) must always exist. We therefore confine the study to the set of strategies in which the "memory" of the indicators {I k } k=1,2,...,n is just sufficient to guarantee admissibility of the applied strategy at each instant. In this vein, let

S n = σ = (I 1 , I 2 , • • • , I n ) : I k may depend on X k , n -k and N k-1 , (2.1)
where

N k = I 1 + I 2 + • • • + I k . (2.2)
Our objective is to find the value

v r,µ (n) := min σ∈Sn E n k=1 I k X k , n ≥ µ ≥ r, r, n ∈ N, (2.3)
and the corresponding selection rule

σ r,µ (n) = argmin σ∈Sn E n k=1 I k X k (2.4) achieving this value subject to the D-constraint N n ≥ r and the E-constraint E(N n ) ≥ µ.

Difference between D-constraint and E-constraint

We have already pointed out that the E-constraint needs special attention. It is quite different in nature from the D-constraint for which no ambiguity is possible. But the difference should also give something new, of course. We therefore allow that, once the D-constraint is satisfied under a given selection rule the reduced E-constraint is no longer sequentially updated in order to just achieve a minimum of µ -r more selections. Otherwise the mixed constraints setting would be equivalent to a D-constraint of µ , where x denotes the ceiling of x. This, however, would be the same case as the case where r = µ which is already covered through our model with the E-constraint being the same as the D-constraint. Therefore it is more general to allow that once the D-constraint is satisfied, the Problem becomes the problem of minimizing additional cost imposed by a pure E-constraint of µ -r. Hence we can continue from that moment onwards with any (memoryless) strategy which selects, in expectation, µ -r items.

3 Existence and structure of the optimal strategy Our way of attacking the existence of a solution to problem (2.1)-(2.4) benefits from two properties which simplify the problem essentially. The first flows out of the i.i.d. assumption for the X k 's, namely:

Lemma 3.1 Let V 0 (n) = v r,µ (n) and let V (n|H k ) denote the conditional minimal total cost expectation over all strategies in S n given the history H k = {(X 1 , I 1 ), (X 2 , I 2 ), • • • (X k , I k )}. If v r-N k ,µ-N k (n -k) exists for 0 ≤ N k ≤ r, then we must have V (n|H k ) = v r-N k ,µ-N k (n -k) + k j=1 I j X j a.s.
(3.1)

Proof: : Since the objective function (total cost of selection) is linear in each term (see (2.3)), the optimal strategy from time k + 1 onwards must be optimal continuation in S n after time k, given H k . The latter is subject to the D-constraint r -N k and the E-constraint µ -N k . Note that

N k = I 1 + • • • + I k is deter- mined by H k . Since, by definition, the forthcoming random variables X k+1 , • • • , X n are independent of (X 1 , I 1 ), • • • , (X k , I k ), and since (X k+1 , • • • , X n ) is distributed like (X 1 , • • • , X n-k
), the corresponding decision process is Markovian, that is, the value of the optimal continuation cannot depend but on

X k , X k+1 , • • • , X n , on n -k and on N k . The optimal loss increment is therefore v r-N k ,µ-N k (n -k)
whereas the currently accumulated cost is k j=1 I j X j a.s. Hence Lemma 3.1 is proved. 2

The next Lemma confirms our intuition that (3.1) holds also if we replace the fixed index k by the stopping time defined by the first time instant in which the D-constraint is completely satisfied. Lemma 3.2 For given n, let δ be the smallest time at which the D-constraint is completely satisfied under application of the S n -optimal strategy. Then,

V δ (n) = v 0,µ-r (n -δ) + δ j=1 I j X j a.s. (3.2) where v 0,µ-r (k) = (µ -r) 2 2k . (3.3) Proof: Conditioned on δ = d, statement (3.
2) follows from Lemma 3.1 because the optimal rule in S n , σ say, must be admissible. Admissibility also implies that δ satisfies the condition r ≤ δ ≤ n -µ + r.

At time δ, the future variables

X δ+1 , • • • , X n are independent of X 1 , • • • , X δ .
Hence, the first statement is bound to hold unconditionally. It remains to be shown that v 0,µ-r (k) = (µ -r) 2 /2k. At time δ+, with K = n -δ observations to come, the D-constraint vanishes. We are thus confronted with the task of designing a rule which selects in expectation µ -r more items from K i.i.d U [0, 1]-random variables. Now, the pure E-constraint concerns solely the expected number of selections and not their values. These values just intervene in the optimal cost. Hence, if it is optimal to select, for j > δ, a value X j = x, say, then it is optimal to accept any X j < x, because it is cheaper paying X j than paying x. Similarly, if it is optimal to refuse X j = x, it must be optimal to refuse any X j with X j > x. It follows that each optimal decision at time j is based on a unique threshold value. This is just the indifference-value with respect to an S n -optimal strategy on the remaining sequence

X j , X j+1 , • • • , X n . Let now t 1 , t 2 , • • • , t K be the selection thresholds for X δ+1 , X δ+2 , • • • , X n
, respectively, that is, we select X δ+j if and only if X δ+j ≤ t j . We can clearly confine our interest to threshold values between 0 and 1. Then

E(I δ+j X δ+j ) = 1 0 1{x ≤ t j }xdx = t 2 j 2 . (3.4)
Equations (3.2) and (3.4) imply that we have to minimize

K j=1 t 2 j subject to the constraint K j=1 E(I δ+j ) = K j=1 t j ≥ µ -r.
Note that for all K the E-constraint can here be replaced by

K j=1 t j = µ -r, (3.5)
since all t j are non-negative. It is now straightforward to show by the Lagrange multiplier method that the optimal thresholds are constant with t j = (µ -r)/K. Hence

v 0,µ-r (K) = K µ -r K µ -r 2K = (µ -r) 2 2K , implying (3.
3). This completes the proof of Lemma 3.2. 2

Existence of an Optimal Strategy

We now are ready to prove the existence of an optimal strategy in S n . We proceed in two steps. The first step is based on the following facts: Given the decision process enters the constraints-state (0, µ -r) at time δ, the optimal future expected cost is, as we have just seen, the unique value v 0,µ (n -δ), which is independent of X 1 , X 2 , • • • , X δ . Then the idea is to look backwards to the first time the decision process enters the constraints-state (1, µ -r + 1). As we shall show below, the threshold argument used before will go through similarly. Using the independence of the X k 's it follows that the S n -optimal future loss from that time onwards is just a function of unique threshold values for the next selection and the optimal expected cost increment v 0,µ (n -δ). Hence v 1,µ-r+1 (k) must exist, and the strategy to achieve this value is again unique. By induction, this argument will yield the recursive structure of the optimization problem in S n .

We now give the details:

Theorem 3.1 Let, as before, v r,µ (n) denote the value for the problem with D-constraint r and E-constraint µ ≥ r for n observations. Then, for µ ≥ r ≥ 1 the v r,µ (n) must satisfy the (double) recursion

v r,µ (n) = v r,µ (n -1) - 1 2 [v r,µ (n -1) -v r-1,µ-1 (n -1)] 2 , (3.6) for n = µ +, µ + 1, • • • , with initial conditions v r,µ ( µ ) = µ 2 ; v 0,µ-r (n) = (µ -r) 2 2n , n = 1, 2, • • • . (3.7)
Proof: Suppose we follow the strategy to select X 1 if and only if X 1 ≤ t and to continue optimally thereafter until the end. Then our value becomes ṽr,µ (n, t), say, and we see that this value must satisfy the optimality equation

ṽr,µ (n, t) = t E (X|X ≤ t) + v r-1,µ-1 (n -1) + (1 -t)v r,µ (n -1). (3.8)
Indeed, according to (3.1) we obtain, if we select X 1 , the loss E(X|X ≤ t) as instantaneous loss plus the optimal loss increment thereafter. The latter is simply

v r-1,µ-1 (n -1) because (I 2 , I 3 , • • • , I n ) may depend on X 1 only through N 1 , that is only through I 1 .
If we refuse X 1 the optimal loss increment for the following n -1 observations is similarly v r,µ (n -1). Using E(X|X ≤ t) = t/2, the rhs of (3.8) is clearly differentiable in t for all t ∈]0, 1[, so that the solution of equation ∂ṽ r,µ (n, t)/∂t = 0 with ∂ 2 ṽr,µ (n, t)/∂t 2 > 0 minimizes ṽr,µ (n, t). It is straightforward to see that this unique solution t * is given by

t * = v r,µ (n -1) -v r-1,µ-1 (n -1). (3.9)
There is no other candidate strategy for minimizing the expected future cost in S n so that we must have ṽr,µ (n, t * ) = v r,µ (n). Using this fact together with the solution (3.9) in equation (3.6) yields, after some elementary transformations, the recursion equation (3.6) of Theorem 3.1.

To see the initial conditions (3.7), suppose first that µ ∈ N and n = µ. Then, after r compulsory selections, the remaining µ -r E-constrained selections are also compulsory. Hence the optimal policy must select all observations, and has therefore value µ/2. If µ -r ∈ N the result turns out the same, because with {x} denoting the fractional part of x and x the floor of x, the E-constraint imposes ( µr ) + {µ/2} selections on its own, and hence the value is r/2 + µ -r /2 + {µ/2} = µ/2. Finally, the second initial condition follows from equation (3.5), and thus the Theorem is proved. 2

Remark 3.1 It is important to note that in this (Bellman-type) optimality equation the restriction to strategies in the set S n is, a priori, not redundant. The optimal future loss depends on (X 2 , I 2 ), (X 3 , I 3 ), . . . , (X n , I n ) and on the knowledge of N 1 . Dependence on X 1 is therefore limited to the dependence on I 1 = 1{X 1 ≤ t}. This is why the future optimal expected losses figuring in (3.8) are v r-1,µ-1 (n -1) and v r,µ (n -1), respectively, with an expected reduction of the E-constraint from µ to µ -t with 0 ≤ t ≤ 1 ≤ µ. There are several reasons why the author believes that S n must contain the overall optimal strategy. He has no rigorous proof, however, and must leave it here as a conjecture.

To describe the optimal rule we introduce the notion of a state of the selection process:

Definition 3.1 For ρ ∈ {0, 1, • • • , r} and k ∈ {0, 1, • • • , n}
we say that the selection process is in state (ρ, k), if ρ selections have been made until time n-k included, that is, with k further unobserved variables to come.

Note that the current E-constraint is implicit for 0 ≤ ρ ≤ r. Since the continuation thereafter is, by hypothesis, a fixed selection rule, it becomes irrelevant once the D-constraint is satisfied. Hence we need not list it as a separate state-coordinate. From the uniqueness of the optimal thresholds (see (3.9)) and Theorem 6.1 we have then the following corollary.

Corollary 3.1 (Optimal selection strategy) The optimal selection strategy σ r,µ (n) is a state-dependent threshold selection rule, that is, for each state

(ρ, k) ∈ {0, 1, • • • , r} × {0, 1, • • • , n}
there exists a unique value t ρ,k such that it is optimal to select X n-k+1 if X n-k+1 ≤ t ρ,k , and to refuse X n-k+1 otherwise. These optimal thresholds are given by

t(ρ, k) := t r,µ (ρ, k) = v r-ρ,µ-ρ (k -1) -v r-ρ-1,µ-ρ-1 (k -1).
(3.10)

4 Elementary monotonicity properties of v r,µ (n)

For all r ∈ N and µ ≥ r, the values v r,µ (n) are positive by definition. Before giving in Section 5. the algorithm to implement the optimal rule σ r,µ (n) and the optimal loss v r,µ (n) we collect elementary properties of v r,µ (n) which will be used in Sections 5. and Section 6. We see from (3.6) in Theorem 3.1 that the sequence (v r,µ (n)) decreases in n whenever the sequence (v r-1,µ-1 (n)) decreases in n. According to (3.7) we know that (v 0,µ-r (n)) decreases in n and thus, as it is bounded below by 0, it must converge to the only possible limit 0. Hence we have by induction:

Corollary 4.1 For all µ ≥ 1 and all integers r, n with n ≥ µ ≥ r the sequence (v r,µ (n)) n≥µ is monotone decreasing with limit 0. This is the monotonicity of v r,µ (n) with respect to the number n of observations. As we shall see now, v is, for fixed n, also monotone with respect to the both constraints. Note that a reduction of the D-constraint from r to r -1 goes, by definition, together with a reduction of the E-constraint from µ to µ-1 (whereas the converse is not true.) The following lemma compares the values in different constraints for the same number of future observations: Lemma 4.1 For n fixed with n ≥ [µ] + and µ ≥ r we have

v r,µ (n) ≥ v r-1,µ-1 (n) (4.1) and v r,µ (n) ≥ v r,µ-1 (n). ( 4

.2)

Proof: To see inequality (4.1), let v h µ,r (n) be the minimal expected total cost of the optimal strategy for the (r, µ)-constraint under the additional hypothesis that we will get, as a bonus, the rth selection for free. Then

v h µ,r (n) ≤ v µ,r (n) (4.3)
because the total cost cannot but decrease by the bonus. However if we play right away optimally under the weaker (r -1, µ -1)-constraint, then we take the minimum expected value over an extended set of strategies: Indeed, the latter covers both the set of strategies for r compulsory selections with the bonus of a free rth selection and those which may forego one selection. Therefore v r-1,µ-1 (n) ≤ v h r,µ (n), and hence, taking both inequalities together, v r,µ (n) ≥ v r-1,µ-1 . This proves (4.1). Inequality (4.2) follows from the second inequality in (3.7) because v 0,µ-r (.) > v 0,µ-1-r (.) uniformly. 2 constant α. Now, the optimal strategy to fulfill the (r, r)-constraints cannot do better than selecting the r items of minimum total cost, that is all r smallest order statistics. The expectation of the sum of these is

1 n + 1 + 2 n + 1 + • • • + r n + 1 = r(r + 1) 2(n + 1) ,
and is thus greater than r 2 /(2n).

Hence v r,µ (n) ≥ v r,r (n) ≥ α/n for α = r 2 /2.
Concerning the upper bound β we see (now from from Corollary 5.1) that the statement is true, if it is true for v r,r (n). To see the latter we note that v r,r (rn

) ≤ v r-1,r-1 ((r -1)n) + v 1,1 (n)
, and hence by induction v r,r (rn)) ≤ rv 1,1 (n).

(5.4)

The sequence (v 1,1 (n)) coincides with Moser's sequence, which is known to satisfy v 1,1 (n) ≤ 2/n for all n. Therefore v r,r (rn)) ≤ (2r)/n. But then, for general n we have v r,r (n) ≤ v r,r ( n/r ), where x denotes the floor of x. Hence

v r,r (n) ≤ 2r n/r ≤ 2r 2 + n
for all > 0 and n sufficiently large, and thus the proof is complete. 2

We can now complete Example 5.1. Recall

y k = kv(k) where v(k) = v 1,2 (k) for k = 2, 3, • • • . It follows from Lemma 5.2 that (y k
) is bounded by some positive constants α and β. Hence, to show that y = lim y k exists it suffices to show that y k is monotone for all k sufficiently large. Replacing k by k + 1 in equation (5.1) and multiplying this equation then by k yields after some elementary transformations

y k+1 -y k = v(k + 1) - k 2 v(k) - 1 2k 2 , (5.5)
so that it suffices to show that the rhs does not change signs for k sufficiently large. Indeed, it is always positive for all k ≥ 2, as A. Dutrifoy (private communication) has shown by a skillful direct estimation. However, we do not give his proof here because we give below an independent and purely probabilistic proof of the more general result that nv r,µ (n) is increasing in n. Indeed, this monotonicity is true for all r ∈ N, µ ≥ r and all n ≥ µ . Hence we know that y = lim n y(n) exists, so that we can eliminate y in the limiting equation and pass on to take limits again. This yields in terms of y the new limit equation y = (1/2)(y -1/2) 2 with solutions 3/2 ± √ 2. Since y n ≥ 1 for all n ≥ 2, and hence y ≥ 1, we can exclude the smaller root, and therefore y = 3/2 + √ 2.

Approximation of general solution

We now prove the important result, that nv r,µ (n) converges for all r ∈ N and all µ ≥ r to a limit c(r, µ) which we can compute explicitly. Hence v r,µ (n) ∼ c(r, µ)/n. This will be done in several steps.

Monotonicity

Lemma 6.1 For all r ∈ N and µ ≥ r the sequence (n v r,µ (n)) n≥µ,n∈N is increasing in n.

Proof: In order to prove the statement of the Lemma we have to show that

v r,µ (n) ≥ n -1 n v r,µ (n -1), for n ≥ µ + 1, n ∈ N. (6.1)
To see this we use a refinement of the "half-prophet"-trick of Bruss and Ferguson. See (Bruss and Ferguson, 1993, Theorem 2, pp 623-624). Imagine a decision maker, H say, which has some "halfprophetical" capacity in the sense that he or she can predict beforehand the largest of the n outcomes, that is

M n = max{X 1 , X 2 , • • • , X n }.
Suppose now that H wants to minimize, exactly as we do, the expected total selection cost under the (r, µ)-constraint over the set of strategies S n . Then H can use at least all the admissible strategies we can use, so that his or her minimal expected total cost, h r,µ (n) say, must satisfy

h r,µ (n) ≤ v r,µ (n), for n ≥ µ. ( 6
, U 2 , • • • , U n-1 } be the (unordered) set of the n -1 smallest order statistics of the sample{X 1 , X 2 , • • • , X n }, and let X k = X k /M n for these 1 ≤ k ≤ n -1.
Since the X k s are again i.i.d and uniform on [0, 1], and since there is a one-to-one correspondence between the U k 's and the X k 's, an optimal strategy forces H to select (respectively, refuse) U k whenever optimal behavior would force us to accept (respectively, refuse) X k . Our optimal value (that is our optimal total expected selection cost) for this selection problem is by definition v r,µ (n -1) because it suffices to replace in equation ( 2.3) the number n by n -1.

Now, using the tower property of conditional expectations in (2.3) we have

v r,µ (n) = min (I1,••• ,In)∈Sn E E n k=1 I k X k M n , n ≥ µ ≥ r, r, n ∈ N. (6.3)
This is our optimal value whereas H, knowing M n , can replace the conditional expectation (6.3) by the simple expectation taken on the sum of the I k U k . Hence, given M n = x, the corresponding optimal value for H reduces by definition of the U k 's to xv r,µ (n -1). If we denote the conditional value for H given M n by h r,µ (n | M n ) and the density of M n by f Mn then we get accordingly for x ∈ [0, 1]

f Mn (x)h r,µ (n | M n = x) = xf Mn (x)v r,µ (n -1). (6.4)
Since the density of M n is given by f Mn (x) = nx n-1 , integrating out this equation yields the identity

h r,µ (n) = 1 0 nx n v r,µ (n -1)dx = n n + 1 v r,µ (n -1). (6.5)
Using (6.2) we get from (6.5)

v r,µ (n) ≥ h r,µ (n) = n n + 1 v r,µ (n -1) ≥ n -1 n v r,µ (n -1)
which is (6.1), and the proof is complete.

2 c 1 = 1 + c + √ 1 + 2c
is meaningful for our problem. Indeed, with c being strictly positive, we would obtain 1+c-√ 1 + 2c < c otherwise. This, however, would contradict w(t) ≥ ṽ(t) which we must require in order to stay compatible with the general inequality v r,µ (n) ≥ v r-1,µ-1 (n) (see (4.1)). This shows that w1 (t) is a particular solution of (6.7).

From the general theory of Riccati differential equations (see e.g. (H. Grauert und W. Fischer , 1968, pp.109-112)) we know that we can now generate a general solution { w2 } from a particular solution by solving (substitution u(t) = 1/(w 2 (t) -w 1 (t)) the first order linear equation

u (t) = -(Q(t) + 2R(t) w1 (t))u(t) -R(t)
where, in our case, R(t) = -1/2 and Q(t) = c/t. The set { w2 } of solutions is then the set { w2 (t) = w1 (t) + u(t) -1 } with a single undetermined constant. Plugging our particular solution w1 (t) into the first order equation yields, after straightforward simplification, the equation u

(t) = u(t) 1 + √ 1 + 2c /t + 1 2
. We solve its associated homogeneous equation and then apply the method of the variation of constants.

Using this yields after re-substitution (including an independent check by Mathematica) that all solutions which are compatible with the monotonicity of v r,µ (n) (decreasing) and the monotonicity of nv r,µ (n) (increasing) lie in the class

S = c t - 1 t -1 + √ 1 + 2c -1 + 2κ t √ 1+2c + κ : κ ∈ R .
Note that for all s ∈ S we have the asymptotic relationship

s(t) ∼ 1 t 1 + c + √ 1 + 2c = w(t) (6.9)
as t → ∞, and hence the proof. 2

Since we have indeed identified the only possible limiting behavior of nv r,µ (n), and thus its correct limiting behavior, our main result Theorem 6.2 will now easily follow by induction. Theorem 6.2 Let g : R + → R + and g r be defined by

(i) g(x) = 1 + x + √ 1 + 2x (ii) g 0 (x) = g(x); g r (x) = g (g r-1 (x)) for r ∈ N.
Then for all r ∈ N and µ ∈ R, µ ≥ r,

L(r, µ) := lim n→∞ n v r,µ (n) = g r (µ -r) 2 2 .
Proof: Let w(t) = v 1,µ-r+1 (t) and ṽ(t) = v 0,µ-r (t). Recall from Lemma 3.2 that v 0,µ-r (t) = (µr) 2 /(2t) so that from equation (6.7)

dv 1,µ-r+1 (t) dt = - 1 2 v 1,µ-r+1 - (µ -r) 2 2t
2 (6.10) and thus from (6.8) (6.11) where c 0 = (µ -r) 2 /2. Renaming successively w(t) = v 1,µ-r+1 (t), v 2,µ-r+2 (t), • • • and ṽ(t) = v 0,µ-r (t), v 1,µ-r+1 (t), • • • we get by induction according to (6.8) and (6.9) v r,µ (t) ∼ c r t and c r := g(c r-1 ) (6.12)

v 1,µ-r+1 (t) ∼ 1 + c 0 + √ 1 + 2c 0 t =: c 1 t ,
where g(x) = 1 + x + √ 1 + 2x. From Corollary 6.1 and Theorem 6.1 the function g in (6.12) is unique. Hence L(r, µ) = lim t→∞ tv r,µ (t) = c r = g r (µ -r) 2 2 (6.13) and Theorem 6.2 is proved. 2

Cost comparison for D-constraint and E-constraint

It seems interesting to compare the normalized limiting costs L(r, µ) = lim t→∞ tv r,µ (t) for different r and µ. It is somewhat intuitive that the D-constraint is "more costly" than the E-constraint. One feels that one has always an advantage if one is not forced to select an observation. This is true and best understood if we fix µ (integer, say) and then compare the values L(1, µ), L(2, µ), • • • , L(µ, µ). They are increasing in r, as we know already, and indeed by increasing increments, as one can easily show (see also Table 1 below). Hence this part of our intuition is correct. Now we may wonder whether it is cheaper to move the D-constraint up by one and keep µ fixed, or is it cheaper vice versa? (Here, as always, it is understood that the D-constraint may not strictly exceed µ.) Our feeling is now that the answer should depend on how r relates to µ: If µ is large and also much larger than r, then it is intuitive that a change from (r, µ) to (r + 1, µ) should increase the normalized limiting cost relatively little. We may reason by a law of large numbers argument that even the pure E-constraint problem (that is, the problem for (0, µ)) would lead, with a probability close to one to a sufficiently large number of selections covering r or r + 1 all the like. This intuition (also visible in Table 1) is again true, as one can generally show using the properties of the function g and its iterates g k defined in Theorem 6.2. The remaining question is, whether there are some surprises if r gets close to µ. More precisely, is it is possible that the normalized limiting cost does not change if we move from a mixed constraint (r, µ) to (r -k, µ + k) for some k ∈ N. The answer is that it may coincide. However, there is only exactly one non-trivial case (i.e. k > 0) where the values coincide, which is the case r = µ and k = 1 as we shall now prove.

Propostion 6.1 L(r -1, r + 1) = L(r, r). (6.14)

Furthermore, this is the only equality of the form L(r, µ) = L(r -k, µ + k) which can hold for 1 ≤ k ≤ µ.

Proof: Recall that L(r, µ) = g r ((µ -r) 2 /2) where g(x) = 1 + x + √ 1 + 2x. Hence L(r -1, r + 1) = g r-1 (2 2 /2) = g r-1 (2). Similarly we obtain L(r, r) = g r (0). Now note that g(0) = 2 so that L(r, r) = g r (0) = g r-1 (g(0)) = g r-1 (2) = L(r -1, r + 1).

(6.15)

  u r,µ (n) = min (I1,••• ,In)∈Tn E n k=1 I k X k , n ≥ µ ≥ r, r, n ∈ N (1.1)and the corresponding selection rule τ r,µ (n) = argmin τ ∈Tn E

  .2) It follows from the i.i.d. assumption for the uniform [0, 1]random variables X k that conditioned onM n = x all X k 's other than M n are i.i.d. uniform random variables on [0, x].Now suppose that H has no further prophetical capacities apart from the gift of being able to foresee M n . Then, as we shall see, H has exactly the same type of optimization problem as we would have for n -1 i.i.d. uniform random variables on [0, 1]. Indeed, let {U 1

Acknowledgements

The author's instigation to do research on this problem is due to a question of David Aldous whose insight in our initial discussions was very helpful. Further, the author thanks Freddy Delbaen and Alexandre Dutrifoy for their interest in this problem and their comments. Special thanks go to the referee whose remarks lead to a better presentation of this paper.

Computing optimal thresholds and values

The optimal thresholds for each state can be computed recursively via the state dependent future values for k observations to come.

We have to start with the optimal values for which we have two independent lines of initial conditions, namely for v 0,µ-r (k) with k ≥ µ -r and for v s,k (k) with k ≥ s. The first one stems from the corresponding optimal memoryless threshold rule (see (3.3) in Lemma 3.2). The second one is even easier, because if k ≥ s and if we have to satisfy the E-constraint and D-constraint at the same time, we must accept all observations to come. These figure as (A1) and (A2) in part A of the algorithm below and are used in the recursion (A3). Part B below computes the optimal thresholds using A.

The algorithm

Algorithm 1: Compute the optimal strategy and the optimal value A Optimal values:

where

Example 5.1

As an example we solve the problem for r = 1 and µ = 2 (Aldous' problem). We have µ -r = 1 and hence from (3.3) the equation v 0,1 (k) = 1/(2k). Moreover the initial condition for v 1,2 (2) = 1 is evident, since any admissible rule must accept both observations. Hence, using (3.6),

with initial condition v(2) = 1. The sequence (v(n)) is clearly decreasing and bounded below by 0. Hence v = lim v(n) exists and taking limits shows v = 0. Aldous' question concerned the limit y of (y n ) where y(n) = nv(n)). As the next section will show, this limit exists and equals 3/2 + √ 2. Hence

(5.2)

5.2 Bounds of v r,µ (n) for general r and µ

The motivation of the following simple lemma is to obtain bounds for the values v r,µ (n) in terms of values stemming from simple recursions. The following result is intuitive and easy to prove:

Proof: Fix indices ρ, m and k such that the conditions for the Lemma are fulfilled. This is always possible since the set of such triples (ρ, m, k) contains at least the trivial triples (r, µ, n) and (0, 0, 0) for which the statement holds by definition. More generally, consider a two-legged strategy. Leg 1 minimizes the expected total cost of accepting items until time k under the D-constraint ρ and the E-constraint m.

The continuation leg 2 remembers the occurred cost at time k and then minimizes (independently) the additional cost of accepting further items under the D-constraint r -ρ and the E-constraint µ -m. This composed strategy is admissible since it fulfills the original constraints, and since

The inequality follows then by sub-optimality. 2

For the special case ρ = r = m we obtain then from equality (3.6) and Lemma 5.1:

Lemma 5.1 and Corollary 5.1 have an important consequence (Lemma 5.2) which will make the asymptotic approach in Section 6 rigorous: Lemma 5.2 For all 1 ≤ r ≤ µ there exist constants α = α(r, µ) and β = β(r, µ) such that

for all n ≥ µ, with n sufficiently large.

Proof: We first prove the lower bound α(r, µ)/n. By definition of the D-constraint and E-constraint we have µ ≥ r. Since, moreover, v r,µ (•) is nondecreasing in µ, for fixed r and n (see inequality (4.2)), it suffices to show v r,r (n) ≥ α/n for some Corollary 6.1 (nv r,µ (n)) n ≥µ, n∈N converges for all r ∈ N, µ ≥ r.

Proof: We know from Lemma 5.2 that, for all r ∈ N, µ ≥ r there exists a constant β(r, µ) such that v r,µ (n) ≤ β(r, µ)/n. Hence nv r,µ (n) is bounded. Convergence follows thus immediately from Lemma 6.1. 2

6.2 Asymptotic behavior of nv r,µ (n)

We are now ready to tackle the problem of how to compute lim n→∞ n v r,µ (n). Corollaries 3.1 and 6.1 justify trying to replace the difference equations determining v r,µ (n) by a differential equation, and this approach will indeed be successful. We rewrite (3.6) for t ∈ N and δt = 1 as

with initial condition (3.7). We fix r and µ and can then simplify the notation by writing v r-1,µ-1 (t) =: v(t) and v r,µ (t) =: w(t), say. Let ṽ(t) and w(t) be differentiable functions which coincide with v(t) and w(t) for t ∈ N with t ≥ µ. It follows from Corollary 3.1 and Corollary 6.1 that the differential equation

2 (6.7) defined for t ∈ [µ, ∞] must (provided that we can solve it) catch the asymptotic behavior of both w(t) and tw(t). Note that equation (6.7) is a general Riccati differential equation. The idea is now to use our results on nv r,µ (n) in order to show that only one class of solutions of equation (6.6) is compatible with the established properties of v r,µ (n), and then that, within this class, all solutions are asymptotically equivalent.

Theorem 6.1 If ṽ(t) = c/t for some constant c ≥ 2 then the only solutions w(t) of equation ( 15) satisfying lim t→∞ v r,µ (t)/ w(t) = 1 are those functions which are asymptotically equivalent to

Proof: We first prove that the function

is a particular solution of equation (6.7). Indeed, there must exist a constant, c 1 say, such that c 1 /t is a particular solution, because plugging this into (6.7) yields a simple quadratic equation in c 1 . We get the equation

with the two solutions {1 + c ± √ 1 + 2c}. We now show that only the solution


Vida Dujmović

David R Wood
email: woodd@unimelb.edu.au

On the Book Thickness of k-Trees

Keywords: 05C62, 68R10 graph, book embedding, book thickness, pagenumber, stacknumber, treewidth, tree decomposition

Every k-tree has book thickness at most k + 1, and this bound is best possible for all k ≥ 3. Vandenbussche et al. [SIAM J. Discrete Math., 2009] proved that every k-tree that has a smooth degree-3 tree decomposition with width k has book thickness at most k. We prove this result is best possible for k ≥ 4, by constructing a k-tree with book thickness k + 1 that has a smooth degree-4 tree decomposition with width k. This solves an open problem of Vandenbussche et al.

Introduction

Consider a drawing of a graph (i) G in which the vertices are represented by distinct points on a circle in the plane, and each edge is a chord of the circle between the corresponding points. Suppose that each edge is assigned one of k colours such that crossing edges receive distinct colours. This structure is called a kpage book embedding of G: one can also think of the vertices as being ordered along the spine of a book, and the edges that receive the same colour being drawn on a single page of the book without crossings. The book thickness of G, denoted by bt(G), is the minimum integer k for which there is a k-page book embedding of G. Book embeddings, first defined by [START_REF] Ollmann | On the book thicknesses of various graphs[END_REF], are ubiquitous structures with a variety of applications; see [START_REF] Dujmović | On linear layouts of graphs[END_REF]) for a survey with over 50 references. A book embedding is also called a stack layout, and book thickness is also called stacknumber, pagenumber and fixed outerthickness.

This paper focuses on the book thickness of k-trees.

A vertex v in a graph G is k-simplicial if its neighbourhood, N G (v), is a k-clique. For k ≥ 1, a k-tree is a graph G such that either G K k+1 , or G has a k-simplicial vertex v and G -v is a k-tree. In the latter case, we say that G is obtained from G -v by adding v onto the k-clique N G (v).
What is the maximum book thickness of a k-tree? Observe that 1-trees are precisely the trees. [START_REF] Bernhart | The book thickness of a graph[END_REF] proved that every 1-tree has a 1-page book embedding. In fact, a graph has a 1-page book embedding if and only if it is outerplanar [START_REF] Bernhart | The book thickness of a graph[END_REF]. 2-trees are the edge-maximal series-parallel graphs. [START_REF] Rengarajan | Stack and queue number of 2-trees[END_REF] proved that every series parallel graph, and thus every 2-tree, has a 2-page book embedding (also see [START_REF] Di Giacomo | Book embeddability of series-parallel digraphs[END_REF]). This bound is best possible, since K 2,3 is series parallel and is not outerplanar. [START_REF] Ganley | The pagenumber of k-trees is O(k)[END_REF] proved that every k-tree has a (k +1)-page book embedding; see [START_REF] Dujmović | Graph treewidth and geometric thickness parameters[END_REF] for an alternative proof. [START_REF] Ganley | The pagenumber of k-trees is O(k)[END_REF] also conjectured that every k-tree has a k-page book embedding. This conjecture was refuted by [START_REF] Dujmović | Graph treewidth and geometric thickness parameters[END_REF], who constructed a k-tree with book thickness k + 1 for all k ≥ 3. [START_REF] Vandenbussche | On the pagenumber of k-trees[END_REF] independently proved the same result. Therefore the maximum book thickness of a k-tree is k for k ≤ 2 and is k + 1 for k ≥ 3.

Which families of k-trees have k-page book embeddings? [START_REF] Togasaki | Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs[END_REF] proved that every graph with pathwidth k has a k-page book embedding (and there are graphs with pathwidth k and book thickness k). This result is equivalent to saying that every k-tree that has a smooth degree-2 tree decomposition (ii) of width k has a k-page book embedding. [START_REF] Vandenbussche | On the pagenumber of k-trees[END_REF] extended this result by showing that every k-tree that has a smooth degree-3 tree decomposition of width k has a k-page book embedding. [START_REF] Vandenbussche | On the pagenumber of k-trees[END_REF] then introduced the following natural definition. Let m(k) be the maximum integer d such that every k-tree that has a smooth degree-d tree decomposition of width k has a k-page book embedding. [START_REF] Vandenbussche | On the pagenumber of k-trees[END_REF] proved that 3 ≤ m(k) ≤ k + 1, and state that determining m(k) is an open problem. However, it is easily seen that the k-tree with book thickness k + 1 constructed in [START_REF] Dujmović | Graph treewidth and geometric thickness parameters[END_REF] has a smooth degree-5 tree decomposition with width k. Thus m(k) ≤ 4 for all k ≥ 3. The main result of this note is to refine the construction in [START_REF] Dujmović | Graph treewidth and geometric thickness parameters[END_REF] to give a k-tree with book thickness k + 1 that has a smooth degree-4 tree decomposition with width k for all k ≥ 4. This proves that m(k) = 3 for all k ≥ 4. It is open whether m(3) = 3 or 4. We conjecture that m(3) = 3.

Construction

Theorem 1 For all k ≥ 4 and n ≥ 11(2k 2 +1)+k, there is an n-vertex k-tree Q, such that bt(Q) = k+1 and Q has a smooth degree-4 tree decomposition of width k.

Proof: Start with the complete split graph K k,2k 2 +1 . That is, K k,2k 2 +1 is the k-tree obtained by adding a set S of 2k 2 + 1 vertices onto a k-clique K = {u 1 , u 2 , . . . , u k }, as illustrated in Figure 1. For each vertex v ∈ S add a vertex onto the k-clique (K ∪ {v}) \ {u 1 }. Let T be the set of vertices added in this step. For each w ∈ T , if v is the neighbour of w in S, then add a set T 2 (w) of three simplicial vertices onto the k-clique (K ∪ {v, w}) \ {u 1 , u 2 }, add a set T 3 (w) of three simplicial vertices onto the k-clique (K ∪ {v, w}) \ {u 1 , u 3 }, and add a set T 4 (w) of three simplicial vertices onto the k-clique

(K ∪ {v, w}) \ {u 1 , u 4 }. This step is well defined since k ≥ 4. For each w ∈ T , let T (w) := T 2 (w) ∪ T 3 (w) ∪ T 4 (w).
By construction, Q is a k-tree, and as illustrated in Figure 2, Q has a smooth degree-4 tree decomposition of width k.

(ii) See [START_REF] Diestel | Graph theory[END_REF] for the definition of tree decomposition and treewidth. Note that k-trees are the edge maximal graphs with treewidth k. A tree decomposition of width k is smooth if every bag has size exactly k + 1 and any two adjacent bags have exactly k vertices in common. Any tree decomposition of a graph G can be converted into a smooth tree decomposition of G with the same width. A tree decomposition is degree-d if the host tree has maximum degree at most d.

K S

Fig. 1: The complete split graph K 4,|S| . It remains to prove that bt(Q) ≥ k + 1. Suppose, for the sake of contradiction, that Q has a k-page book embedding. Say the edge colours are 1, 2, . . . , k. For each ordered pair of vertices v, w ∈ V (Q), let vw be the list of vertices in clockwise order from v to w (not including v and w).

K + v 1 K + v 2 K + v i K + v |S|-1 K + v |S| K + v i -u 1 + w i K + v i -u 1 + w i -u 2 + * K + v i -u 1 + w i -u 2 + * K + v i -u 1 + w i -u 2 + * K + v i -u 1 + w i -u 3 + * K + v i -u 1 + w i -u 3 + * K + v i -u 1 + w i -u 3 + * K + v i -u 1 + w i -u 4 + * K + v i -u 1 + w i -u 4 + * K + v i -u 1 + w i -u 4 + *
Say K = (u 1 , u 2 , . . . , u k ) in anticlockwise order. Since there are 2k 2 + 1 vertices in S, by the pigeonhole principle, without loss of generality, there are at least 2k + 1 vertices in

S ∩ u 1 u k . Let (v 1 , v 2 , . . . , v 2k+1 ) be 2k + 1 vertices in S ∩ u 1 u k in clockwise order.
Observe that the k edges {u i v k-i+1 : 1 ≤ i ≤ k} are pairwise crossing, and thus receive distinct colours, as illustrated in Figure 3(a). Without loss of generality, each u i v k-i+1 is coloured i. As illustrated in Figure 3(b), this implies that u 1 v 2k+1 is coloured 1, since u 1 v 2k+1 crosses all of {u i v k-i+1 : 2 ≤ i ≤ k} which are coloured 2, 3, . . . , k. As illustrated in Figure 3(c), this in turn implies that u 2 v 2k is coloured 2, and so on. By an easy induction, u i v 2k+2-i is coloured i for each i ∈ {1, 2, . . . , k}, as illustrated in Figure 3(d). It follows that for all i ∈ {1, 2, . . . , k} and j ∈ {ki + 1, ki + 2, . . . , 2k + 2 -i}, the edge u i v j is coloured i, as illustrated in Figure 3(e). Moreover, as illustrated in Figure 3(f): Note that the argument up to now is the same as in [START_REF] Dujmović | Graph treewidth and geometric thickness parameters[END_REF]. Let w be the vertex in T adjacent to v k+1 . Recall that w is adjacent to each vertex in

If qu i ∈ E(Q) and q ∈ v k v k+2 , then qu i is coloured i. ( ) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (a) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (b) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (c) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (d) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (e) u 1 u 2 u 3 u 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (f)
K \ {u 1 }. Vertex w is in v k v k+2 , as otherwise the edge wv k+1 crosses k edges of Q[{v k , v k+2 }; K] that are all coloured differently. Without loss of generality, w is in v k v k+1 . Each vertex x ∈ T (w) is in v k v k+1 , as otherwise xw crosses k edges in Q[{v k , v k+1 }; K]
that are all coloured differently. Therefore, all nine vertices in T (w) are in v k v k+1 . By the pigeonhole principle, at least one of v k w or wv k+1 contains two vertices from T i (w) and two vertices from T j (w) for some i, j ∈ {2, 3, 4} with i = j. Let x 1 , x 2 , x 3 , x 4 be these four vertices in clockwise order in v k w or wv k+1 .

Case 1. x 1 , x 2 , x 3 and x 4 are in v k w: By ( ), the edges in Q[{w}; K] are coloured 2, 3, . . . , k. Thus x 2 v k+1 , which crosses all the edges in Q[{w}; K], is coloured 1. At least one of the vertices in {x 2 , x 3 , x 4 } is adjacent to {K \ {u 1 , u i }} and at least one to {K \ {u 1 , u j }}. Thus, by ( ), the edges in Q[{x 2 , x 3 , x 4 }; K] are coloured 2, 3, . . . , k. Thus x 1 w, which crosses all the edges of Q[{x 2 , x 3 , x 4 }; K] is coloured 1. Thus x 2 v k+1 and x 1 w cross and are both coloured 1, which is the desired contradiction.

Case 2. x 1 , x 2 , x 3 and x 4 are in wv k+1 : As in Case 1, the edges in Q[{x 2 , x 3 , x 4 }; K] are coloured 2, 3, . . . , k. Thus x 1 v k+1 , which crosses all the edges in Q[{x 2 , x 3 , x 4 }; K], is coloured 1. Since the edges in Q[{x 1 , x 2 , x 3 }; K] are coloured 2, 3, . . . , k, the edge x 4 w, which crosses all the edges of Q[{x 1 , x 2 , x 3 }; K], is coloured 1. Thus x 1 v k+1 and x 4 w cross and are both coloured 1, which is the desired contradiction.

Finally, observe that

|V (Q)| = |K| + |S| + |T | + w∈Q |T (w)| = |K| + 11|S| = k + 11(2k 2 + 1
). Adding more k-simplicial vertices to Q does not reduce its book thickness. Moreover, it is simple to verify that the graph obtained from Q by adding simplicial vertices onto K has a smooth degree-4 tree decomposition of width k. Thus for all n ≥ 11(2k 2 + 1) + k, there is a k-tree G with n vertices and bt(G) = k + 1 that has the desired tree decomposition. 2

Final Thoughts

For k ≥ 3, the minimum book thickness of a k-tree is k+1 2 (since every k-tree contains K k+1 , and bt(K k+1 ) = k+1 2 ; see [START_REF] Bernhart | The book thickness of a graph[END_REF]). However, we now show that the range of book thicknesses of sufficiently large k-trees is very limited.

Proposition 1 Every k-tree G with at least 1 2 k(k + 1) vertices has book thickness k -1, k or k + 1.

Proof: [START_REF] Ganley | The pagenumber of k-trees is O(k)[END_REF]

proved that bt(G) ≤ k + 1. It remains to prove that bt(G) ≥ k -1 assuming |V (G)| ≥ k(k+1)

2

. Numerous authors [START_REF] Bernhart | The book thickness of a graph[END_REF][START_REF] Cottafava | Book-thickness and book-coarseness of graphs[END_REF][START_REF] Keys | Graphs critical for maximal bookthickness[END_REF]

observed that |E(G)| < (bt(G) + 1)|V (G)| for every graph G. Thus (k -1)|V (G)| ≤ k|V (G)| -1 2 k(k + 1) = |E(G)| < (bt(G) + 1)|V (G)| .
Hence k -1 < bt(G) + 1. Since k and bt(G) are integers, bt(G) ≥ k -1. 2

We conclude the paper by discussing some natural open problems regarding the computational complexity of calculating the book thickness for various classes of graphs.

Proposition 1 begs the question: Is there a characterisation of the k-trees with book thickness k -1, k or k + 1? And somewhat more generally, is there a polynomial-time algorithm to determine the book thickness of a given k-tree? Note that the k-th power of paths are an infinite class of k-trees with book thickness k -1; see [START_REF] Swaminathan | The pagenumber of the class of bandwidth-k graphs is k -1[END_REF].

k-trees are the edge-maximal chordal graphs with no (k + 2)-clique, and also are the edge-maximal graphs with treewidth k. Is there a polynomial-time algorithm to determine the book thickness of a given chordal graph? Is there a polynomial-time algorithm to determine the book thickness of a given graph with bounded treewidth?

Fig. 2 :

 2 Fig. 2: A smooth degree-4 tree decomposition of Q.

Fig. 3 :

 3 Fig. 3: Illustration of the proof of Theorem 1 with k = 4.

Research supported in part by NSERC. Supported by a QEII Research Fellowship from the Australian Research Council. (i) We consider simple, finite,