O Bouaziz

A Guilloux
email: agathe.guilloux@upmc.fr

A penalized algorithm for event-specific rate models for recurrent events

Keywords: Recurrent events process, total variation penalization, Aalen model, Cox model

We introduce a covariate-specific total variation penalty in two semiparametric models for the rate function of recurrent event process. The two models are a stratified Cox model, introduced in Prentice et al. (1981), and a stratified Aalen's additive model. We show the consistency and asymptotic normality of our penalized estimators. We demonstrate, through a simulation study, that our estimators outperform classical estimators for small to moderate sample sizes. Finally an application to the bladder tumour data of Byar (1980) is presented.

Introduction

Recurrent events are frequent in clinical or epidemiological studies when each subject experiences repeated events over the time. Standard medical examples include the repetition of asthma attacks, epileptic seizures or tumour recurrences for individual patients. In this context, proportional hazards models have been largely studied in the literature to model the rate or mean functions of recurrent event data. For instance, [START_REF] Andersen | Cox's regression model for counting processes: a large sample study[END_REF] introduce a conditional Cox model where the recurrent events process is assumed to be a Poisson process. Without this assumption, similar proportional hazards models and extensions are considered in [START_REF] Lawless | Some simple robust methods for the analysis of recurrent events[END_REF], [START_REF] Lin | Accelerated failure time models for counting processes[END_REF], [START_REF] Lin | Semiparametric regression for the mean and rate functions of recurrent events[END_REF] and [START_REF] Cai | Marginal means/rates models for multiple type recurrent event data[END_REF].

To model rate functions in a recurrent events context, a different approach consists in fitting a Cox model for any different recurrence. Along these lines, [START_REF] Prentice | On the regression analysis of multivariate failure time data[END_REF] introduce two stratified proportional hazards models with event-specifics baseline hazards and regression coefficients. Gap times and conditional models are presented in their paper and a marginal event-specific model is studied in [START_REF] Wei | Regression analysis of multivariate incomplete failure time data by modeling marginal distributions[END_REF]. We refer to [START_REF] Kelly | Survival analysis for recurrent event data: an application to childhood infectious diseases[END_REF] for a complete review of existing Cox-based recurrent event models.

Additive models provide an useful alternative to proportional hazards models. For classical counting processes, the Aalen model was first introduced in [START_REF] Aalen | A model for nonparametric regression analysis of counting processes[END_REF] and is extensively studied in [START_REF] Mckeague | Asymptotic theory for weighted least squares estimators in Aalen's additive risk model[END_REF], [START_REF] Huffer | Weighted least squares estimation for aalen's additive risk model[END_REF], [START_REF] Lin | Semiparametric analysis of the additive risk model[END_REF]. It is considered in the context of recurrent events in [START_REF] Scheike | The additive nonparametric and semiparametric Aalen model as the rate function for a counting process[END_REF]. We propose in this paper to consider an event-stratified version of the Aalen model, in the manner of [START_REF] Prentice | On the regression analysis of multivariate failure time data[END_REF].

As demonstrated in the following, event-stratified models allow more flexibility but suffer from over-parametrization as soon as the sample size is not large enough with respect to the number of covariates and the number of recurrent events. We address this drawback by introducing new estimators defined as minimizers of penalized empirical risks. More specifically, we consider a covariate-specific total variation penalty. The remainder of this article is organized as follows. The multiplicative and additive models studied in this paper are presented in Section 1. In Paragraph 2•4, we describe our novel algorithms. It requires preliminary details on inference in these two models, which are given in Paragraphs 2•2 and 2•3. Consistency and asymptotics normality of the estimators are derived in Section 3. Simulation studies and a real data analysis are provided in Sections 4 and 5. A discussion and some concluding remarks are contained in Section 6.

2. Models and algorithm 2•1. Models Let D denote the time of the terminal event and N * (t) the number of recurrent events before time t. The end-point of the observation is τ > 0. The p-dimensional process of covariates is denoted by X and ρ 0 represent the rate function. The event-specific rate function of the process N * is then defined as

E dN * (t) | X(t), D ≥ t, N * (t) = s -1 = 1(D ≥ t)ρ 0 (t, s, X(t))dt,
for t in [0, τ ] and s = 1, . . . , B. Apart from the stratification, this definition of the rate function can be found in [START_REF] Scheike | The additive nonparametric and semiparametric Aalen model as the rate function for a counting process[END_REF].

We consider two semiparametric models for the function ρ 0 . The first one is an eventspecific multiplicative rate model introduced in [START_REF] Prentice | On the regression analysis of multivariate failure time data[END_REF]. In this model, the rate function is specified, for t in [0, τ ], by

ρ 0 (t, s, X(t)) = α 0 (t, s) exp (X(t)β 0 (s)) (1)
where for each event number s, β 0 (s) is an unknown p-dimensional vector of parameters and α 0 is an unknown baseline function.

Following [START_REF] Scheike | The additive nonparametric and semiparametric Aalen model as the rate function for a counting process[END_REF], and [START_REF] Zeng | A semiparametric additive rate model for recurrent events with an informative terminal event[END_REF], we also propose to consider its additive counterpart. The rate function in our event-specific additive model is then for t in [0, τ ]:

ρ 0 (t, s, X(t)) = (α 0 (t, s) + X(t)β 0 (s)) .
(2)

The models, where β 0 is constant over the events are refereed to as constant models in what follows.

We consider the problem of estimating the unknown parameter β 0 , in stratified models (1) and (2) on the basis of data from n independent and identically distributed random variables. Introduce the censoring time C. In a random sample of n subjects, the data consist of

{N i (t), T i , δ i , X i (t), t ≤ τ }, i = 1, . . . , n where N i (t) = N * i (t ∧ C i ), T i = D i ∧ C i 75 is the minimum between D i and C i , δ i = 1(D i ≤ C i ) and (X i (t), 0 ≤ t ≤ T i )
is the covariates process. The next assumption characterizes the dependence mechanism between the censoring time and the other variables.

Assumption 1. For all s = 1, . . . , B and t in [0, τ ],

