text:
# A Family of Quasi-solvable Quantum Many-body Systems

## I Introduction

New findings of solvable or integrable models have stimulated development of new and wide research directions and ideas in both physics and mathematics. The discovery of quasi-solvability in quantum mechanics TuUs1  is a typical example. By quasi-solvability we mean that a part of the spectra can be solved, at least, algebraically111The term  quasi-exact solvability has been widely used in this meaning. However, we keep it to express the case where the state vectors corresponding to the solvable spectra are normalizable. Importance of this distinction is explained in Refs. AST2 ; ST1 . One of the most successful approach to construct a quasi-solvable model is the algebraic method introduced by Turbiner in 1988 Turbi1 , in which a family of quasi-solvable one-body models was constructed by the $`𝔰𝔩(2)`$ generators on a polynomial space. This family was later completely classified under the consideration of the $`GL(2,)`$ invariance of the models LoKaOl3 ; LoKaOl4 . Recently, this family have been paid much attention to in the context of $`𝒩`$-fold supersymmetry AKOSW2 ; ASTY ; AST1 ; KlPl2 ; KlPl3 ; DoDuTa1 ; DoDuTa2 ; AST2 ; ANST1 ; ANST2 ; ST1 ; Tanak2 . Several attempts were made to construct quasi-solvable many-body models by naive extension to higher-rank algebras. Especially, construction of two-body problems by the rank 2 algebras was extensively investigated LoKaOl4 ; ShTu1 ; Shifm1 ; LoKaOl1 ; LoKaOl2 ; Turbi2 ; Ushve . These approaches however led to Schrödinger operators in curved space in general and could hardly apply to $`M`$-body ($`M>2`$) problems.

In 1995, a significant progress was made in Ref. RuTu1 , where the exact solvability of the rational and trigonometric $`A`$ type Calogero–Sutherland (CS) models Calog1 ; Suthe1 ; Moser1  for any finite number of particles were shown by a similar algebraic method. The key ingredient is the introduction of the elementary symmetric polynomials which reflect the permutation symmetry of the original models. The algebra for the $`M`$-body system is $`𝔰𝔩(M+1)`$. This idea was further applied to show the exact solvability of the rational and trigonometric $`A`$ and $`BC`$ type CS models and their supersymmetric generalizations BrTuWy1 , and to show the quasi-exact solvability of various deformed CS models MiRoTu1 ; HoSh1 . Therefore, one can say the approach starting from Ref. RuTu1  is, up to now, the most successful in investigating quasi-solvable quantum many-body problems. However, one has not yet known all the models that can be obtained by this approach. In other words, we have not obtained the classification of these $`𝔰𝔩(M+1)`$ $`M`$-body models like that of the $`𝔰𝔩(2)`$ one-body models. Recently, this classification problem was partly accessed in Ref. UlLoRo1  though, as was stressed by the authors themselves, the results depend on the specific ansatz and thus are incomplete. In this Letter, we will show the complete classification of the quantum many-body systems with up to two-body interactions which can be constructed by the $`𝔰𝔩(M+1)`$ method.

## II Construction of the Models

Consider an $`M`$-body quantum Hamiltonian,

$`H_𝒩={\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle \frac{^2}{q_i^2}}+V(q_1,\mathrm{},q_M),`$ (1)
which possesses permutation symmetry, that is,

$`V(\mathrm{},q_i,\mathrm{},q_j,\mathrm{})=V(\mathrm{},q_j,\mathrm{},q_i,\mathrm{}),`$ (2)
for $`ij`$. To algebraize the Hamiltonian (1), we will proceed the following three steps. At first, we make a gauge transformation on the Hamiltonian (1):

$`\stackrel{~}{H}_𝒩=e^{𝒲(q)}H_𝒩e^{𝒲(q)}.`$ (3)
The function $`𝒲(q)`$ is to be determined later and plays the role of the superpotential when the system Eq. (1) is supersymmetric. As in Eq. (3), we will hereafter attach tildes to both operators and vector spaces to indicate that they are quantities gauge-transformed from the original ones. In the next, we change the variables $`q_i`$ to $`h_i`$ by a function $`h`$ of a single variable; $`h_i=h(q_i)`$. Note that the way of changing of the variables preserves the permutation symmetry. The third step is the introduction of elementary symmetric polynomials of $`h_i`$ defined by,

$`\sigma _k(h)={\displaystyle \underset{i_1<\mathrm{}<i_k}{}}h_{i_1}\mathrm{}h_{i_k}(k=1,\mathrm{},M),`$ (4)
from which we further change the variables to $`\sigma _i`$. Then, we choose a set of components of the $`𝒩`$-fold supercharges in terms of the above variables $`\sigma _i`$ as follows:

$`\stackrel{~}{P}_𝒩^{\{i\}}={\displaystyle \frac{^𝒩}{\sigma _{i_1}\mathrm{}\sigma _{i_𝒩}}}(1i_1\mathrm{}i_𝒩M),`$ (5)
where $`\{i\}`$ is an abbreviation of the set $`\{i_1,\mathrm{},i_𝒩\}`$. Using these $`𝒩`$-fold supercharges, we define the vector space $`\stackrel{~}{𝒱}_𝒩_{\{i\}}\mathrm{ker}\stackrel{~}{P}_𝒩^{\{i\}}`$ , which now becomes,

$`\stackrel{~}{𝒱}_𝒩=\text{span }\{\sigma _1^{n_1}\mathrm{}\sigma _M^{n_M}:0_{i=1}^Mn_i𝒩1\}.`$ (6)
For given $`M`$ and $`𝒩`$, the dimension of the vector space (6) becomes,

$`dim\stackrel{~}{𝒱}_𝒩={\displaystyle \underset{n=0}{\overset{𝒩1}{}}}{\displaystyle \frac{(n+M1)!}{n!(M1)!}}={\displaystyle \frac{(𝒩+M1)!}{(𝒩1)!M!}}.`$ (7)
We will construct the system (3) to be quasi-solvable so that the solvable subspace is given by just Eq. (6). This can be achieved by imposing the following quasi-solvability condition AST2 ; ANST1 ; Tanak2 ,

$`\stackrel{~}{P}_𝒩^{\{i\}}\stackrel{~}{H}_𝒩\stackrel{~}{𝒱}_𝒩=0\text{for}\{i\}.`$ (8)
The general solution of Eq. (8) can be obtained in completely the same way as shown in Refs. ANST1 ; Tanak2 . As in the case of the one-body models, it is sufficient to find differential operators up to the second-order as solutions for $`\stackrel{~}{H}_𝒩`$ since we are constructing a Schrödinger operator in the original variables $`q_i`$. It turns out that the general solution which contains up to the second derivatives takes the following form,

$`\stackrel{~}{H}_𝒩={\displaystyle \underset{\kappa ,\lambda ,\mu ,\nu =0}{\overset{M}{}}}A_{\kappa \lambda ,\mu \nu }E_{\kappa \lambda }E_{\mu \nu }+{\displaystyle \underset{\kappa ,\lambda =0}{\overset{M}{}}}B_{\kappa \lambda }E_{\kappa \lambda }C,`$ (9)
where $`A_{\kappa \lambda ,\mu \nu }`$, $`B_{\kappa \lambda }`$, $`C`$ are arbitrary constants, and $`E_{\kappa \lambda }`$ are the first-order differential operators which constitute the Lie algebra $`𝔰𝔩(M+1)`$:

$`E_{0i}`$ $`=`$ $`{\displaystyle \frac{}{\sigma _i}},E_{ij}=\sigma _i{\displaystyle \frac{}{\sigma _j}},`$ (10a)
$`E_{i0}`$ $`=`$ $`\sigma _iE_{00}=\sigma _i\left(𝒩1{\displaystyle \underset{k=1}{\overset{M}{}}}\sigma _k{\displaystyle \frac{}{\sigma _k}}\right).`$ (10b)
If we explicitly express the general solution (9) in terms of $`\sigma _i`$, we obtain the following expression,

$`\stackrel{~}{H}_𝒩`$ $`=`$ $`{\displaystyle \underset{k,l=1}{\overset{M}{}}}\left[𝑨_0(\sigma )\sigma _k\sigma _l𝑨_k(\sigma )\sigma _l+𝑨_{kl}(\sigma )\right]{\displaystyle \frac{^2}{\sigma _k\sigma _l}}`$ (11)
$`+{\displaystyle \underset{k=1}{\overset{M}{}}}\left[𝑩_0(\sigma )\sigma _k𝑩_k(\sigma )\right]{\displaystyle \frac{}{\sigma _k}}𝑪(\sigma ),`$
where $`𝑨_\kappa `$, $`𝑨_{kl}`$, $`𝑩_\kappa `$ and $`𝑪`$ are second-degree polynomials of several variables.

One of the most difficult problems one would come across in the algebraic approach to the quasi-solvable quantum many-body systems is to solve the canonical-form condition:

$`H_𝒩=e^{𝒲(q)}\stackrel{~}{H}_𝒩e^{𝒲(q)}={\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle \frac{^2}{q_i^2}}+V(q).`$ (12)
If the Hamiltonian (11) is gauge-transformed back to the original one, it in general does not take the canonical form of the Schrödinger operator like Eq. (1) and one can hardly solve, for arbitrary $`M`$, the conditions under which a gauge-transform of Eq. (11) could be cast in the Schrödinger form. This difficulty can, however, be partly overcome by the following observation. Suppose we can solve the canonical-form condition for an $`M`$ and obtain a quasi-solvable $`M`$-body Hamiltonian constructed from the $`𝔰𝔩(M+1)`$ generators, which would have the following form:

$`H_𝒩={\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle \frac{^2}{q_i^2}}+{\displaystyle \underset{i=1}{\overset{M}{}}}V_1(q_i)+{\displaystyle \underset{i<j}{\overset{M}{}}}V_2(q_i,q_j)+\mathrm{}+V_M(q_1,\mathrm{},q_M).`$ (13)
Then, we can get a quasi-solvable $`M`$-body model with up to the two-body interactions if we turn off all the coupling constants of the interactions except for the one- and two-body ones:

$`H_𝒩={\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle \frac{^2}{q_i^2}}+{\displaystyle \underset{i=1}{\overset{M}{}}}V_1(q_i)+{\displaystyle \underset{i<j}{\overset{M}{}}}V_2(q_i,q_j).`$ (14)
The resultant model (14) should be, when we put $`M=2`$, identical with one of the two-body models constructed from the $`𝔰𝔩(3)`$ generators. This comes from the fact that the gauged Hamiltonian (11) constructed from the $`𝔰𝔩(M+1)`$ generators reduces to the one constructed from the $`𝔰𝔩(3)`$ generators if we put $`M=2`$ and $`h_i=0`$ for $`i>2`$.

Therefore, as far as up to two-body interactions are concerned, it is sufficient to solve the $`M=2`$ case by virtue of the permutation symmetric construction. We have found that we can actually solve the canonical-form condition for $`M=2`$ and that $`\stackrel{~}{H}_𝒩`$ for $`M2`$ must have the following expression in terms of the variables $`h_i`$,

$`\stackrel{~}{H}_𝒩(h)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{M}{}}}P(h_i){\displaystyle \frac{^2}{h_i^2}}`$ (15)
$`{\displaystyle \underset{i=1}{\overset{M}{}}}\left[Q(h_i){\displaystyle \frac{𝒩2+(M1)c}{2}}P^{}(h_i)\right]{\displaystyle \frac{}{h_i}}`$
$`2c{\displaystyle \underset{ij}{\overset{M}{}}}{\displaystyle \frac{P(h_i)}{h_ih_j}}{\displaystyle \frac{}{h_i}}𝑪\left(\sigma (h)\right),`$
where $`𝑪`$ is given by,

$`𝑪\left(\sigma (h)\right)`$ $`=`$ $`{\displaystyle \frac{𝒩1}{12}}\left[𝒩2+2(M1)c\right]{\displaystyle \underset{i=1}{\overset{M}{}}}P^{\prime \prime }(h_i)`$ (16)
$`{\displaystyle \frac{𝒩1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}Q^{}(h_i){\displaystyle \frac{𝒩1}{2}}c{\displaystyle \underset{ij}{\overset{M}{}}}{\displaystyle \frac{P^{}(h_i)}{h_ih_j}}+R.`$
The $`P`$ and $`Q`$ in Eqs. (15) and (16) are a fourth- and a second-degree polynomial, respectively:

$`P(h)`$ $`=`$ $`a_4h^4+a_3h^3+a_2h^2+a_1h+a_0,`$ (17a)
$`Q(h)`$ $`=`$ $`b_2h^2+b_1h+b_0.`$ (17b)
Thus, there are 10 parameters $`a_n`$, $`b_n`$, $`c`$, $`R`$, which characterize the quasi-solvable Hamiltonian (15). One can prove the quasi-solvability of the operator (15) by the convertibility of it into the form (11). The function $`h(q)`$, which determines the change of variables, is given by a solution of the differential equation,

$`h^{}(q)^2=2P\left(h(q)\right).`$ (18)
One may notice that the resultant Eqs. (15)–(18) have resemblance to those of the one-body quasi-solvable models constructed from $`𝔰𝔩(2)`$ generators Turbi1 ; LoKaOl3 ; LoKaOl4 , or equivalently, the type A $`𝒩`$-fold supersymmetric models ANST1 ; ANST2 ; Tanak2 . Indeed, we can easily see that the above results reduce to the one-body $`𝔰𝔩(2)`$ quasi-solvable and type A $`𝒩`$-fold supersymmetric models if we set $`M=1`$, where the double summation is understood as $`_{ij}^10`$. This is consistent with the fact that in the case of $`M=1`$ the above procedure is essentially equivalent to that in the $`𝔰𝔩(2)`$ construction of type A $`𝒩`$-fold supersymmetry ANST1 ; Tanak2 . Under the above conditions (15)–(18) satisfied, the original Hamiltonian becomes the following Schrödinger type,

$`H_𝒩={\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle \frac{^2}{q_i^2}}+{\displaystyle \frac{1}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}\left[\left({\displaystyle \frac{𝒲(q)}{q_i}}\right)^2{\displaystyle \frac{^2𝒲(q)}{q_i^2}}\right]𝑪\left(\sigma (h)\right),`$ (19)
and the superpotential $`𝒲(q)`$ is given by,

$`𝒲(q)={\displaystyle \underset{i=1}{\overset{M}{}}}{\displaystyle 𝑑h_i\frac{Q(h_i)}{2P(h_i)}}+{\displaystyle \frac{𝒩1+(M1)c}{2}}{\displaystyle \underset{i=1}{\overset{M}{}}}\mathrm{ln}\left|h_i^{}\right|c{\displaystyle \underset{i<j}{\overset{M}{}}}\mathrm{ln}\left|h_ih_j\right|.`$ (20)
It is evident by the construction that the solvable wave functions $`\psi (q)`$ of the Hamiltonian (19) take the following form,

$`\psi (q)=\stackrel{~}{\psi }(q)e^{𝒲(q)},\stackrel{~}{\psi }(q)\stackrel{~}{𝒱}_𝒩.`$ (21)
The Hamiltonian (19) with Eqs. (16) and (20) is the most general quasi-solvable many-body systems with two-body interactions which can be constructed from the $`𝔰𝔩(M+1)`$ generators (10).

Before investigating what kind of particular models emerges from the general Hamiltonian (19), we will refer to an interesting feature of the result. If the algebraic Hamiltonian (9) does not contain any raising operator $`E_{i0}`$, it preserves the vector space $`\stackrel{~}{𝒱}_𝒩`$ for arbitrary $`𝒩`$ and becomes not only a quasi-solvable but also a solvable model Turbi2 ; Ushve . In this case, it turns out that $`𝑪(\sigma )=C`$, one of the constants involved in Eq. (9), and thus the original Hamiltonian (19) becomes supersymmetric Witte1 ; Witte2 . A system is always quasi-solvable if it is supersymmetric, since the ground state is always solvable. From the above result, we can conclude that a system is always supersymmetric if it is solvable and all its states have the form (21).

## III Classification of the Models

It was shown that the one-body $`𝔰𝔩(2)`$ quasi-solvable models can be classified using the shape invariance of the Hamiltonian under the action of $`GL(2,)`$ of linear fractional transformations LoKaOl3 ; LoKaOl4 . We can see that the many-body Hamiltonian (15) also has the same property of shape invariance. The linear fractional transformation of $`h_i`$ is introduced by,

$`h_i\widehat{h}_i={\displaystyle \frac{\alpha h_i+\beta }{\gamma h_i+\delta }}(\mathrm{\Delta }\alpha \delta \beta \gamma 0).`$ (22)
Then, it turns out that the Hamiltonian (15) is shape invariant under the following transformation induced by Eq. (22),

$`\stackrel{~}{H}_𝒩(h)\widehat{\stackrel{~}{H}}_𝒩(h)={\displaystyle \underset{i=1}{\overset{M}{}}}(\gamma h_i+\delta )^{𝒩1}\stackrel{~}{H}_𝒩(\widehat{h}){\displaystyle \underset{i=1}{\overset{M}{}}}(\gamma h_i+\delta )^{(𝒩1)},`$ (23)
where the polynomials $`P(h)`$ and $`Q(h)`$ in the $`\stackrel{~}{H}_𝒩(h)`$ are transformed according to,

$`P(h)\widehat{P}(h)=\mathrm{\Delta }^2(\gamma h+\delta )^4P(\widehat{h}),`$ (24a)
$`Q(h)\widehat{Q}(h)=\mathrm{\Delta }^1(\gamma h+\delta )^2Q(\widehat{h}).`$ (24b)
For a given $`P(h)`$, the function $`h(q)`$ is determined by Eq. (18) and a particular model is obtained by substituting this $`h(q)`$ for Eqs. (16), (19) and (20). Under the transformation (24a) of $`GL(2,)`$, every real quartic polynomial $`P(h)`$ is equivalent to one of the following eight forms:

$`\text{1). }{\displaystyle \frac{1}{2}},\text{2). }2h,\text{3). }2\nu h^2,\text{4). }2\nu (h^21),`$
$`\text{5). }2\nu (h^2+1),\text{6). }{\displaystyle \frac{\nu }{2}}(h^2+1)^2,`$
$`\text{7). }2h^3{\displaystyle \frac{g_2}{2}}h{\displaystyle \frac{g_3}{2}},\text{8). }{\displaystyle \frac{\nu }{2}}(h^2+1)\left[(1k^2)h^2+1\right].`$
where $`\nu `$, $`k`$, $`g_2`$ and $`g_3`$ are all real numbers satisfying $`\nu 0`$, $`0<k<1`$ and $`g_2^327g_3^20`$. Thus, the quasi-solvable models (19) can be classified into the above eight cases.

Case 1). $`h(q)=q`$:

This leads to the rational $`A`$ type Inozemtsev model Inoze1 ; InMe1 ; Inoze3 . Inozemtsev models are known as a family of deformed CS models which preserve the classical integrability. The main difference between quantum and classical case is that the quantum quasi-solvability holds only for quantized values of the parameter, say, for integer $`𝒩`$, while the classical integrability holds for continuous values. This is one of the common features that the quantum quasi-solvable models share.

Case 2). $`h(q)=q^2`$:

This leads to the rational $`BC`$ type Inozemtsev model. The quasi-exactly solvable model reported in Ref. HoSh1  is just this case.

Case 3). $`h(q)=e^{2\sqrt{\nu }q}`$:

This leads to the hyperbolic ($`\nu >0`$) and trigonometric ($`\nu <0`$) $`A`$ type Inozemtsev model.

Case 4). $`h(q)=\mathrm{cosh}2\sqrt{\nu }q`$:

This leads to the hyperbolic ($`\nu >0`$) and trigonometric ($`\nu <0`$) $`BC`$ type Inozemtsev model. The quasi-solvability of the special cases of the above four were recently shown in Ref. SaTa1  by an ansatz method.

Case 5). $`h(q)=\mathrm{sinh}2\sqrt{\nu }q`$:

This leads to a hyperbolic model being neither the Inozemtsev nor the Olshanetsky–Perelomov type OlPe2 . The paper Ref. UlLoRo1  covers most of the above five models.

Case 6). $`h(q)=\mathrm{tan}\sqrt{\nu }q`$:

This leads to a trigonometric model being neither the Inozemtsev nor the Olshanetsky–Perelomov type.

Case 7). $`h(q)=\mathrm{}(q;g_2,g_3)`$:

This case includes the elliptic $`BC`$ type Inozemtsev model and the twisted CS models HoPh1 ; HoPh2 ; BoSa1 . The elliptic model in Ref. UlLoRo2  may be also included in this case.

Case 8). $`h(q)=\text{sn }(\sqrt{\nu }q|k)/\text{cn }(\sqrt{\nu }q|k)`$:

This leads to an elliptic model being neither the Inozemtsev nor the Olshanetsky–Perelomov type.

The two-body potentials in all the cases have singularities at $`q_i=q_j(ij)`$. Thus, each of the models is naturally defined on a Weyl chamber if the potential is non-periodic or on a Weyl alcove if the potential is periodic OlPe2 . Cases 1–5 with $`\nu >0`$ and Case 6 with $`\nu <0`$ correspond to the former while the others to the latter. In the latter case, a system can be quasi-exactly solvable unless a pole of a one-body potential in the system exists and is in the Weyl alcove. On the other hand, quasi-exact solvability in the former case depends mainly on the asymptotic behavior of Eq. (21) at $`|q_i|\mathrm{}`$. Since this behavior is in general not dominated by the two-body term in the r.h.s. of Eq. (20), most of the results on the normalizability of the one-body $`𝔰𝔩(2)`$ quasi-solvable models in Ref. LoKaOl3  may also hold for our models.