E dN * (t) | X(t), D ∧ C ≥ t, N * (t) = s -1 = E dN * (t) | X(t), D ≥ t, N * (t) = s -1 .
Note that this assumption is slightly weaker than assuming the independence between C and (N * , D, X). A similar assumption can be found for instance in [START_REF] Lin | Semiparametric regression for the mean and rate functions of recurrent events[END_REF]. We also impose the following conditions on the tails of the distribution of T and N .

Assumption 2. There exists a nonnegative integer B such that

(i) ∀t ∈ [0, τ ], P N (t) ≤ B = 1, (ii) ∀t ∈ [0, τ ], ∀s = 1, . . . , B, P T ≥ t, N (t) = s -1 | X(t) > 0.
Assumption 2 (i) ensures that in models (1) and ( 2), the total number of observed events is almost surely bounded. It is standard for inference for recurrent events process, see e.g. [START_REF] Dauxois | Non-parametric tests for recurrent events under competing risks[END_REF], [START_REF] Scheike | The additive nonparametric and semiparametric Aalen model as the rate function for a counting process[END_REF] or [START_REF] Bouaziz | Nonparametric estimation of the intensity function of a recurrent event process[END_REF].

Under Assumption 2, the unknown vector of parameters β 0 has p × B unknown coefficients to be estimated. For reasonable sizes of sample n, these models are overparametrized in the sense that, when √ n ≤ p × B, the estimators show very poor behaviours (see Section 4 for an illustration). On the other hand, simpler forms of models ( 1) and ( 2), in which the unknown parameter does not change with the event, β 0 (s) = β 0 , might be too poor to accurately fit the data (see also Section 4 and the discussion in [START_REF] Kelly | Survival analysis for recurrent event data: an application to childhood infectious diseases[END_REF]). In this paper, we aim at providing estimators realizing a compromise between these two situations.

In the following, we define, for each individual i, the event-specific at-risk function Y s i and the overall at-risk function Y i for all t in [0, τ ]:

Y s i (t) = 1(T i ≥ t, N i (t) = s), Y i (t) = B s=1 Y s i (t) = 1(T i ≥ t).

2•2. Inference in the multiplicative model

As in [START_REF] Prentice | On the regression analysis of multivariate failure time data[END_REF], in the multiplicative event-specific model ( 1), an estimator βES/mult of the unknown parameter β 0 ∈ R p×B is defined as the maximizer of the partial log-likelihood, or equivalently as βES/mult ∈ argmin

β∈R p×B L P L n (β) (3) = argmin β∈R p×B   - 1 n B s=1 n i=1    X i (t)β(s) -log   n j=1 Y s j (t) exp (X j (t)β(s))      Y s i (t)dN i (t)   .
105

An estimator βC/mult in the constant model is defined as βC/mult ∈ argmin

β∈R p   - 1 n n i=1    X i (t)β -log   n j=1 Y j (t) exp (X j (t)β)      Y i (t)dN i (t)   .
(4) 2•3. Inference in the additive model As noticed in Martinussen & Scheike (2009a,b) or [START_REF] Gaiffas | High-dimensional additive hazards models and the lasso[END_REF], in the usual additive hazards model, the estimator βES/add of the unknown parameter β 0 ∈ R p×B can be written as the minimizer of a (partial) least-squares criterion: βES/add ∈ argmin

β∈R p×B L P LS n (β) = argmin β∈R p×B B s=1 β(s) H n (s)β(s) -2h n (s)β(s) , (5)
where for all s ∈ {1, . . . , B}, H n (s) are p × p symetrical positive semidefinite matrices equal to

1 n n i=1 Y s i (t) X i (t) -Xs (t) ⊗2 dt,
and where h n (s) are p-dimensional vectors equal to