More details on the results presented here and further development will be reported in the near future Tanak3 .

###### Acknowledgements.

We would like to thank H. Aoyama, N. Nakayama, R. Sasaki, M. Sato, K. Takasaki and S. Yamaguchi for useful discussions. We would also like to thank A. González-López for crucial comments. This work was supported in part by a JSPS research fellowship.


format: text

text:
# Evidence for Spin and Energy Extraction in a Galactic Black Hole Candidate: The XMM-Newton/EPIC-pn Spectrum of XTE J1650-500

## 1. Introduction

The accretion flow geometry in stellar-mass black holes may change considerably with the mass accretion rate ($`\dot{m}`$). Characteristic periods of correlated intensity, energy spectral hardness, and fast variability in the X-ray band are identified as “states” (for a review, see Tanaka & Lewin 1995; see also Homan et al. 2001). These states are observed in all stellar-mass black holes, and are thought to be driven primarily by changes in $`\dot{m}`$.

Of five common states, the “very high” state is perhaps the least-understood. Often the first state observed in a transient outburst and usually very luminous, a variety of phenomena are observed that indicate a unique inner accretion flow environment. Fast quasi-periodic oscillations (QPOs; 30–450 Hz) — if tied to the Keplerian frequency of the inner accretion disk — indicate accretion disks which extend close to the marginally stable circular orbit for a Schwarzschild black hole, and may even indicate black hole spin (e. g., Strohmayer 2001, Miller et al. 2001a). Discrete jet ejections are sometimes observed in the radio band with velocities that approach $`c`$ (for a review, see Fender 2001). The X-ray energy spectra observed in the very high state are a mix of thermal and non-thermal components. The spectra suggest a disk which may extend close to the black hole, and a corona (the assumed non-thermal source) which irradiates the disk and produces a “reflection” spectrum (George & Fabian 1991; see also Gierlinski et al. 1999).

With adequate spectral resolution, Fe K$`\alpha `$ line profiles may provide effective tools for constraining the nature of accretion flows (e. g. Miller et al. 2002) in stellar-mass black holes. Such profiles have been used to infer black hole spin and rotational energy extraction via magnetic fields in active galactic nuclei (AGNs; Iwasawa et al. 1996, Wilms et al. 2001). Evidence for spin, based on Fe K$`\alpha `$ line profiles, has also been reported in stellar-mass black holes, but with gas proportional counters offering lower resolution and inhibiting stronger conclusions (Balucinska-Church & Church 2000, Miller et al. 2001b, Campana et al. 2002). The high effective area of XMM-Newton and short frame times available with the EPIC-pn camera are well-suited to capturing high resolution spectra of bright sources.

We were granted a target-of-opportunity observation to study the Galactic black hole candidate XTE J1650$``$500 (Remillard 2001) early in its Fall, 2001 outburst. Although a neutron star primary can only be ruled-out by optical radial velocity measurements, there is strong evidence in X-rays that XTE J1650$``$500 harbors a black hole. Based on the spectrum we obtained with XMM-Newton and timing properties (Wijnands, Miller, & Lewin 2001), we observed XTE J1650$``$500 in the very high state — the first pile-up-free CCD spectrum of a stellar-mass black hole in this state. Herein, we report the detection of a broad Fe K$`\alpha `$ line. We discuss the implications of this line for the accretion flow geometry in this source, and explore connections to the recent XMM-Newton observation of the Seyfert-I AGN MCG–6-30-15 (Wilms et al. 2001).

## 2. Observation and Data Reduction

We observed XTE J1650$``$500 with XMM-Newton on 13 September, 2001, from 15:45:25–21:41:04 (UT) for a total exposure of 21.4 ks. We did not operate the EPIC-MOS2 camera or the Optical Monitor to preserve telemetry. The EPIC-MOS1 camera was operated in timing mode but suffered a full scientific buffer nearly continuously due to the high flux. Full spectral results from the Reflection Grating Spectrometer (RGS, 0.33–2.5 keV) will be reported in a separate paper. To prevent photon pile-up, the EPIC-pn camera was operated in “burst” mode with the “thin” optical filter in place (for more information on the pn camera, see Stüder et al. 2001). Only one CCD of the pn camera is active in burst mode, and spatial information is only recorded in one dimension. Burst mode has a time resolution of 7 $`\mu `$s, but a duty cycle of approximately 3%.

We extracted source counts using a box region centered on the source position (with X an Y half-widths of 1694 and 28, respectively, in DET units). Two background regions adjacent to the source position were selected. Single and double events were included for analysis. Standard pn filtering was accomplished with the procedure XMMEA\_EP, assuming a source position of $`16^{}50^{}01.0^{\prime \prime },49^h57^m45^s`$ (Castro-Tirado et al. 2001; Groot et al. 2001). We measured a source count rate of $`2557.0\pm 1.9`$ counts s-1, and a background count rate of $`151.5\pm 0.5`$ counts s-1. Calibrated event lists were custom-made at MPE using SAS–5.3$`\alpha `$. The source and background spectra were created with SAS–5.2.0. Spectra were grouped based both on a requirement for counts per channel (20) and on the maximum number of spectral channels sampling the pn energy resolution (3).

This is the first spectral analysis to be reported from an observation which employed burst mode. Despite the peculiarities of this mode, the instrumental effective area and the energy response, and charge transfer inefficiency (CTI) correction do not differ from more standard modes (Kirsch et al. 2002). Therefore, “full frame” mode response matrices were created to model the instrument response using SAS–5.2.0.

The spectral fits reported herein were made using XSPEC version 11.1.0 (Arnaud 1996). Quoted errors correspond to $`\mathrm{\Delta }\chi ^2=1.0`$. Below 0.5 keV and above 10.0 keV, deviations were seen in the residuals regardless of the spectral model used. We therefore restricted our analysis to the 0.5–10.0 keV band. We note a feature at 2.34 keV which appears as an emission line. The detector effective area changes sharply at this energy and the line is well-fit by a zero-width Gaussian, suggesting that the feature is instrumental.

## 3. Analysis and Results

In examining the EPIC-pn and RGS data of XTE J1650$``$500, we find oxygen to be $`13_5^{+1}`$% under-abundant, neon to be $`16_6^{+8}`$% over-abundant, and iron to be $`45\pm 5`$% under-abundant relative to solar values along this line of sight (assuming abundances as measured by Anders & Grevesse 1989). The RGS spectrum reveals that the oxygen edge location is more consistent with 0.536 keV than the expected 0.532 keV; this has also been noted in fits to Chandra data of Cygnus X-1 (Schulz et al. 2001, Miller et al. 2002). We therefore fixed the oxygen edge to be at 0.536 keV in all fits. All other elements are found to have abundances consistent with solar values.

Absorption in the ISM was modeled using the “vphabs” model in XSPEC (with the abundance of oxygen set to zero,

and an additional edge to model the oxygen absorption at 0.536 keV). We measure an effective neutral hydrogen column density of $`N_H=7.8\pm 0.2\times 10^{21}`$ atoms cm-2.

Fits with the standard multicolor accretion disk black body (hereafter, MCD; Mitusda et al. 1984) plus power-law model to the 0.5–10.0 keV spectrum were statistically unacceptable ($`\chi ^2=513.4`$ for 233 d.o.f.). The data/model ratio for this model is shown in Figure 1. The emission line profile in this data/model ratio is similar to that observed in Cygnus X-1 with the Chandra High Energy Transmission Grating Spectrometer (Miller et al. 2002), and similar to line profiles seen in some AGNs with ASCA (see, e. g., Iwasawa et al. 1996; Weaver, Gelbord, & Yaqoob 2001).

Gaussian emission line and smeared edge (see Ebisawa et al. 1994) components were added to the model. The addition of these components improved the fit significantly ($`\chi ^2=314.8`$ for 225 d.o.f.). Using this model, we measure an inner disk color temperature of $`kT=0.322\pm 0.004`$ keV, and an MCD normalization of $`3.9_{1.3}^{+0.3}\times 10^4`$. The measured power-law index is $`\mathrm{\Gamma }=2.09_{0.09}^{+0.03}`$; the normalization of this component is measured to be $`3.1\pm 0.2`$ ph cm-2 s-1 keV-1 at 1 keV. The 0.5–10.0 keV flux of the MCD component is $`0.36_{0.12}^{+0.03}\times 10^8`$ erg cm-2 s-1, and that for the power-law component is $`1.17\pm 0.08\times 10^8`$ erg cm-2 s-1.

The best-fit Gaussian indicates a broad line, shifted from the neutral Fe K$`\alpha `$ line energy of 6.40 keV: E$`=5.3_{0.3}^{+0.1}`$ keV, FWHM$`=3.2_{0.6}^{+0.8}`$ keV, and W$`=250\pm 50`$ eV. The edge is measured to be at E$`=6.8\pm 0.3`$ keV, with a depth of $`\tau =0.5\pm 0.1`$. However, significant residuals remain in the Fe K$`\alpha `$ line region with this fit, due in part to the non-Gaussian nature of the line profile (see Figure 1). Moreover, on a broader energy range (one that includes the 20–30 keV “Compton hump” seen in many sources), a reflection model is often required to fit the spectra of stellar-mass black holes (see, e.g., Gierlinski et al. 1999). Broad Gaussian and smeared edge components are merely an approximation to a full reflection model in the 0.5–10.0 keV band. Therefore, we now focus on the results of fitting more sophisticated, physically-motivated reflection models. These replace the hard power-law, Gaussian, and smeared edge components discussed above.

Anticipating a highly-ionized accretion disk, we made fits with the “constant density ionized disk” reflection model (hereafter, CDID; Ross, Fabian, & Young 1999). This model measures the relative strengths of the directly-observed and reflected flux, the accretion disk ionization parameter ($`\xi =L_X/nR^2`$, where $`L_X`$ is the X-ray luminosity, $`n`$ is the hydrogen number density, and $`R`$ is radius), and the photon index of the illuminating power-law flux. Fe K$`\alpha `$ line emission and line broadening due to Comptonization in an ionized disk surface layer are included in this model.

The fit obtained with this model is shown in the top panel of Figure 2. The photon index of the irradiating power law is measured to be $`\mathrm{\Gamma }=2.08_{0.04}^{+0.02}`$. The ionization parameter is high: $`\xi =1.3_{0.1}^{+0.7}\times 10^4`$ erg cm s-1, and the relative strength of reflected flux is measured to be $`f=0.5_{0.1}^{+0.7}`$ (where $`F_{total}=F_{direct}+f\times F_{refl.}`$). While the shape of the Fe K edge is reproduced by this model, the width and shape of the Fe K$`\alpha `$ line is not, and a statistically-poor fit is obtained ($`\chi ^2=399.7`$ for 231 d.o.f.). The ionization parameter obtained with this model corresponds to a mixture of helium-like and hydrogenic ion species of Fe (Kallman and McCray 1982).

As Doppler shifts and general relativistic smearing may be expected for lines produced in an accretion disk close to the black hole, we next made fits after convolving (or, “blurring”) the CDID model with the line element expected near a Kerr black hole. We assumed an inner disk radius of 1.24 $`R_g`$, an outer line production radius of 400 $`R_g`$, and an inclination of $`i=45^{}`$ (in fits with this and other models, intermediate inclinations were marginally preferred in terms of $`\chi ^2`$). With this blurred model, we obtained parameter constraints which differed marginally from the previous fit: $`\xi =2.5_{0.1}^{+5.5}\times 10^4`$ erg cm s-1, $`f=0.6_{0.1}^{+0.6}`$, and $`\mathrm{\Gamma }=1.96_{0.06}^{+0.04}`$. The shape and strength of the Fe K$`\alpha `$ line are not fit adequately; the fit is slightly worse than the un-blurred model ($`\chi ^2=407.8`$, 231 d.o.f.).

Finally, we constructed a model which allows the Fe K$`\alpha `$ line and reflection components to be treated separately. We fit the line with the “Laor” line model (Laor 1991), and the power-law and reflection continuum (minus the line) with the “pexriv” model (Magdziarz & Zdziarski 1995). With pexriv, $`f=1`$ corresponds to a disk which intercepts half of the incident power-law flux. It should be noted that this model was also used by Wilms et al. (2001) in fits to the XMM-Newton/EPIC spectrum of the Seyfert galaxy MCG–6-30-15, allowing for a direct comparison. For the Laor line, we initially fixed the inner disk edge at 1.24 $`R_g`$, the outer line production region at 400 $`R_g`$, and the inclination at $`i=45^{}`$. The line energy, emissivity profile ($`ϵr^\beta `$; we fit for $`\beta `$), and intensity were allowed to vary. The MCD and pexriv reflection components were blurred as before.

We found that the data could not simultaneously constrain $`f`$, $`\xi `$, and the disk surface temperature with pexriv (an additional

parameter for this model). We therefore fixed the ionization parameter at $`\xi =2.0\times 10^4`$ erg cm s-1, and the disk surface temperature at $`kT=1.3`$keV (as per Ross, Fabian, & Young 1999 in fits to Cygnus X-1, wherein a similarly low MCD disk temperature but similarly high values of $`\xi `$ are reported).

The fit obtained with this model is shown in the bottom panel of Figure 2. Statistically, this model represents a significant improvement ($`\chi ^2=319.9`$ for 229 d.o.f.). A power-law index of $`\mathrm{\Gamma }=2.04_{0.02}^{+0.03}`$ is obtained. We measure the Fe K$`\alpha `$ line to be centered at E$`=6.8_{0.1}^{+0.2}`$ keV, likely due to a blend of Fe XXV and Fe XXVI (helium-like and hydrogenic Fe) and consistent with the high ionization parameters previously measured. The line is strong, with an equivalent width of W$`=350_{40}^{+60}`$ eV and a flux of $`2.2\pm 0.3\times 10^{10}`$ erg cm-2 s-1 ($`3.2\pm 0.4\times 10^2`$ ph cm-2 s-1). When the inner disk edge is allowed to vary, an inner radius of 1.24 $`R_g`$ (the limit of the Laor model, corresponding to $`a=0.998`$) is preferred over an inner radius of 6.0 $`R_g`$ (the marginally stable circular orbit around a Schwarzschild black hole) at the 6$`\sigma `$ level of confidence. A steep emissivity is suggested via the Laor line model: $`\beta =5.4\pm 0.5`$. This emissivity is preferred over that for a standard accretion disk ($`\beta =3.0`$) at the 5.6$`\sigma `$ level of confidence. The pexriv reflection “fraction” is $`f=0.6_{0.1}^{+0.3}`$. This is consistent with the reflection fractions measured in the high state of Cygnus X-1 (Gierlinski et al. 1999), wherein the disk may extend to the marginally stable circular orbit.

It is not likely that these results can be explained in terms of an anomalous Fe abundance. Allowing $`\beta `$ and $`A_{Fe}`$ (in pexriv) to vary, the abundance is poorly constrained: $`A_{Fe}=1.0_{0.7}^{+0.5}`$, and the emissivity drops only slightly to $`\beta =5.0`$. Fixing the emissivity at $`\beta =3.0`$ and allowing the Fe abundance to vary yields a significantly worse fit ($`\chi ^2=353.1`$ for 229 d.o.f.) and Fe must be more than 30 times over-abundant. We note that the line strength and reflection fraction in our final fit are not strictly congruent, and that $`f=0.6_{0.1}^{+0.3}`$ is below the reflection fraction measured in MCG–6-30-15 ($`f=1.52.0`$, Wilms et al. 2001) using a similar model. If we fix the $`f=1.5`$ in our final model, $`\chi ^2`$ increases only slightly ($`\chi ^2=324.9`$ for 230 d.o.f.), and the other fit parameters only change within their 1$`\sigma `$ confidence intervals. Thus, more congruent values of $`f`$ are allowed by the data.

The high $`\chi ^2`$ value associated with our final model could be due to unmodeled narrow spectral features, approximations in the model, and calibration issues. We note a feature at approximately 7.0 keV, which may be a narrow edge due to neutral Fe or an Fe XXVI absorption line. Alternatively, there may be an Fe K$`\beta `$ emission line near 7.4 keV due to ionized Fe species, which is superimposed upon the broader smeared edge fit by the reflection models. There is also weak evidence for a narrow absorption edge feature near 9.3 keV, consistent with Fe XXVI. Modeling these features and the addition of 0.5% systematic errors below 1 keV are sufficient to make the fit acceptable.

## 4. Discussion

We have observed a broad Fe K$`\alpha `$ line profile in the XMM-Newton/EPIC-pn spectrum of the Galactic black hole candidate XTE J1650$``$500 in the very high state. A comparison with the broad line profile observed with Chandra in Cygnus X-1 is shown in Figure 1. That such profiles are observed in very different systems, strongly suggests that broad Fe K$`\alpha `$ lines in stellar-mass black holes stem from a common process. Like the broad lines observed in some Seyfert AGNs, these lines are likely produced by irradiation of the inner disk.

The Fe K$`\alpha `$ line we have observed in XTE J1650$``$500 suggests a Kerr black hole with near-maximal angular momentum ($`a=0.998`$). The accretion disk emissivity profile measured with the Laor line model is inconsistent with the energy dissipation expected for standard disks. These results are very similar to those reported by Wilms et al. (2001) using the same line and reflection models for the broad Fe K$`\alpha `$ line observed in an XMM-Newton/EPIC-pn spectrum of the Seyfert galaxy MCG–6-30-15 (E$`=6.97_{0.10}`$ keV, W$`300`$–400 eV, $`f=1.52`$, $`\beta 4.3`$–5.0). Those authors suggest that rotational energy extraction from the spinning black hole (Blandford & Znajek 1977) or material in the plunging region (Agol & Krolik 2000) may infuse the inner accretion disk with extra energy via magnetic connections, creating the steep emissivity profile indicated by the Fe K$`\alpha `$ line. It is possible that rotational energy extraction may be at work in XTE J1650$``$500 as well. If so, a fundamental general relativistic prediction may be confirmed across a factor of roughly $`10^6`$ in black hole mass.

This observation suggests a connection between the accretion geometry of stellar-mass black holes in the very high state, and that inferred in some Seyfert galaxies. This is an important step towards understanding the nature of the very high state, and the variety of exotic phenomena observed in this state. The Blandford–Znajek process is also often invoked as a means of launching jets (Blandford 2001a, 2001b; see also Fender 2001). That we have found an emissivity which might be explained by magnetic connections to the black hole or to matter in the plunging region in the very high state of XTE J1650$``$500 (detected at 7.5 mJy at 0.8 GHz with MOST in this state with a spectrum indicative of jets; S. Tingay, priv. comm.), suggests that the discrete radio ejections observed in some sources in this state (see Fender 2001) may be driven by rotational energy extraction.

Martocchia, Matt, & Karas (2002) have shown that a “lamp-post” reflection model may explain the steep disk emissivity implied in fits to the Fe K$`\alpha `$ line in MCG–6-30-15. This model assumes a source of power-law flux which illuminates the accretion disk from a location directly above the black hole. To explain $`\beta 4`$, this model requires $`f4`$ — well above the values we measure. Therefore, the lamp-post model may not adequately describe the accretion geometry of XTE J1650$``$500.

## 5. Acknowledgments

We wish to thank XMM-Newton project scientist Fred Jansen for executing our TOO request. RW was supported by NASA through Chandra fellowship grants PF9-10010, which is operated by the Smithsonian Astrophysical Observatory for NASA under contract NAS8–39073. This work is based on observations obtained with XMM-Newton, an ESA science mission with instruments and contributions directly funded by ESA Member States and the USA (NASA).


text:
# Edge coloring complete uniform hypergraphs with many components

## 1 Introduction

All graphs and hypergraphs considered here are finite, unordered and simple. For standard terminology the reader is referred to . Let $`H`$ be a hypergraph. For a $`k`$-edge coloring $`c:E(H)\{1,\mathrm{},k\}`$ let $`f(H,c)`$ be the number of components in the subhypergraph induced by the color class with the least number of components. Isolated vertices are not considered as components in a subhypergraph induced by edges. To avoid trivialities we always assume $`ke(H)`$. Let $`f_k(H)`$ be the maximum possible value of $`f(H,c)`$ ranging over all $`k`$-edge colorings of $`H`$. Trivially, if $`H`$ has $`n`$ vertices then $`1f_k(H)n/r`$ where $`r`$ is the minimum cardinality of an edge of $`H`$, and $`f_1(H)=c(H)`$ where $`c(H)`$ is the number of components of $`H`$ that are not isolated vertices.

In case $`H`$ is the complete $`r`$-uniform hypergraph $`K_n^r`$ it is not difficult to prove (see last part of Theorem 1.3) that $`f_k(K_n^r)=1`$ for $`kr`$. In fact, this is a generalization of the graph theoretic case, $`r=2`$, where $`f_2(K_n)=1`$ is merely the well-known fact that either a graph or its complement is connected (recently several extension of this elementary fact were proved  and our paper is in part inspired by this simple theorem). For fixed $`kr+1`$ it is not difficult to show that $`f_k(K_n^r)`$ is linear in $`n`$. However, determining the exact value is a nontrivial task.