1 n n i=1 1(N i (t) = s) X i (t) -Xs (t) dN i (t), with Xs (t) = n i=1 X i (t)Y s i (t)/ n i=1 Y s i (t).
We show in the Appendix why this criterion is a relevant strategy in the additive event-specific model. On the other hand, an estimator βC/add in the constant model is defined as βC/add ∈ argmin 6) 2•4. A total-variation penalty To overcome the possible over-parametrization of models (1) and ( 2), we propose to define penalized versions of criteria (3) and ( 5). For all β = (β(s), s = 1, . . . , B) with β(s) = (β 1 (s), . . . , β p (s)), define for all j = 1, . . . , p β j = (β j (1), . . . , β j (B)) and tv(

β∈R p β H n β -2h n β , with H n = B s=1 H n (s) and h n = B s=1 h n (s). (
β j ) = B s=2 |β j (s) -β j (s -1)| = B s=2 |∆β j (s)|. ( 7
)
We now consider the minimizers of the partial log-likelihood (respectively the partial least-squares) penalized with a covariate specific total variation. Define the penalized estimators in models (1) and (2) as:

βtv/mult ∈ argmin β∈R p×B    L P L n (β) + λ n n p j=1 tv(β j )    and (8) βtv/add ∈ argmin β∈R p×B    L P LS n (β) + λ n n p j=1 tv(β j )    . ( 9
)
These penalized algorithms can be rewritten as lasso algorithms (the details are given in Supplementary Material).

Asymptotic results

We successively provide the asymptotic results for the estimators βtv/add in the additive model and βtv/mult in the multiplicative model. In both models, the following condition is mandatory.

Assumption 3. The covariates process X(•) is of bounded variation on [0, τ ]. Define for all s = 1, . . . , B the centered process M s (t) = N (t) -E N (t) | X(t), D ∧ C ≥ t, N (t) = s -1 and the p × p matrix H(s) := E[Y s (t)X(t) X(t)]dt - (E[Y s (t)X(t)]) ⊗2 E[Y s (t)] dt,
which from Assumption 2 (ii) is well defined.

Theorem 1. Assume that, for each s = 1, . . . , B, H(s) is non-singular and that Asumptions 1, 2 and 3 are fulfilled.

1. If λ n /n → 0 as n → ∞ then βtv/add converges to β 0 in probability. 2. If λ n / √ n → λ 0 ≥ 0 as n → ∞ then √ n( βtv/add -β 0 ) converges in distribution to argmin u∈R p Λ add (u) = argmin u∈R p B s=1 u(s) H(s)u(s) -2u(s) ξ add (s) + λ 0 p j=1 B s=2 |∆u j (s)|1(∆β j (s) = 0) + sgn(∆β j (s))(∆u j (s))1(∆β j (s) = 0) ,
and for each s, ξ add (s) is a centered p-dimensional gaussian vector with covariance matrix equal to

E τ 0 (X(t) -E[Y s (t)X(t)]/E[Y s (t)])1(N (t) = s)dM s (t) ⊗2 .
Define for all s = 1, . . . , B and for all t ∈ [0, τ ],

s (l) (s, t, β) = E[Y s (t)X(t) ⊗l exp(X(t)β(s))], l = 0, 1, 2. Introduce e(s, t, β) = s (1) (s, t, β)/s (0) (s, t, β), v(s, t, β) = s (2) (s, t, β)/s (0) (s, t, β) - e(s, t, β) ⊗2 and Σ(s, β) = v(s, t, β)E[Y s (t)dN (t)].
For any s = 1, . . . , B and for any t ∈ [0, τ ], the three functions s (l) (s, t, β 0 ) are bounded from Assumption 3 and e(s, t, β), v(s, t, β) and Σ(s, β) are finite from Assumptions 2 and 3.

Theorem 2. Assume that for each s = 1, . . . , B, Σ(s, β 0 ) is non-singular and that Assumptions 1, 2 and 3 are fulfilled.

1. If

λ n /n → 0 as n → ∞ then βtv/mult converges to β 0 in probability. 2. If λ n / √ n → λ 0 ≥ 0 as n → ∞ then √ n( βtv/mult -β 0 ) converges in distribution to 155 argmin u∈R p Λ mult (u) = argmin u∈R p B s=1 1 2 u(s) Σ(s, t, β 0 )u(s) + u(s) ξ mult (s) + λ 0 p j=1 B s=2
|∆u j (s)|1(∆β j 0 (s) = 0) + sgn(∆β j 0 (s))(∆u j (s))1(∆β j 0 (s) = 0) , and for each s, ξ mult (s) is a centered p-dimensional gaussian vector with covariance matrix equal to

E τ 0 (X(t) -e(s, t, β 0 )) Y s (t)dM s (t) ⊗2 .
Theorems 1 and 2 prove the consistency and asymptotic normality of our estimators ( 8) and ( 9). This assures that they behave better than the constant estimators when β 0 is non constant. In addition, the considered penalty will induce sparsity for each covariate j = 1, . . . , p in the successive differences ∆β j (s), s = 1, . . . , B. As a consequence, the effects of a covariate on two consecutive events will often be equal. We show, in the following simulation study, that this induced sparsity ameliorates the behaviour of our estimators compared to the unconstrained ones (defined in Equations ( 3) and ( 5)).

Simulation studies

We compare the performances of the penalized estimators ( 8) and ( 9), the constant ones ( 4) and ( 6) , and the unconstrained ones (3) and (5). To mimic the bladder tumour cancer dataset studied in Section 5, we set p = 4 and consider B = 5 recurrent events for the estimation. In the multiplicative and additive models, the sample size n varies from n = 50 = 2•5 pB to n = 1000 (pB) 2•3 .

We draw the p = 4 covariates from uniform distributions and set the parameters values at

β 1 0 = (0, 0, b 1 , b 1 , 0, . . . , 0), β 2 0 = (b 2 , . . . , b 2 ), β 3 0 = b 3
(1, 2, 3, . . .) and β 4 0 = (0, . . . , 0). We generate recurrent event times from the multiplicative (1) and additive (2) models with baseline defined through the Weibull distribution with shape parameter a W and scale parameter 1. The death and censoring times are generated from exponential distributions with parameters a D and a C respectively. We set the value of parameter a W at 2•5. Finally, the values of a D and a C are empirically determined to obtain p obs = 28 -29% and 14 -15% of individuals experiencing the fifth event.

To evaluate the performances of the different estimators, we conduct a Monte Carlo study with M = 200 experiences. The estimation accuracy is investigated for each method via a mean squared rescaled error defined as

mse = 1 M M m=1 βm -β 0 2 β 0 2 , ( 10
)
where βm is the estimation in the sample m. We furthermore study the detection power of non-constant (respectively constant) covariate effects by computing mean false positive (fp) rates and mean false negative (fp) rates for each method. They are defined, for an estimation βm , as fp( βm ) = Card j ∈ {1, . . . , p} s.t. tv( βj ) = 0 and tv(β j 0 ) = 0 (11) and fn( βm ) = Card j ∈ {1, . . . , p} s.t. tv( βj ) = 0 and tv(

β j 0 ) = 0 , ( 12
)
where tv is defined in (7).

As expected, the constant model is biased and behave poorly for our choice of a nonconstant β 0 . The comparison between the unconstrained and penalized estimators is in favour of our estimator in all four cases as long as n is smaller than p 2 . When the percentage of individuals experiencing the fifth event drops, non-constant estimators are slightly less accurate. Algorithms are not able to compute all M = 200 unconstrained estimators for n = 50. For p = 4, B = 5, n = 100 and p obs = 14% (which are values close 195 to those encountered in the bladder tumour cancer dataset studied in the next section) our penalized estimators are respectively 5•8, in the additive model, and 10•6, in the multiplicative model, times better than the unconstrained ones in terms of estimation error. Surprisingly the number of false positives detected by our penalized estimators in-200 creases when the sample size increases. A possible solution to ameliorate the latter is to apply the reweighed lasso, or two-steps lasso, as proposed in [START_REF] Candès | Enhancing sparsity by reweighted l1 minimization[END_REF] (details are given in Supplementary Material). We compute the mean squared error, false positive and negative rates of the resulting estimator. It shows better false positive rates than the first step penalized estimator, greater false negative rates and comparable mean squared errors.

We repeat the simulation study for a W = 2•5 and then for a Gompertz baseline with shape parameter a G = 0•5 (and a G = 0•5) and scale parameter 1. The results are reported in Supplementary Material. Conclusions are similar.

Bladder tumour data analysis

In this section we illustrate the behaviour of our estimators on the bladder tumour cancer data of [START_REF] Byar | The veterans administration study of chemoprophylaxis for recurrent stage 1 bladder tumors: comparison of placebo, pyridoxine, and topical thiotepa. Bladder Tumors and Others Topics in Urological Oncology[END_REF]. These data were obtained from a clinical trial conducted by the Veterans Administration Co-operative Urological Group. One hundred and sixteen patients were randomised to one of three treatments: placebo, pyridoxine or thiotepa. For each patient, the time of recurrence tumours were recorded until the death or censoring times. The number of recurrences ranges from 0 to 10. On the n = 116 patients, since 13• 79% experienced at least five tumour recurrences and only 6•9% patients experienced six tumour recurrences or more, we set the parameter B to 5. In addition to the two treatment variables, pyridoxine and thiotepa, two supplementary covariates were recorded for each patient: the number of initial tumours and the size of the largest initial tumour.

Figure 1 displays the estimations obtained from the constant, unconstrained and total variation estimators in the multiplicative model. In order to enforce the variables selection performance of the total variation estimator, the coefficients were estimated using the reweighed lasso. The unconstrained estimator shows very strong variations and is difficult to interpret as such. On the other hand, the constant estimator gives valuable information on the impact of each covariate, but in turn cannot detect a change in variation. Our total-variation estimator reaches compromise: it is not constant but easily interpretable.

For instance, a remarkable aspect of the pyrodixine treatment can be highlighted from the total variation estimation: this treatment produces a protective effect for the first three tumour recurrences but the odds of further recurrences are increased by this treatment. In the same way, an increase in the effect of the initial number of tumours on recurrences is observed from the third recurrence. On the opposite, the effects of the thiotepa treatment or the size of the largest tumour are shown to be constant in the total variation model, the parameter estimates having values similar to the ones obtained in the constant model.

Our conclusions on the treatments effects are in agreement with previous studies on bladder tumours recurrences. For instance, no difference in the rate or time to tumour recurrence was found from patients using pyrodixine with patients using placebo in [START_REF] Tanaka | Pathobiology and chemoprevention of bladder cancer[END_REF] and [START_REF] Goossens | Designing the selenium and bladder cancer trial (seleblat), a phase lll randomized chemoprevention study with selenium on recurrence of bladder cancer in belgium[END_REF]. Moreover, [START_REF] Huang | Marginal regression of gaps between recurrent events[END_REF] and [START_REF] Sun | The additive hazards model for recurrent gap times[END_REF] have respectively studied gap time recurrences in the multiplicative and additive models. The results obtained from the former showed a small protective effect of this treatment while the latter concluded that gap times did not seem related to pyridoxine. These examples illustrate the nice features of our total-variation estimator: it provides sharper results, giving relevant informations on covariates effect with respect to the number of recurrent events experienced by a subject and it provides the ability to detect a change of variation. Further details are provided in Supplementary Material.

Discussion

In this paper, the Aalen and Cox models were studied to model the effect of covariates on the rate function. However, such models are not essential in our approach. Penalized algorithms could be easily derived for other models such as the accelerated failure time model or the semiparametric transformation model for instance.

Although we have only presented asymptotic theoretical results, the simulation studies show clear evidence that our estimators outperform standard estimators for small sample sizes. Therefore, it would be of great interest to study their finite sample properties. However, such results involve deviation inequalities for non i.i.d. and non martingale empirical processes. To our knowledge, no such results have yet been established in the context of recurrent events.

Another development of the present paper would be to establish results for the estimation of change-point locations and the number of change-points. Such results can be found for the change-point detection in the mean of a gaussian signal in [START_REF] Harchaoui | Multiple change-point estimation with a total variation penalty[END_REF], for instance.

Appendix: Proofs

Proofs of Lemma 1 to 3 are in Supplementary Material. pointwise convergence of Γ add n (β) towards Γ add (β). Now write: Thus Λ add n (u) converges to Λ add (u) in distribution. Since Λ add n is convex and Λ add has a unique minimum, it follows that √ n( βtv/add -β 0 ) converges to argmin u Λ add (u) in distribution.

Γ add n (β) -Γ add (β) ≤ L P LS n (β) -Γ(β) + λ n n Bp max s,j |β j (s) -β j (s -1)| ≤ Bp 2 max j,k,s |β j (s)β k (s)(H j,k n (s) -H j,k (

Proof of Theorem 2

First define for l = 0, 1 or 2

S (l) n (s, t, β) = 1 n n i=1
Y s i (t)X i (t) ⊗l exp(X i (t)β(s)). Following the arguments in example VII.2.7 page 502 of [START_REF] Andersen | Statistical models based on counting processes[END_REF], it can easily be shown that

Fig. 1 .

 1 Fig.1. Estimates for the bladder data in the multiplicative model. The crosses represent the constant estimator, the filled circles the unconstrained estimator and the squares the reweighed lasso estimator.

  h j (s)||β j (s)| + λ n n Bpand the result follows from the law of large number and the fact that λ n /n → 0 as n tends to infinity.

  t) -E[Y s (t)X(t)]/E[Y s (t)])1(N (t) = s)dM s (t) s) H n (s)u(s) converges to B s=1 u(s) H(s)u(s), in probability and λ n j tv(β j 0 + u j / √ n)tv(β j 0 ) /λ 0 converges to p j=1 B s=2|∆u j (s)|1(∆β j (s) = 0) + sgn(∆β j 0 (s))(∆u j (s))1(∆β j (s) = 0) .

  sup t∈[0,τ ] |S (l) n (s, t, β 0 ) -s (l) (s, t, β 0 )|