This paper contains several results concerning the parameter $`f_k(K_n^r)`$. In the graph-theoretic case, we completely settle the case $`k=3`$ and the cases $`k=n1`$ and $`k=n`$. For other fixed values of $`k`$ we supply close upper and lower bounds that are also valid for the hypergraph case.

Our main results are summarized in the following theorems. For simplicity we use the notation $`f(n,k,r)`$ instead of $`f_k(K_n^r)`$, and $`f(n,k)`$ for the graph-theoretic case $`r=2`$. The first theorem on $`f(n,k)`$ is an exact result dealing with the lower end of the scale of colors, namely $`k=3`$.

###### Theorem 1.1

$`f(4,3)=f(5,3)=2`$. Otherwise $`f(n,3)=n/6+1`$.

The next theorem is an exact result dealing with values of $`k`$ in the upper end of the scale.

###### Theorem 1.2

1. $`f(n,n1)=n/2`$.
2. $`f(n,n)=(n1)/2`$.
3. If $`kn1`$ and $`k`$ divides $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ then $`f(n,k)=n(n1)/(2k)`$.
4. Suppose $`t1`$ and $`rt`$ divides $`n`$, then for $`k=t(n1)!/((r1)!(nr)!)`$, $`f(n,k,r)=n/(rt)`$.
5. If $`k\left(\genfrac{}{}{0pt}{}{n}{r}\right)\left(\genfrac{}{}{0pt}{}{nr}{r}\right)`$ then $`f(n,k,r)=\left(\genfrac{}{}{0pt}{}{n}{r}\right)/k`$.

Our next theorem supplies close upper and lower bounds for all fixed values of $`k`$. Before we state the theorem we need a few definitions. Given an edge-coloring $`c`$ of $`K_n^r`$, let $`z(n,r,c,s)`$ denote the fraction of the vertices incident with at least one edge whose color is $`s`$. Let $`z(n,r,c)`$ denote the maximum value of $`z(n,r,c,s)`$ taken over all colors appearing in $`c`$. For $`k1`$, let $`z_k(n,r)`$ denote the minimum possible value of $`z(n,r,c)`$ taken over all colorings that use at most $`k`$ colors. Finally, let $`z_{k,r}`$ denote the infimum of $`z_k(n,r)`$ taken over all $`nr`$. For $`r=2`$ denote $`z_k=z_{k,2}`$. The following theorem relates $`z_{k,r}`$ with the function $`f(n,k,r)`$.

###### Theorem 1.3

Let $`kr+1`$. Then,

$$n\left(\frac{1}{r}\frac{1}{rk^{1/r}}\right)(1+o_n(1))f(n,k,r)n\left(\frac{1}{r}\frac{z_{k,r}}{r}\right)(1+o_n(1)).$$

If $`kr`$ then $`z_{k,r}=1`$ and $`f(n,k,r)=1`$.

We conjecture that the lower bound in the last theorem is the correct one:

###### Conjecture 1.4

Let $`kr+1`$. Then,

$$f(n,k,r)=n\left(\frac{1}{r}\frac{z_{k,r}}{r}\right)(1+o_n(1)).$$

In section 2 we analyze the parameters $`z_{k,r}`$ and $`z_k`$. Infinitely many values of $`z_{k,r}`$ are known, and the values of infinitely many others are open problems. In particular, we determine (with varying difficulty of proofs depending on $`k`$) the following specific values: $`z_{r+1,r}=r/(r+1)`$, $`z_4=3/5`$, $`z_5=5/9`$, $`z_6=1/2`$, $`z_7=3/7`$, $`z_{12}=1/3`$, $`z_{6,3}=2/3`$, $`z_{14,3}=1/2`$. More generally, $`z_{p^2+p+1}=(p+1)/(p^2+p+1)`$ whenever $`p`$ is a prime power, and $`z_{p^2+p}=1/p`$ whenever $`p`$ is a prime power. $`k=8`$ is the smallest number for which $`z_k`$ is still unknown. It is also not difficult to bound $`z_k`$ from below. In fact, we show $`z_k1/\sqrt{k+1/4}1/2`$. Since, by definition, $`z_k`$ is monotone decreasing and since for every integer $`s`$ there is a prime (moreover a prime power) between $`s`$ and $`s+O(s^{2/3})`$  we have that $`z_k=1/\sqrt{k}+O(1/k)`$. Together with Theorem 1.3 we have, in the graph-theoretic case:

###### Corollary 1.5

Let $`k3`$ and let $`p`$ be the largest prime power satisfying $`p^2+p+1k`$ then

$$n\left(\frac{1}{2}\frac{1}{2\sqrt{k}}\right)(1+o_n(1))f(n,k)n\left(\frac{1}{2}\frac{p+1}{2(p^2+p+1)}\right)(1+o_n(1)).$$

The last corollary, together with the argument concerning density of primes show that the upper and lower bounds in the last corollary are very close. Table 1 summarizes the best upper and lower bounds that we currently have for $`lim\; supf(n,k)/n`$ and $`lim\; inff(n,k)/n`$ respectively, for some small values of $`k`$. For each specific $`k`$ (except $`k=3`$), the upper bound follows from Theorem 1.3 and in all cases, the lower bound follows from the best known upper bound for $`z_k`$ (all these upper bounds are consequences of constructions that appear in Section 2). We note that it may be possible to prove Conjecture 1.4 without determining the precise value of $`z_k`$ or $`z_{k,r}`$ for all $`k`$. On the other hand, although we know that, say, $`z_4=3/5`$, and $`z_{6,3}=2/3`$, proving that $`limf(n,4)/n=1/5`$ or $`limf(n,6,3)/n=1/9`$ is still an open problem. Currently, Conjecture 1.4 is open, in the graph theoretic case, for all $`k4`$, and for $`r3`$ it is open for all $`kr+1`$.

In Section 3 we prove the theorems and also consider the bipartite analog, namely, the parameter $`f_k(K_{n,n})`$.

## 2 Localized edge-coloring of complete hypergraphs

### 2.1 Lower bounds for $`z_{k,r}`$

We consider first the case $`kr`$. We show that in this case $`z_{k,r}=1`$. Namely, there must be a color that is incident with all vertices. In fact, we will show something somewhat stronger. There is always a color such that the subgraph of $`K_{n,r}`$ induced by the edges with this color is connected and spanning. In other words:

###### Lemma 2.1

If $`kr`$ then $`f(n,k,r)=1`$.

Proof: Clearly it suffices to prove $`f(n,r,r)=1`$. We shall prove this by induction on $`r`$. For $`r=2`$ we trivially have $`f(n,2)=f(n,2,2)=1`$ since either a graph or its complement is connected. Assume the theorem holds for $`r1`$, and we prove it for $`r`$. The proof for $`r`$ also proceeds by induction on $`n`$. If $`n=r+1`$ then exactly one color appears in two (intersecting) edges and hence this color must be incident with $`r+1=n`$ vertices and we trivially have $`f(r+1,r,r)=1`$. Assume it hold for $`n1`$ and we prove it for $`n`$. Fix a vertex $`v`$ and consider the subhypergraph $`K_{n1}^r`$ obtained by removing $`v`$. By the induction hypothesis there is a color $`c`$ such that the subhypergraph of $`K_{n1}^r`$ induced by this color is spanning and connected. If $`c`$ also appears in some edge of $`K_n^r`$ that contains $`v`$ we are done. Otherwise, consider the hypergraph $`K_{n1}^{r1}`$ obtained by removing $`v`$ and coloring each $`(r1)`$-set $`f`$ with the color of the edge $`fv`$ in $`K_n^r`$. This coloring does not use the color $`c`$ and hence is an $`r1`$ coloring of $`K_{n1}^{r1}`$. By the induction hypothesis it has a color $`c^{}`$ such that the subhypergraph induced by this color is connected and spanning. By the definition of the coloring of $`K_{n1}^{r1}`$, the subhypergraph of $`K_n^r`$ induced by color $`c^{}`$ must also be connected and spanning.         .

The following lemma supplies a lower bound for $`z_{k,r}`$ in case $`kr+1`$.

###### Lemma 2.2

Let $`kr+1`$, and let $`d2`$ be a positive integer. Then,

$$z_{k,r}\mathrm{max}\{\mathrm{min}\{\left(\frac{d}{k}\right)^{\frac{1}{r1}},\frac{1}{d1}\},\mathrm{min}\{\frac{d}{k},z_{d1,r1}\}\}.$$

Proof: Let $`d2`$ be a positive integer. Consider a coloring of $`K_n^r`$ with at most $`k`$ colors. For $`i=1,\mathrm{},k`$, let $`s_i`$ denote the number of $`(r1)`$-sets that are contained in an edge whose color is $`i`$. For an $`(r1)`$-set $`U`$, let $`b_U`$ denote the number of distinct colors that appear in edges that contain $`U`$. Clearly, $`_{U\left(\genfrac{}{}{0pt}{}{[n]}{r1}\right)}b_U=s_1+\mathrm{}+s_k`$. If $`b_Ud`$ for all $`U\left(\genfrac{}{}{0pt}{}{[n]}{r1}\right)`$ then $`s_1+\mathrm{}+s_k\left(\genfrac{}{}{0pt}{}{n}{r1}\right)d`$ and hence at least some $`s_i`$ satisfies $`s_i\left(\genfrac{}{}{0pt}{}{n}{r1}\right)d/k`$. Thus, if $`x`$ is the number of vertices appearing in an edge colored $`i`$, we must have $`\left(\genfrac{}{}{0pt}{}{x}{r1}\right)s_i\left(\genfrac{}{}{0pt}{}{n}{r1}\right)d/k`$. This implies that

$$\left(\frac{x}{n}\right)^{r1}\frac{x(x1)\mathrm{}(xr+2)}{n(n1)\mathrm{}(nr+2)}\frac{d}{k}$$

and hence $`xn(d/k)^{1/(r1)}`$. Thus, the fraction of vertices incident with color $`i`$ is at least $`(d/k)^{1/(r1)}`$. Otherwise, there exists an $`(r1)`$-subset $`U`$ such that $`b_Ud1`$. Assume, without loss of generality, that only the colors $`1,\mathrm{},d1`$ appear in edges that contain $`U`$. Then each vertex of $`K_n^r`$ appears in an edge whose color is one of the colors $`1,\mathrm{},d1`$. Thus, for some color $`i`$ the fraction of vertices appearing in an edge colored $`i`$ is at least $`1/(d1)`$. We have shown that $`z_{k,r}\mathrm{min}\{(d/k)^{1/(r1)},1/(d1)\}`$.

Next, we show that $`z_{k,r}\mathrm{min}\{d/k,z_{d1,r1}\}`$. For completeness, define $`z_{t,1}=1/t`$ (in a $`t`$-coloring of $`n`$ singletons at least $`n/t`$ elements obtain the same color, and this bound is realized). If there is a vertex $`v`$ of $`K_n^r`$ that is incident only with $`td1`$ colors then consider a coloring of $`K_{n1}^{r1}`$ obtained by removing vertex $`v`$ and coloring each $`(r1)`$-set $`U`$ with the color of the edge $`U\{v\}`$ in $`K_n^r`$. This defines a $`t`$-coloring of $`K_{n1}^{r1}`$ and hence, by definition of $`z_{t,r1}`$, some color is incident with at least $`(n1)z_{t,r1}`$ vertices. Since this color is also incident with $`v`$ and since $`z_{d1,r1}z_{t,r1}`$ we have found a color incident with a fraction of at least $`z_{d1,r1}`$ vertices of $`K_n^r`$. Otherwise, each vertex of $`K_n^r`$ is incident with at least $`d`$ colors, and hence there is a color that is incident with at least $`nd/k`$ vertices. In any case we have shown $`z_{k,r}\mathrm{min}\{d/k,z_{d1,r1}\}`$.

In the case $`r=2`$, by choosing $`d=\sqrt{k+1/4}+1/2`$ and using the fact that for this choice of $`d`$, $`d/k1/(d1)`$, we get

###### Corollary 2.3

For all $`k3`$, $`z_k1/\sqrt{k+1/4}1/2`$.

Notice that for $`r3`$ it is best to take $`dk^{1/r}`$ in Lemma 2.2, except for small values of $`k`$ where the lower bound of $`\mathrm{min}\{d/k,z_{d1,r1}\}`$ does better.

### 2.2 Upper bounds and precise values of $`z_{k,r}`$

Upper bounds for $`z_k`$ and $`z_{k,r}`$ are demonstrated by construction. Consider a trivial coloring of $`K_n^r`$ with $`\left(\genfrac{}{}{0pt}{}{n}{r}\right)`$ colors, each edge colored with a unique color. The fraction of vertices incident with each color is trivially $`r/n`$. This shows, in particular, that

###### Corollary 2.4

$`z_{\left(\genfrac{}{}{0pt}{}{n}{r}\right),r}r/n`$ , $`z_{n(n1)/2}2/n`$ , $`z_{r+1,r}r/(r+1)`$.

Corollary 2.4, together with Lemma 2.2 yield the following:

###### Corollary 2.5

$`z_3=2/3`$ , $`z_{r+1,r}=r/(r+1)`$ , $`z_6=1/2`$.

Proof: Upper bounds follow from Corollary 2.4. $`z_{r+1,r}r/(r+1)`$ follows from Lemma 2.2 by taking $`k=r+1`$ and $`d=r`$ (and recalling that $`z_{r1,r1}=1`$ by Lemma 2.1). $`z_3`$ is a special case of $`z_{r+1,r}`$. $`z_61/2`$ by taking $`r=2`$, $`k=6`$ and $`d=3`$ in Lemma 2.2.

In many cases we can find non-trivial constructions that match the lower bound that follows from Lemma 2.2. For example, the smallest nontrivial Steiner Triple System shows that $`K_7`$ can be decomposed into $`7`$ triangles. In other words, there is a coloring of $`K_7`$ with $`7`$ colors such that each color induces a triangle. We therefore get $`z_73/7`$. On the other hand, applying Lemma 2.2 with $`r=2`$, $`k=7`$ and $`d=3`$ gives $`z_73/7`$. Thus, $`z_7=3/7`$. More generally we can prove the following:

###### Proposition 2.6

Let $`p`$ be a prime power. Then, $`z_{p^2+p+1}=(p+1)/(p^2+p+1)`$ and $`z_{p^2+p}=1/p`$.

Proof: Whenever $`p`$ is a prime power there exists a projective plane $`PG(2,p)`$. This projective plane corresponds to the existence of a $`2(p^2+p+1,p+1,1)`$ design (see, e.g., ), which, in turn, corresponds to the fact that $`K_{p^2+p+1}`$ decomposes into $`p^2+p+1`$ copies of $`K_{p+1}`$. Hence, we have that $`z_{p^2+p+1}(p+1)/(p^2+p+1)`$ and using Lemma 2.2 with $`r=2`$ and $`d=p+1`$ we get $`z_{p^2+p+1}=(p+1)/(p^2+p+1)`$. Similarly, when $`p`$ is a prime power there exists an affine plane $`AG(2,p)`$. This affine plane corresponds to the existence of a $`2(p^2,p,1)`$ design (), which, in turn, corresponds to the fact that $`K_{p^2}`$ decomposes into $`p^2+p`$ copies of $`K_p`$ and using Lemma 2.2 with $`r=2`$, $`d=p+1`$ we get $`z_{p^2+p}=1/p`$.

Notice that Proposition 2.6 gives, in particular, $`z_{13}=4/13`$ and $`z_{12}=1/3`$.

Hanani has shown the existence of $`3(n,4,1)`$ designs for every even $`n`$ not divisible by 6 (cf. ). In other words, $`K_4^3`$ decomposes $`K_n^3`$ for $`n=2,4mod6`$. Hence if $`k=n(n1)(n2)/24`$ and $`n=2,4mod6`$ then $`z(k,3)4/n`$. In particular $`z(14,3)1/2`$. This upper bound has a matching lower bound that follows from Lemma 2.2 by taking $`r=3`$, $`k=14`$ and $`d=7`$ and recalling that $`z_{6,2}=z_6=1/2`$. Thus, we obtain the sporadic value $`z_{14,3}=1/2`$.

In all previous constructions, all color classes induced the same clique (or hyperclique) size. Constructions using non-isomorphic color classes (and even color classes that are not cliques) are also very useful. In fact, sometimes using non-isomorphic color classes is provably an optimal strategy. Consider the case $`k=4`$. Color $`K_5`$ with four colors as follows: For $`i=1,2,3`$, color $`i`$ appears in the edges $`(i,4)`$ and $`(i,5)`$ and color $`4`$ appears in the edges $`(1,2),(1,3),(2,3)`$. The edge $`(4,5)`$ is colored arbitrarily by one of the colors $`1,2`$ or $`3`$. Notice that each color is incident with precisely three vertices. Thus, $`z_43/5`$. Notice that we cannot match this upper bound with Lemma 2.2 so in order to prove that this is an optimal strategy we need to explicitly prove:

###### Proposition 2.7

$`z_43/5`$.

Proof: We need to show that in any coloring of a complete graph $`K_n`$ with at most four colors, at least one color is incident with at least $`3n/5`$ vertices. Consider a coloring of $`K_n`$ with the colors $`1,2,3,4`$. We use the same notations as in the proof of Lemma 2.2 (recalling that in case $`r=2`$ the sets $`U`$ are singletons). If $`b_v3`$ for all $`v=1,\mathrm{},n`$ then at least one color has $`s_i3n/4>3n/5`$. Assume, therefore, that there exist vertices with $`b_v=2`$. (If there exists a vertex with $`b_v=1`$ then the unique color $`i`$ incident with $`v`$ has $`s_i=n`$.) Let $`X\{1,\mathrm{},n\}`$ be the subset of vertices with $`b_v=2`$. Each $`vX`$ is associated with the unique pair of colors incident with $`v`$. Notice that if $`v`$ is associated with $`(i,j)`$ then no $`v^{}X`$ is associated with $`(k,l)`$ where $`\{k,l\}\{i,j\}=\mathrm{}`$. Thus, there are only at most three types of associations. It follows that there are two (not necessarily mutually exclusive) cases. Either there exists a color $`i`$ such that each $`vX`$ is incident with $`i`$, or there exists a color $`j`$ such that no $`vX`$ is incident with $`j`$. Consider the first case. If $`|X|3n/5`$ then $`s_i3n/5`$ and we are done. Otherwise, $`s_1+s_2+s_3+s_43(n|X|)+2|X|=3n|X|12n/5`$. Thus, some $`s_i`$ has $`s_i3n/5`$. Consider the second case. Then $`s_1+s_2+s_3+s_4s_j2n`$. Hence, some $`s_i`$ (i $`j`$) has $`s_i2n/3`$.

The coloring of $`K_5`$ with four colors described above yielding $`z_43/5`$ is somewhat ”reducible”. Indeed, if we allow weights on the vertices of $`K_n`$ then the following coloring of $`K_4`$ with four colors is more efficient: Color the edge $`(i,4)`$ with color $`i`$ for $`i=1,2,3`$. Color the triangle $`(1,2,3)`$ with color 4. Assign the weight $`2/5`$ to vertex 4, and the weight $`1/5`$ to each of the vertices $`1,2,3`$. Thus, the sum of weights of the vertices incident with color $`i`$ is $`3/5`$ for all $`i=1,2,3,4`$, as expected. Indeed, any $`c`$-coloring of a weighted $`K_n`$ (with rational weights) can be transformed to a non-weighted $`c`$-coloring of a larger $`K_n^{}`$ where each vertex of $`K_n`$ is “blown-up” proportionally to its weigh (an edge of $`K_n^{}`$ connecting two vertices corresponding to the same blown-up vertex of $`K_n`$ can be colored with any arbitrary color that is incident with that vertex of $`K_n`$).

The proof for the case $`k=5`$ is more complicated. For the upper bound, color $`K_9`$ as follows: Two colors induce each a copy of $`K_5`$. The two copies of $`K_5`$ share one vertex. The remaining 16 yet uncolored edges form a $`K_{4,4}`$. $`K_{4,4}`$ can be decomposed into two $`K_{2,3}`$ and one $`K_{1,4}`$. Thus, we have a 5-coloring of $`K_9`$ where each color is incident with 5 vertices. This shows that $`z_55/9`$. Again, we cannot match this upper bound with Lemma 2.2. We therefore show:

###### Proposition 2.8

$`z_55/9`$.