Table 1 .

 1 Simulation results in the multiplicative model for p obs = 28%

	n	Unconstrained	Constant			tv		two-steps tv
		mse	fp fn	mse	fp fn	mse	fp	fn	mse	fp	fn
	50	0•100	2	0	0•412	0	2	0•054 1•44 0•03 0•044 0•82 0•02
	100	0•030	2	0	0•415	0	2	0•025 1•54	0	0•019 0•76	0
	500	0•006	2	0	0•413	0	2	0•008 1•76	0	0•006 0•30	0
	1000	0•005	2	0	0•415	0	2	0•006 1•81	0	0•006 0•05	0

mse: mean squared error, fp: false positives, fn: false negatives.

Table 2 .

 2 Simulation results in the multiplicative model for p obs = 14%

	n	Unconstrained	Constant			tv		two-steps tv
		mse	fp	fn	mse	fp fn	mse	fp	fn	mse	fp	fn
	50	NA	NA NA 0•440	0	2	0•161 1•37 0•185 0•137 0•82 0•19
	100	0•566	2	0	0•434	0	2	0•053 1•55 0•005 0•042 0•88	0
	500	0•014	2	0	0•433	0	2	0•016 1•84	0	0•012 1•06	0
	1000	0•009	2	0	0•433	0	2	0•011 1•89	0	0•010 0•68	0

mse: mean squared error, fp: false positives, fn: false negatives, na: non applicable .

Table 3 .

 3 Simulation results in the additive model for p obs 28%

	n	Unconstrained	Constant			tv		two-steps tv
		mse	fp fn	mse	fp fn	mse	fp	fn	mse	fp	fn
	50	4•986	2	0	0•416	0	2	0•467 0•98 0•58 1•142 0•65 0•81
	100	0•935	2	0	0•351	0	2	0•254 1•38 0•21 0•353 0•86 0•48
	500	0•135	2	0	0•309	0	2	0•079 1•91 0•01 0•094 1•44 0•08
	1000	0•071	2	0	0•299	0	2	0•049 1•98	0	0•05	1•64	0

mse: mean squared error, fp: false positives, fn: false negatives

Table 4 .

 4 Simulation results in the additive model for p obs 14%

	n	Unconstrained	Constant			tv		two-steps tv
		mse	fp	fn	mse	fp fn	mse	fp	fn	mse	fp	fn
	50	NA	NA NA 0•505	0	2	0•781	0•95	0•81 2•368 0•86 0•97
	100	4•114	2	0	0•393	0	2	0•707 1•450 0•27	0•84	1•11 0•52
	500	0•339	2	0	0•330	0	2	0•154 1•975 0•01	0•19	1•67 0•06
	1000	0•171	2	0	0•320	0	2	0•097 1•995	0	0•12	1•80 0•02

mse: mean squared error, fp: false positives, fn: false negatives, na: non applicable .

  Let F n (t) = s ( Xs (t) -E[Y s (t)X(t)]/E[Y s (t)])u(s)and F (t) = 0. F n has bounded variation and from Lemma A3 (ii), the second term converges to 0 in probability. Now, take f (T i , δ i , X

								X i (t) -	E[Y s (t)X(t)] E[Y s (t)]	u(s)1(N i (t) = s)dM s i (t)
	-	1 √ n	n i=1	0	τ	B s=1	Xs (t) -	E[Y s (t)X(t)] E[Y s (t)]	u(s)1(N i (t) = s)dM s i (t).

i (t), N i (t)) = s (X i (t) -E[Y s (t)X(t)]/E[Y s (t)])u(s)1(N i (t) = s)

which is also a function of bounded variation. From Lemma A3 (i), the first term converges weakly towards a centered gaussian variable with variance equal to

E τ 0 B s=1 (X(t) -E[Y s (t)X(t)]/E[Y s (t)])u(s)1(N (t) = s)dM s (t) 2 = B s=1 u(s) E

A key relation Lemma A1. Under Assumption 1, for all i = 1, . . . , n

Decomposition of the least squares criterion in the additive model

The next proposition gives the details of the construction of the partial least squares in the additive model. One has to notice that the processes Z n (s) introduced below are centered which implies that finding a minimizer of L P LS n is a natural way of estimating β 0 in model (2). Lemma A2. In the additive event-specific model (2), the partial least squares criterion (5) can be rewritten as

where

A technical lemma

Lemma A3. Let D[0, τ ] denotes the set of càdlàg functions on [0, τ ] and let F n (•) and

We then have the following properties:

converges weakly in D[0, τ ] to a centered gaussian process with variance equal to

Proof of Theorem 1

Proof of 1. Let Γ add n (β) be the quantity minimized by βtv/add and introduce Γ add

Using Lemma A1 notice that h(s) = β 0 (s) H(s) and consequently, argmin β Γ add = β 0 . Since the criterion to minimize is convex, the convergence in probability of βtv/add to β 0 follows from the using the fact that the covariates process is of bounded variation (in particular, this assumption guarantees that s (l) (s, t, β 0 ) has a countable number of jumps).

Proof of 1. Let Γ mult n (β) be the quantity minimized by βtv/mult and introduce

where the last equality follows from Lemma A1. From similar arguments as in proof 1. of Theorem 1 and the uniform convergence with respect to t of S (0)

n (s, t, β 0 ) towards s (0) (s, t, β 0 ), we get the pointwise convergence in probability of Γ mult n (β) to Γ mult (β). Then, the consistency of βtv/mult follows from the convexity of Γ mult n (β) and the fact that argmin β Γ mult (β) = β 0 . Proof of 2. Consider the convex function

which is minimum at u = √ n( βtv/mult -β 0 ). Then from a Taylor expansion, one gets

where

The uniform convergence with respect to t of S (0) n (s, t, β) and S

(2) n (s, t, β) towards s (0) (s, t, β 0 ) and s (2) (s, t, β 0 ) respectively and the law of large number give the convergence in probability of the term

From Lemma 3, the same kind of arguments as in the proof of Theorem 1 can be applied to 335 conclude the proof.

Supplementary material Supplementary material includes a description of the algorithms, extended simulation study and additional analysis on the bladder tumour data of [START_REF] Byar | The veterans administration study of chemoprophylaxis for recurrent stage 1 bladder tumors: comparison of placebo, pyridoxine, and topical thiotepa. Bladder Tumors and Others Topics in Urological Oncology[END_REF]. It also contains proofs of 400 Proposition 2 and Lemma 3.


S Bessy

F Havet

Introduction

Colorings Algorithmic problems Our results

Enumerating the 3-edge colorings of a cubic graph The 3-edge colorings of a 3-regular graph Turning the proof into algorithm Extensions: k-edge colorings and the total colorings k-edge colorings A more precise bounds for the 3-edge coloring Total coloring Conclusion

Introduction