Proof: We need to show that in any coloring of a complete graph $`K_n`$ with at most five colors, at least one color is incident with at least $`5n/9`$ vertices. Consider a coloring of $`K_n`$ with the colors $`1,2,3,4,5`$. We use the same notations as in the proof of Lemma 2.2. If some vertex has $`b_v=1`$ we are done. Assume, therefore all vertices have $`b_v2`$. If at least $`7n/9`$ vertices have $`b_v>2`$ then $`s_1+s_2+s_3+s_4+s_53n2n/9`$ which implies that some $`i`$ has $`s_i5n/9`$ as required. Thus, let $`X\{1,\mathrm{},n\}`$ be the subset of vertices with $`b_v=2`$, and we may assume $`|X|2n/9`$. As in Proposition 2.7, each $`vX`$ is associated with the unique pair of colors incident with $`v`$, and if $`v`$ is associated with $`(i,j)`$ then no $`v^{}X`$ is associated with $`(k,l)`$ where $`\{k,l\}\{i,j\}=\mathrm{}`$. Thus, either there exists a color $`i`$ such that each $`vX`$ is incident with $`i`$, or there exist three colors $`i,j,k`$ such that only the associations $`(i,j),(i,k),(j,k)`$ are valid associations for the vertices of $`A`$. Consider the second case. In this case, each $`uX`$ is incident with at least two of the colors $`\{i,j,k\}`$. To see this, notice that if $`u`$ is not incident with, say, both $`i`$ and $`j`$ then the edge connecting $`u`$ to $`vA`$ where $`v`$ is associated with $`(i,j)`$, cannot be colored. We therefore have $`s_i+s_j+s_k2n`$ so at least one of the colors is incident with at least $`2n/3>5n/9`$ vertices. Now consider the first case. Since color $`i`$ is incident with all vertices of $`X`$ we may assume $`|X|5n/9`$, otherwise we are done. Let $`s`$ be the number of additional colors, other than $`i`$, incident with vertices of $`X`$. Without loss of generality, assume $`i=1`$ and assume all other colors incident with vertices of $`X`$ are $`2,\mathrm{},s+1`$. Clearly $`1s4`$. Let $`Y`$ be the subset of vertices not in $`X`$ and which are incident with color 1. Thus, color 1 is incident with precisely $`|Y|+|X|`$ vertices, and colors $`2,\mathrm{},s+1`$ are all incident with at least all vertices of $`v(K_n)(XY)`$, namely to at least $`n|X||Y|`$ vertices. Assume first that $`s2`$. Each vertex of $`Y`$ is incident with at least three colors, one of which is color 1, so it is also incident with at least $`s2`$ of the colors $`2,\mathrm{},s+1`$. It follows that $`s_2+\mathrm{}+s_{s+1}s(n|X||Y|)+(s2)|Y|+|X|`$. Thus, some $`s_i`$ is incident with at least $`n|X|2|Y|/s+|X|/s`$ vertices. It suffices to show that $`\mathrm{max}\{|Y|+|X|,n|X|2|Y|/s+|X|/s\}5n/9`$. Since the maximum is minimized when both terms are equal, and this happens when $`|Y|=ns/(s+2)|X|(2s1)/(s+2)`$ it suffices to show that $`ns/(s+2)|X|(s3)/(s+2)5n/9`$. For $`s=2`$ this holds since $`|X|2n/9`$ and thus $`n/2+|X|/45n/9`$. For $`s=3`$ this holds since $`3n/5>5n/9`$. For $`s=4`$ this holds since $`|X|5n/9`$ and thus $`2n/3|X|/6>5n/9`$. Finally, assume $`s=1`$. In this case colors 1 and 2 are incident with all vertices of $`K_n`$ and therefore $`s_1+s_2n+|X|`$. Thus, one of them is incident with at least $`n/2+|X|/2>5n/9`$ since $`|X|2n/9`$.

The reader may notice the significant added complexity to the proof of Proposition 2.8 as opposed to Proposition 2.7. It is plausible that with an increasing amount of effort one may determine $`z_k`$ or $`z_{k,r}`$ for every specific $`k`$ and $`r`$ with an appropriate “ad-hoc” proof.

A non-symmetric construction in the hypergraph ($`r=3`$) case that yields an exact result is the following:

###### Proposition 2.9

$`z_{6,3}=2/3`$.

Proof: The lower bound follows from Lemma 2.2 by taking $`r=3`$, $`k=6`$ and $`d=4`$ and recalling that $`z_{3,2}=z_3=2/3`$. For the upper bound, color $`K_6^3`$ with six colors as follows: Color 1 appears in $`(1,2,3),(1,2,4),(1,3,4),(2,3,4)`$. Color 2 appears in $`(1,2,5),(1,2,6),(1,5,6),(2,5,6)`$. Color 3 appears in $`(1,3,5),(1,3,6),(3,5,6)`$. Color 4 appears in $`(2,3,5),(2,4,5),(3,4,5)`$. Color 5 appears in $`(1,4,5),(1,4,6),(4,5,6)`$. Color 6 appears in $`(2,3,6),(2,4,6),(3,4,6)`$. Every color is incident with four vertices hence $`z_{6,3}4/6=2/3`$.

The upper and lower bounds for $`z_k`$ in case $`k=8,9,10,11`$ appearing in Table 1 are obtained as follows: For $`k=8`$, $`z_8z_7=3/7`$, and $`z_83/8`$ by selecting $`d=3`$ in Lemma 2.2. For $`k=9`$, $`z_92/5`$ since $`K_4^{}`$ (the graph obtained from $`K_4`$ be deleting an edge) decomposes $`K_{10}`$ into $`9`$ copies (see ). $`z_91/3`$ by selecting $`d=4`$ in Lemma 2.2. $`z_{10}z_92/5`$. $`z_{10}1/3`$ by selecting $`d=4`$ in Lemma 2.2. $`z_{11}4/11`$ since $`K_4^{}`$ decomposes $`K_{11}`$ into $`11`$ copies (see ). $`z_{11}1/3`$ by selecting $`d=4`$ in Lemma 2.2.

Finally, infinitely many nontrivial upper bounds in the case $`r=3`$ are obtained by using Möbius designs. For $`q`$ a prime power there exist the Möbius designs $`3(q^s,q+1,1)`$ (cf. ). Hence, $`K_{q+1}^3`$ decomposes $`K_{q^s+1}^3`$ and hence, for $`s=2`$ we have that for $`k=(q^2+1)q`$, $`z(k,3)(q+1)/(q^2+1)`$. In particular, $`z(10,3)3/5`$. This can be compared with the lower bound of $`z(10,3)5/9`$ that follows from Lemma 2.2 for $`r=3`$, $`k=10`$ and $`d=6`$, and using Proposition 2.8 which states that $`z_{5,2}=z_5=5/9`$.

## 3 Proof of the main results

We start with the lower bound in theorem 1.3 as its proof will also be used to prove one direction in Theorem 1.1.

### 3.1 A lower bound for $`f(n,k,r)`$

We shall require the following lemma, whose proof is an immediate consequence of a theorem of Baranyai .

###### Lemma 3.1

Let $`r2`$ and $`t1`$ be positive integers. There exists $`n_0=n_0(r,t)`$ such that for all $`nn_0`$, $`K_n^r`$ contains $`t`$ disjoint maximum matchings (a maximum matching is a set of $`n/r`$ independent edges).

It is well-known that $`n_0(2,t)=t+1`$, since the complete graph on $`t+1`$ vertices decomposes into $`t`$ perfect matchings in case $`t`$ is odd, and $`t+1>t`$ maximum matchings in case $`t`$ is even. For $`r3`$ the theorem of Baranyai states that if $`n`$ is a multiple of $`r`$ then $`K_n^r`$ decomposes into perfect matchings, and hence precisely $`t=(n1)!/((r1)!(nr)!)`$ disjoint perfect matchings. Thus, $`n_0(r,t)(t(r1)!)^{1/(r1)}`$.

We need to prove that $`f(n,k,r)n\left(\frac{1}{r}\frac{z_{k,r}}{r}\right)(1+o_n(1))`$. Let $`ϵ>0`$. Let $`t=t(k,r,ϵ)`$ be the smallest integer such that $`K_t^r`$ has a coloring $`C`$ using at most $`k`$ colors, such that each color is incident with at most $`t(z_{k,r}+ϵ)`$ vertices. Notice that in some cases it is possible to have $`ϵ=0`$. In Section 2 we have shown, e.g., that for $`r=2`$ and $`k=3,4,5,6,7,12,13`$ we can take $`ϵ=0`$ (in other words, $`z_k`$ is realized in these cases). As an example, for $`r=2`$ and $`k=3`$ we can pick $`ϵ=0`$ and $`t=3`$.

###### Lemma 3.2

Suppose $`n`$ satisfies

$$\frac{n}{t}n_0(r,k\frac{1}{z_{k,r}+ϵ}),$$

then $`f(n,k,r)\frac{n}{rt}t(1z_{k,r}ϵ)+1`$.

Proof: Assume the vertices of $`K_t^r`$ are $`\{1,\mathrm{},t\}`$ and assume the colors of $`C`$ are $`\{1,\mathrm{},k\}`$. Let $`C(e)`$ denote the color of edge $`e`$ (notice that it is possible that $`C`$ is not onto $`\{1,\mathrm{},k\}`$ as $`c`$ may use less than $`k`$ colors).

Partition the vertices of $`K_n^r`$ into $`t`$ equitable parts $`A_1,\mathrm{},A_t`$. The cardinality of each part is either $`n/t`$ or $`n/t`$ and by the assumption in the statement of the lemma, the parts are nonempty.

We now show how to color each edge of $`K_n^r`$. Let $`f`$ be an arbitrary edge, and let $`U=\{i:A_if\mathrm{}\}`$. Clearly $`1|U|r`$. Consider first the case $`|U|>1`$. In this case, let $`eK_t^r`$ be an edge such that $`Ue`$. In this case, we color $`f`$ with the color $`C(e)`$. Consider next the case $`|U|=1`$. In this case $`f`$ is completely within some part $`A_i`$. Hence, it remains to show how to color edges that are completely within some $`A_i`$. Let $`C_i\{1,\mathrm{},k\}`$ be the subset of colors not appearing in any edge of $`K_t^r`$ that contains the vertex $`i`$. We claim that $`|C_i|k\frac{1}{z_{k,r}+ϵ}`$. To see this, notice that if there were less than $`\frac{1}{z_{k,r}+ϵ}`$ colors incident with $`i`$ then at least one color would have been incident with more than $`t(z_{k,r}+ϵ)`$ vertices, contradicting the assumption. We claim that we can find in $`A_i`$ a set of $`|C_i|`$ disjoint maximum matchings. Indeed this follows from Lemma 3.1, and by the assumption in the current lemma that states that $`|A_i|n/tn_0(r,k\frac{1}{z_{k,r}+ϵ})`$. Fixing $`|C_i|`$ disjoint maximum matchings in $`A_i`$ we now color each maximum matching with a distinct color of $`C_i`$. It remains to show how to color the edges completely within $`A_i`$ that do not belong to any of the selected maximum matchings. In this case, we can color them with any color of $`CC_i`$ (does not matter which one).