Total Coloring

Definition (k-total coloring) A k-total coloring of G = (V , E ) is c : V ∪ E → {1, . . . , k} such that: -uv ∈ E implies c(u) = c(v ) -uv ∈ E and uw ∈ E , with v = w implies c(uv ) = c(uw ) -uv ∈ E implies c(uv ) = c(u) b c f a e d Total Coloring Definition (k-total coloring) A k-total coloring of G = (V , E ) is c : V ∪ E → {1, . . . , k} such that: -uv ∈ E implies c(u) = c(v ) -uv ∈ E and uw ∈ E , with v = w implies c(uv ) = c(uw ) -uv ∈ E implies c(uv ) = c(u) b c f a e d Total Coloring Definition (k-total coloring) A k-total coloring of G = (V , E ) is c : V ∪ E → {1, . . . , k} such that: -uv ∈ E implies c(u) = c(v ) -uv ∈ E and uw ∈ E , with v = w implies c(uv ) = c(uw ) -uv ∈ E implies c(uv ) = c(u) b c f a e d
Definition (total chromatic number)

χ T (G ) is the minimum k such that G admits a k-total coloring.

Famous bounds

Let ∆(G ) denotes the maximum degree of G .

Brook 's Theorem (1941):

χ(G ) ≤ ∆(G ) if G is not a complete graph or an odd cycle.

Famous bounds

Let ∆(G ) denotes the maximum degree of G .

Brook 's Theorem (1941):

χ(G ) ≤ ∆(G ) if G is not a complete graph or an odd cycle.
Vizing 's Theorem (1964):

∆(G ) ≤ χ ′ (G ) ≤ ∆(G ) + 1
Total coloring conjecture (Behzad, Vizing, ∼1964): 1981).

∆(G ) + 1 ≤ χ T (G ) ≤ ∆(G ) + 2
k-total coloring is NP-complete for every fixed k ≥ 4 (A. Sánchez-Arroyo, 1989).

Enum-k-vertex/edge/total coloring: -Input: a graph G = (V , E ) -Output: Enumerate all the k-vertex/edge/total coloring of G .

Algorithmic problems

k-vertex/edge/total coloring: Garey and D.S. Johnson, 1979).

-Input: a graph G = (V , E ) -Output: Does G admit a k-vertex/edge/total coloring? k-vertex coloring is NP-complete for every fixed k ≥ 3 (M.R.
k-edge coloring is NP-complete for every fixed k ≥ 3 (I. Holyer, 1981).

k-total coloring is NP-complete for every fixed k ≥ 4 (A. Sánchez-Arroyo, 1989).

Enum-k-vertex/edge/total coloring:

-Input: a graph G = (V , E ) -Output: Enumerate all the k-vertex/edge/total coloring of G .

Algorithmic point of view

What to do with an NP-complete problem?

approximation algorithm: find in poly-time a result which is not worst than c time the optimal.

randomized algorithm: find a result which is good w.h.p. or/and with running time correct w.h.p.

... parameterized algorithm: find an algorithm with running time f (k).poly (n) for some parameter k.

exact (exponential) algorithms: find an algorithm with running time

O ⋆ (c n ) (= O(P(n)c n ))

Examples of exact algorithms

Enum-3-edge coloring:

-Input: a graph G = (V , E ) with ∆(G ) ≤ 3.
-Output: Enumerate all the 3-vertex/edge/total coloring of G .

The exhaustive algorithm:

-Try every possible colorings of the edge set and decide which colorings are proper.

Time analysis:

O ⋆ (3 m ) = O ⋆ (3

Examples of exact algorithms

Enum-3-edge coloring:

-Input: a graph G = (V , E ) with ∆(G ) ≤ 3.
-Output: Enumerate all the 3-vertex/edge/total coloring of G .

The exhaustive algorithm:

-Try every possible colorings of the edge set and decide which colorings are proper.

Time analysis:

O ⋆ (3 m ) = O ⋆ (3

Examples of exact algorithms

Enum-3-edge coloring: a 'naive' branching algorithms

Previous work: exact algorithms

What is the gain on the running time?

In the same environment:

t = O ⋆ (a n 1 ) = O ⋆ (b n 2 ) with a < b
We obtain: n 1 ∼ log b log a n 2 A multiplicative factor on the instance size of log b log a > 1

Previous work: exact algorithms

What is the gain on the running time?

In the same environment: Our results

t = O ⋆ (a n 1 ) = O ⋆ (b n 2 ) with a < b We obtain: n 1 ∼ log b log a n 2 A multiplicative

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting

Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n )
Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n ) ? ≤ Enum-4-total coloring ≤ O ⋆ (3.0845 n )
Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n ) ? ≤ Enum-4-total coloring ≤ O ⋆ (3.0845 n )
Our results:

Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). (factor on data size: 1.25)

Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n ) ? ≤ Enum-4-total coloring ≤ O ⋆ (3.0845 n )
Our results:

Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). (factor on data size: 1.25)

Enum-4-total coloring in O ⋆ (2.8285 n ). Example in Ω(2.3784 n ).
Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n ) ? ≤ Enum-4-total coloring ≤ O ⋆ (3.0845 n )
Our results:

Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). (factor on data size: 1.25)

Enum-4-total coloring in O ⋆ (2.8285 n ). Example in Ω(2.3784 n ). Enum-k-edge coloring in O ⋆ ((k -1!) n
2 ) and a sharp example (multi-graph).

Our results

Motivations:

a useful technique for edge coloring 3-edge coloring more interesting Gap:

Ω(1.2822 n ) ≤ Enum-3-edge coloring ≤ O ⋆ (1.5423 n ) ? ≤ Enum-4-total coloring ≤ O ⋆ (3.0845 n )
Our results:

Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). (factor on data size: 1.25)

Enum-4-total coloring in O ⋆ (2.8285 n ). Example in Ω(2.3784 n ). Enum-k-edge coloring in O ⋆ ((k -1!) n 2 )
c 3 (C n ) = 2 n + 2, if n is even, 2 n -2, if n is odd.

Number of 3-edge colorings of 3-regular graphs

Lemma Let C n be the cycle of length n.

c 3 (C n ) = 2 n + 2, if n is even, 2 n -2, if n is odd.
Proof: By induction on n. True for n = 2 and n = 3.

c 3 (C n ) = 2 n + 2, if n is even, 2 n -2, if n is odd.
Proof: By induction on n. True for n = 2 and n = 3. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

v2 v1 vn vn-1 v3 vn-2 v2 vn-1 v3 vn-2 v1 c 3 (C n ) = 2.c 3 (C n-2 )+ c 3 (C n-1 ) S.
Number of 3-edge colorings of 3-regular graphs

We denote by n i the number of vertices of degree i in G .

Theorem

Let G be a 2-connected subcubic graph. Then c

3 (G ) ≤ 3 • 2 n-n 3 2 .

Number of 3-edge colorings of 3-regular graphs

We denote by n i the number of vertices of degree i in G .

Theorem

Let G be a 2-connected subcubic graph. Then c

3 (G ) ≤ 3 • 2 n-n 3 2 . Proof: If G is a cycle, it is true.
Otherwise, let v 1 and v n be two vertices of degree 3 and consider v 1 , . . . , v n an st-ordering of G : for all 1 Enum-3-edge coloring:

< i < n, d(v i ) {v 1 ,...,v i-1 } ≥ 1 and d(v i ) {v i+1 ,...,
Corollary (Solving Enum-3-edge coloring:)

There exists a branching algorithm with running time O ⋆ (2 Number of 3-edge colorings for simple graphs

n 2 ) = O ⋆ (1.4143 n
Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

c 3 (H n ) = 2 n/2 + 8, if n/2 is even, 2 n/2 -2, if n/2 is odd.

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let M n be:

Lemma (c 3 of the Moebius ladder graph)

c 3 (M n ) = 2 n/2 + 2, if n/2 is even, 2 n/2 + 4, if n/2 is odd.
Enum-4-total coloring:

Corollary (Solving Enum-3-edge coloring:)

There exists a branching algorithm with running time O ⋆ (2

2 ) = O ⋆ (2.8285 n ) and polynomial space to solve Enum-4-total coloring.

  edge colorings of a cubic graph The 3-edge colorings of a 3-regular graph Turning the proof into algorithm Extensions: k-edge colorings and the total colorings k-edge colorings A more precise bounds for the 3line graph L(G ) of G : -The vertex set of L(G ) is the edge set of G -Two edges e and f of G are adjacent in L(G ) if there are incident in G line graph L(G ) of G : -The vertex set of L(G ) is the edge set of G -Two edges e and f of G are adjacent in L(G ) if there are incident in G total coloring of G = (V , E ) is c : V ∪ E → {1, . . . , k} such that: uv ∈ E implies c(u) = c(v ) uv ∈ E and uw ∈ E , with v = w implies c(uv ) = c(uw ) uv ∈ E implies c(uv ) = c(u)

  Time analysis: O⋆ (2 m ) = O ⋆ (2Examples of exact algorithmsEnum-3-edge coloring: a 'naive' branching algorithms Time analysis: O ⋆ (2 m ) = O ⋆ (2

  factor on the instance size of log b log a

  and a sharp example (multi-graph). More precise bound on the number of 3-edge coloring of simple graph Introduction Colorings Algorithmic problems Our results Enumerating the 3-edge colorings of a cubic graph The 3-edge colorings of a 3-regular graph Turning the proof into algorithm Extensions: k-edge colorings and the total colorings k-edge colorings A more precise bounds for the 3edge colorings of 3-regular graphs Lemma Let C n be the cycle of length n.

  3 (C n ) = 2.c 3 (C n-2 )+ S.Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012 Number of 3-edge colorings of 3-regular graphs Lemma Let C n be the cycle of length n.

  ) and polynomial space to solve Enum-3-edge coloring.S.Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012Enum-3-edge coloring:Corollary (Solving Enum-3-edge coloring:)There exists a branching algorithm with running time O ⋆ (2n 2 ) = O ⋆ (1.4143 n) and polynomial space to solve Enum-3-edge coloring.Proof:If ∆ ≥ 4 answer 0. If the graph is not connected enough, divide the instance.Otherwise, run a branching algorithm. edge colorings of a cubic graph The 3-edge colorings of a 3-regular graph Turning the proof into algorithm Extensions: k-edge colorings and the total colorings k-edge colorings A more precise bounds for the 3

  Minimum vertex coloring in O ⋆ (2 n ) (A. Bjöklund, T. Husfeld and M. Koivisto, 2006) Is there a O ⋆ ((2 -ǫ) n ) algorithm for some ǫ > 0 Minimum vertex coloring in O ⋆ (2 n ) (A. Bjöklund, T. Husfeld and M. Koivisto, 2006) Is there a O ⋆ ((2 -ǫ) n ) algorithm for some ǫ > 0 Minimum edge coloring in O ⋆ (2 m ) Is there a O ⋆ (2 n ) algorithm Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). Is it possible to fix c 3 (n) = max{c 3 (G ) : G simple graph on n vertices} We know that 2 Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). Is it possible to fix c 3 (n) = max{c 3 (G ) : G simple graph on n vertices} We know that 2Enum-4-total coloring in O ⋆ (2.8285 n ). Example in Ω(2.3784 n ).Enum-3-edge coloring in O ⋆ (1.4142 n ) and a sharp example (multi-graph). Is it possible to fix c 3 (n) = max{c 3 (G ) : G simple graph on n vertices} We know that 2 Enum-4-total coloring in O ⋆ (2.8285 n ). Example in Ω(2.3784 n ). Is it possible to find the algorithm with best running time for Enum-4-total coloring.

	Enum-4-total coloring:
	Minimum vertex coloring in O ⋆ (2 n ) (A. Bjöklund, T. Husfeld Introduction Colorings and M. Koivisto, 2006)
	Algorithmic problems
	Corollary (Solving Enum-3-edge coloring:) Our results Enumerating the 3-edge colorings of a cubic graph n 2 < c 3 (n) ≤ 9 4 • 2 n 2 n 2 < c 3 (n) ≤ 9 4 • 2 n 2 n 2 < c 3 (n) ≤ 9 n 4 • 2 2
	There exists a branching algorithm with running time O ⋆ (2 The 3-edge colorings of a 3-regular graph	3n 2 ) =
	O ⋆ (2.8285 n ) and polynomial space to solve Enum-4-total coloring. Turning the proof into algorithm
	Extensions: k-edge colorings and the total colorings
	k-edge colorings
	A more precise bounds for the 3-edge coloring
	Total coloring
	Conclusion
	S. Bessy and F.Havet ()	Enumerating the edge-colourings	WGTC, Kaohsiung, 2012	38 / 41

S.

Bessy

and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012 S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012 S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

S.Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

2 n ) = O ⋆ (5.1962 n ) S.Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