Now consider any color $`cC`$. If $`c`$ is not used at all in the coloring of $`K_t^r`$ then the subhypergraph of $`K_n^r`$ induced by the edges colored $`c`$ is composed of isolated edges, exactly $`|A_i|/r`$ isolated edges from each $`A_i`$. Therefore, this subhypergraph has at least $`tn/(rt)`$ components. If $`c`$ is used as a color of at least one edge of $`K_t^r`$ then the subhypergraph induced by the edges colored $`c`$ in $`K_n^r`$ has some large components consisting of all the $`s`$ sets $`A_i`$ such that the vertex $`i`$ of $`K_t^r`$ is incident with an edge colored $`c`$, and isolated edges, exactly $`|A_i|/r`$ isolated edges from each of the $`ts`$ sets $`A_i`$ where vertex $`i`$ of $`K_t^r`$ is not incident with any edge colored $`c`$. Thus, this subhypergraph has at least $`(ts)n/(rt)+1`$ components. Since $`s(z_{k,r}+ϵ)t`$ our construction shows that $`f(n,k,r)\frac{n}{rt}t(1z_{k,r}ϵ)+1`$.

### 3.2 Proof of Theorem 1.1

Trivially $`f(3,3)=1`$. $`f(4,3)=2`$ as seen by coloring $`K_4`$ with three colors each inducing a perfect matching. $`f(5,3)=2`$ as seen by coloring $`K_5`$ with a red triangle and a red edge vertex-disjoint with the triangle, and coloring the remaining 6 edges with three blue edges forming a $`K_{1,2}`$ and a $`K_{1,1}`$ vertex disjoint with each other, and three green edges that are now also forced to induce a $`K_{1,2}`$ and a $`K_{1,1}`$ vertex disjoint with each other. Thus, we assume $`n6`$.

For the lower bound we use lemma 3.2. Recall that $`z_3=2/3`$ and $`K_3`$ realizes $`z_3`$ with $`ϵ=0`$ by giving each edge of $`K_3`$ a distinct color. The condition in Lemma 3.2 is satisfied for all $`n6`$ since $`n_0(2,1)=2`$, and hence we get $`f(n,3)n/6+1`$.

It remains to show the upper bound. Consider a coloring of $`K_n`$ with the three colors $`1,2,3`$. Let $`A_i`$ be the subset of vertices in a maximum cardinality component induced by color $`i`$. Put $`|A_i|=a_i`$ and assume $`a_1a_2a_3`$. Put $`D=A_1A_2`$ and $`d=|D|`$. Put $`M=V(A_1A_2)`$ where $`V`$ is the set of vertices of $`K_n`$, and $`m=|M|`$. If $`a_12n/3`$ then we are done since the subgraph induced by color $`1`$ has at most $`1+(n2n/3)/2=1+n/6`$ components. Hence we assume $`a_i<2n/3`$ for $`i=1,2,3`$. Consider the following cases

1. $`d=0`$. In this case every edge between $`A_1`$ and $`A_2`$ is colored 3. Thus, $`a_3a_1+a_2`$, a contradiction since the $`a_i`$ cannot be zero.
2. $`d>0`$, $`m=0`$, and $`d=a_1`$ or $`d=a_2`$ (or both). In this case one of the colors 1 or 2 (or both) induces a connected spanning subgraph of $`K_n`$.
3. $`d>0`$, $`m=0`$, $`d<a_1`$, $`d<a_2`$. In this case all edges between $`A_1D`$ and $`A_2D`$ are colored 3. Thus, $`2n/3>a_3(a_1d)+(a_2d)`$. On the other hand $`(a_1d)+(a_2d)+d=n`$. Thus, $`d>n/3`$. It follows that $`a_1+a_2=n+d>4n/3`$. Hence, $`a_1>2n/3`$, a contradiction.
4. $`d>0`$, $`m>0`$, $`a_1>d`$ and $`a_2>d`$. As in the previous case all edges between $`A_1D`$ and $`A_2D`$ are colored 3. Also all edges between $`M`$ and $`D`$ are colored 3. Thus, the subgraph induced by $`3`$ has at most two components and $`2n/6+1`$.
5. $`d>0`$, $`m>0`$, $`a_2=d`$. In this case all edges between $`M`$ and $`D`$ are colored 3. Thus, $`a_3d+m>d=a_2`$, a contradiction to the assumption $`a_3a_2`$.

### 3.3 Proof of Theorem 1.2

1. If $`n`$ is even then $`K_n`$ decomposes into $`n1`$ perfect matchings. Thus, $`f(n,n1)n/2`$. If $`n`$ is odd then $`K_n`$ decomposes into $`(n1)/2`$ Hamiltonian cycles. Each cycle further decomposes into a matching of size $`(n1)/2`$ and the remaining $`(n+1)/2`$ edges form a subgraph with $`(n1)/2`$ components (one component is a path with three vertices and the others are independent edges). Thus, $`f(n,n1)(n1)/2=n/2`$. In both the even and odd cases we always have $`f(n,n1)\left(\genfrac{}{}{0pt}{}{n}{2}\right)/(n1)=n/2`$. Thus, $`f(n,n1)=n/2`$.
2. If $`n`$ is odd then the chromatic index of $`K_n`$ is $`n`$. Thus, $`K_n`$ decomposes into $`n`$ matchings. This forces each matching to be of size $`(n1)/2`$. Thus, $`f(n,n)(n1)/2`$. If $`n`$ is even then $`n+1`$ is odd and we have $`f(n+1,n)=n/2`$ by the previous case. Deleting the additional vertex causes each induced subgraph of a color to loose at most one component. Thus, $`f(n,n)n/21`$. In both cases we always have $`f(n,n)(n1)/2`$. Since, trivially, $`f(n,n)\left(\genfrac{}{}{0pt}{}{n}{2}\right)/n=(n1)/2`$ we have shown $`f(n,n)=(n1)/2`$.
3. Assume $`kn1`$ and assume $`t=n(n1)/(2k)`$ is an integer. Thus, $`2tn`$ and it is well known that in this case $`tK_2`$ decomposes $`K_n`$ . Thus, $`f(n,k)t`$. The other direction follows from the trivial fact that $`f(n,k)\left(\genfrac{}{}{0pt}{}{n}{2}\right)/k=t`$.
4. Suppose $`t1`$ and $`rt`$ divides $`n`$. In particular, $`r`$ divides $`n`$, and by the result of Baranyai , $`K_n^r`$ decomposes into $`(n1)!/((r1)!(nr)!)`$ perfect matchings. Each perfect matching has cardinality $`n/r`$ and is further decomposed into $`t`$ matchings, each consisting of $`n/(rt)`$ edges. Hence, for $`k=t(n1)!/((r1)!(nr)!)`$ we have $`f(n,k,r)n/(rt)`$. Trivially, $`f(n,k,r)\left(\genfrac{}{}{0pt}{}{n}{r}\right)/k=n/(rt)`$.
5. Consider the line graph $`L`$ of $`K_n^r`$. $`L`$ has $`N=\left(\genfrac{}{}{0pt}{}{n}{r}\right)`$ vertices and is regular of degree $`s=\left(\genfrac{}{}{0pt}{}{n}{r}\right)\left(\genfrac{}{}{0pt}{}{nr}{r}\right)1`$. By the theorem of Hajnal and Szemerédi , for all $`k^{}>s`$, $`L`$ has a $`k^{}`$ equipartite coloring, namely, a vertex-coloring with $`k^{}`$ colors where each color class has either $`N/k^{}`$ or $`N/k^{}`$ elements. Using $`k=k^{}`$ and translating this back to the original hypergraph $`K_n^r`$, we have a $`k`$-edge coloring of $`K_n^r`$ such that each color induces a matching of cardinality at least $`\left(\genfrac{}{}{0pt}{}{n}{r}\right)/k`$. Thus, $`f(n,k,r)\left(\genfrac{}{}{0pt}{}{n}{r}\right)/k`$. The other direction is trivial.

### 3.4 Proof of Theorem 1.3

In case $`kr+1`$, the lower bound of Theorem 1.3 is shown in Lemma 3.2. For the upper bound, notice that in a $`k`$-edge coloring of $`K_n^r`$ at least one color appears in at least $`\left(\genfrac{}{}{0pt}{}{n}{r}\right)/k`$ edges. Fix such a color, and let $`s_1,\mathrm{},s_t`$ denote the cardinalities of the components in the subhypergraph induced by this color. Clearly, $`s_ir`$ for $`i=1,\mathrm{},t`$ and

$$\left(\genfrac{}{}{0pt}{}{nr(t1)}{r}\right)+(t1)\left(\genfrac{}{}{0pt}{}{s_1+\mathrm{}+s_tr(t1)}{r}\right)+(t1)\underset{i=1}{\overset{t}{}}\left(\genfrac{}{}{0pt}{}{s_i}{r}\right)\left(\genfrac{}{}{0pt}{}{n}{r}\right)\frac{1}{k}.$$
(1)
It follows that $`nr(t1)(1+o_n(1))n/k^{1/r}`$ and hence $`t(n/rn/(rk^{1/r}))(1+o_n(1))`$. In case $`kr`$, $`f(n,k,r)=1`$ is shown in Lemma 2.1.

It is not difficult to show that in case $`r=2`$, the negation of the error term in the upper bound of Theorem 1.3 is at least $`\mathrm{\Theta }(1/k^{3/2})`$, by considering the maximal cardinality components induced by each color, and showing that either there is a color with a “huge” component, or otherwise there must be (at least) two such maximal components (belonging to two distinct colors) that intersect in $`\mathrm{\Theta }(n)`$ vertices, and thus at least one of these maximal components is far from being a clique (misses $`\mathrm{\Theta }(n^2)`$ edges from being a clique), and hence the convexity argument in inequality (1) cannot be exploited to its extreme. However, this improvement is negligible. Even for $`k=4`$ we could only improve the constant from $`0.25`$ to (a little less than) $`0.243`$. That is, $`lim\; supf(n.4)/40.243`$.

### 3.5 The bipartite analog

Let $`C`$ be a $`k`$-edge coloring of $`K_r`$ where color $`i`$ is incident with $`s_i`$ vertices. We show how to construct a coloring $`C^{}`$ of $`K_{r,r}`$ where color $`i`$ is incident with $`2s_i`$ vertices. Assume the vertices of one partite class are labeled $`\{a_1,\mathrm{},a_r\}`$ and the vertices of the other partite class are labeled $`\{b_1,\mathrm{},b_r\}`$. For $`ij`$ color $`(a_i,b_j)`$ with the same color as the edge $`(i,j)`$ of $`K_r`$. Color $`(a_i,a_i)`$ with any color incident with vertex $`i`$ in $`K_r`$. The obtained coloring has the desired property. Now, this construction together with the same “blow up” argument as in Lemma 3.2 yields the following:

$$f_k(K_{n,n})n(1z_k)(1+o_n(1)).$$

An upper bound density argument similar to the one in Theorem 1.3 gives $`f_k(K_{n,n})n(11/\sqrt{k})(1+o_n(1))`$. Recalling that $`z_k=1/\sqrt{k}+O(1/k)`$ we get that the upper and lower bounds for $`f_k(K_{n,n})`$ are very close.

## Acknowledgment

The authors thank Yehuda Roditty for valuable discussions.