2 n ) = O ⋆ (5.1962 n )Usual methods to improve: branching algorithms and dynamic programming.S.Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

n ) = O ⋆ (2.8284 n ) Polynomial space.S. Bessy and F.Havet ()Enumerating the edge-colourings WGTC, Kaohsiung, 2012

n ) = O ⋆ (2.8284 n ) min. nb of leaves Polynomial space. min. height S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Previous work: exact algorithms

What is the gain on the running time?

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Previous work: exact algorithms

Main results in exact algorithms to color a graph:

3-vertex coloring in O ⋆ (1.3289 n ) (R. [START_REF] Beigel | Previous work: exact algorithms Main results in exact algorithms to color a graph: 3-vertex coloring in O ⋆ (1.3289 n )[END_REF] Previous work: exact algorithms

Main results in exact algorithms to color a graph:

3-vertex coloring in O ⋆ (1.3289 n ) (R. [START_REF] Beigel | Previous work: exact algorithms Main results in exact algorithms to color a graph: 3-vertex coloring in O ⋆ (1.3289 n )[END_REF] Minimum vertex coloring in O ⋆ (2 n ) (A. Bjöklund, T. Husfeld and M. Koivisto, 2006) Enum-3-edge coloring

We denote by c k (G ) the number of k-edge-colorings of a graph G .

Here, we want to compute c 3 (G ), G being a sub-cubic (multiple) graph.

We can assume that G is connected.

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Enum-3-edge coloring

We denote by c k (G ) the number of k-edge-colorings of a graph G .

Here, we want to compute c 3 (G ), G being a sub-cubic (multiple) graph.

We can assume that G is connected.

Proof:

Orient from left to right.

Number of 3-edge colorings of 3-regular graphs

Proof:

Orient from left to right.

Number of 3-edge colorings of 3-regular graphs

Denote by c i the number of partial 3-edge colorings of arcs with tail in {v 1 , . . . , v i }.

Number of 3-edge colorings of 3-regular graphs

Theorem

Denote by c i the number of partial 3-edge colorings of arcs with tail in {v 1 , . . . , v i }.

Denote by c i the number of partial 3-edge colorings of arcs with tail in {v 1 , . . . , v i }.

This is sharp for multi-graphs:

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Number of k-edge colorings of k-regular graphs

We denote by c k the number of k-edge colorings of G .

Theorem

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Number of k-edge colorings of k-regular graphs

We denote by c k the number of k-edge colorings of G .

Theorem Theorem

We denote by c k the number of k-edge colorings of G .

Theorem Corollary (Solving Enum-3-edge coloring:)

There exists a branching algorithm with running time O ⋆ ((k -1!)

n

2 ) and polynomial space to solve Enum-k-edge coloring.

Proof: Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

Can we improve a lot? Not really: let H n be:

Lemma (c 3 of the ladder graph)

Number of 3-edge colorings for simple graphs

So, for simple cubic graphs, we have: Number of 3-edge colorings for simple graphs So, for simple cubic graphs, we have:

Theorem

Let G be a connected simple cubic graph. Then c 3 (G ) ≤ 9 4 • 2 n-n .

Number of 3-edge colorings for simple graphs

So, for simple cubic graphs, we have:

Theorem

Let G be a connected simple cubic graph. Then c 3 (G ) ≤ 9 4 • 2 n-n .

Proof:

We have

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

4-total colorings

Let c T 4 (G ) be the number of 4-total colorings of G . Theorem

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

4-total colorings

Let c T 4 (G ) be the number of 4-total colorings of G . Theorem

Proof:

Orient from left to right.

Denote by c i the number of partial 4-total colorings of vertices and arcs with tail in {v 1 , . . . , v i }.

4-total colorings

Theorem

Denote by c i the number of partial 4-total colorings of vertices and arcs with tail in {v 1 , . . . , v i }.

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

4-total colorings

Theorem

Denote by c i the number of partial 4-total colorings of vertices and arcs with tail in {v 1 , . . . , v i }.

4-total colorings

Theorem

Denote by c i the number of partial 4-total colorings of vertices and arcs with tail in {v 1 , . . . , v i }.

4-total colorings

Theorem

Denote by c i the number of partial 4-total colorings of vertices and arcs with tail in {v 1 , . . . , v i }. Enum-4-total coloring:

A lower bound on c T 4 , the nb of 4-total colorings: Lemma Let T be a binary tree (degree = 1 or 3) on n vertices, c T 4 (T ) = 3 • 2 3n 2 .

S. Bessy and F.Havet () Enumerating the edge-colourings WGTC, Kaohsiung, 2012

Enum-4-total coloring:

A lower bound on c T 4 , the nb of 4-total colorings: Lemma Let T be a binary tree (degree = 1 or 3) on n vertices, c T 4 (T ) = 3 • 2 3n 2 .

Proof: by induction:

Enum-4-total coloring:

A lower bound on c T 4 , the nb of 4-total colorings: Lemma Let T be a binary tree (degree = 1 or 3) on n vertices, c T 4 (T ) = 3 • 2 3n 2 .

Proof: by induction:

Enum-4-total coloring:

A lower bound on c T 4 , the nb of 4-total colorings: Lemma Let T be a binary tree (degree = 1 or 3) on n vertices, c T 4 (T ) = 3 • 2 3n 2 .

Proof: by induction: Enum-4-total coloring:

A lower bound on c T 4 , the nb of 4-total colorings: Lemma Let T be a binary tree (degree = 1 or 3) on n vertices, c T 4 (T ) = 3 • 2 3n 2 .

Proof: by induction: