\section{Introduction}

Are there multitudes of planetary systems that are capable of
harboring life, like our own Solar System?  Answering this question
motivates the research activities of a great number of astronomers, as
well as scientists of many disciplines.  Yet the answer depends on
which aspect of our solar system to which one is comparing the
physical properties of other systems. Extrapolation of radial velocity
results to 20 AU suggests that planets with mass at least a third that
of Jupiter's surround 15-20 \% of sun-like stars (Cumming et
al. 2008).  Yet lower mass planets might turn out to be even more
common (e.g. Mayor et al. 2009).  Enormous progress has been made in
the past several years on many aspects of circumstellar disk evolution
(e.g. Meyer et al. 2007), especially those that can be addressed with
observations from the Spitzer Space Telescope (Werner et al. 2006).
In this review we explore answers to three key questions: 1) What is
the time available to form gas giant planets?  2) What is the history
of planetesimal collisions versus radius?  3) How do answers to the
above vary with stellar properties?  Because the answers to these
questions are subtle, one needs large stellar samples with reliable
stellar ages from the youngest pre--main sequence stars to the oldest
stars known in the galactic disk.  In our attempt to study important
evolutionary processes in the formation and evolution of planetary
systems, we assemble groups of stars with like properties (such as a
narrow range in stellar mass) as a function of age, the main topic of
this symposium.  We hope that by studying the mean (as well as the
dispersion) in those properties of the circumstellar environment as a
function of time, we can create a ''movie'' (or range of plausible
trajectories) that helps tell the story of how our solar system might
have formed.  Once completed for one range in stellar mass, we can
attempt to repeat the study for other stellar masses.  Examining the
differences in circumstellar disk evolution as a function of stellar
mass may be our best tool in delineating the most important physical
processes in planet formation.  It is a lofty goal, and often strong
assumptions are required to make progress.  We can only hope that most
of these assumptions represent hypotheses we can test in the near
future.

Observations of circumstellar gas and dust, both its amount and
geometrical distribution, can be compared to theoretical timescales
for its expected evolution.  Keplerian orbits can range from days to
millennia.  The viscous timescale in the context of an $\alpha$ disk
model depends on the orbital radius and can be $<$ 1 Myr within 10 AU
for reasonable parameters (Hartmann 1998).  Preliminary results
suggest that disk chemistry proceeds more slowly than relevant
dynamical times indicating that mixing could be important (Bergin et
al. 2007).  The inward migration of solids in the disk results in the
loss of planet--building material and remains a serious problem on
many scales: a) gas drag on meter--sized bodies can reach 1 AU/century
(Weidenschilling, 1977); b) Type I migration of lunar--mass planetary
embryos on timescales of 10$^5$ yrs; and c) Type II migration of
forming gas giant planets on timescales proportional to the viscous
time (e.g. Ida \& Lin, 2008 and references therein).  The timescale
for orderly growth of bodies through collisions (e.g. Goldreich et
al. 2004) is proportional to the product of the radius and volume
density of typical particles divided by the product of the mass
surface density of solids and the orbital frequency.  The timescale
for radiogenic heating of forming planetesimals is set by the relative
abundances of radioactive nuclides as well their half-lives (Sanders
\& Taylor, 2005).  Current models suggest that photoevaporation of gas
from illumination by EUV, FUV, and x--ray emission can disperse
primordial gas disks around sun-like stars on timescales $<$ 10 Myr
(Gorti \& Hollenbach 2009; Ercolano et
al. 2009).  Additional physical processes are important in debris disk
evolution.  In most (if not all) debris disks studied to date (our
solar system dust disk being a notable exception), mutual collisions
between dust grains reduce particle sizes to the blow--out limit where
radiation pressure efficiently removes them from the system (Wyatt 2008).
The Lyapunov timescale characterizes divergence of orbital elements in a
chaotic system and is related to the timescale for instability in
planetary systems (Murison et al. 1994).  In this context, we note
that our own planetary system is thought to be stable on timescales
comparable to its present age of 4.56 Gyr (Laskar 1994) while the
main sequence lifetime of the Sun is approximately twice this.

In what follows, we describe some of the observational evidence for
primordial disk evolution and resulting constraints on theories of
planet formation.  We follow with a brief discussion of planet
formation, the evolution of planetesimals belts, and the dust debris
they generate.  We conclude with a summary and look forward to
exciting developments we can anticipate in the years ahead.

\section{Primordial Circumstellar Disks}

It is now well established that most sun--like stars form surrounded
by circumstellar disks.  These disks are
primordial mixtures of gas and dust initially resembling the
composition of the interstellar medium from which the star-disk
systems form.  Near--infrared excess emission traces the hottest inner
disk structures within 0.1 AU.  While the inner edge of the dust disk
is determined by the location at which the dust particles sublimate
($\sim$ 1400 K for typical silicates; Muzerolle et al. 2003), the gas
disk can extend inward, perhaps terminating near the boundary set by
magnetospheric accretion theory (e.g. Shu et al. 1994).  The
pioneering work of Strom et al. (1989) suggested that inner disks
dissipate on timescales of 10 Myr from observations of K--band excess
toward T Tauri stars in the Taurus dark cloud.  Haisch et al. (2001)
surveyed near--IR excess emission using color--color diagrams toward
hundreds of stars in several young clusters concluding that the mean
inner disk lifetime is approximately 3 Myr.  Yet if the spectral type
of star is known, and multi--color optical/infrared photometry is
available, one can carefully separate the effects of intrinsic stellar
colors, reddening due to dust along the line of sight toward the star,
and circumstellar disk excess determining with greater precision the
magnitude of any excess emission (e.g. Meyer et al. 1997).  This
approach was used by Hillenbrand and collaborators
(2008) to construct the evolutionary diagram shown
in Figure 1 which we have adapted to include:
a) relative formation timescales for solar system
objects as determined from measurements of extinct
radioactive nuclides from meteorite samples
(Scott, 2007; Jacobsen, 2005); and
b) the frequency distribution of inner disk
lifetimes based on these evolutionary diagrams.
While the mean disk lifetime is 3 Myr,
there is a large {\it dispersion} of inner
disk lifetimes.  Andrews \& Williams (2005) have
observed the distribution of disk masses
for young stars ranges over two orders of
magnitude from millimeter wave continuum data.
Perhaps the distribution of initial conditions
(specific angular momenta in collapsing
cloud cores) results in a distribution of
disk masses and thus disk lifetimes.

\begin{figure}[bh]
\begin{center}
 \includegraphics[width=2.4in]{15.Meyer.f1a.eps}
 \includegraphics[width=2.4in]{15.Meyer.f1b.eps}
 \caption{\textit{Left:}
 Fraction of inner accretion disks as a function of time
  surrounding sun-like stars
 (roughly 0.5-2 M$_{\odot}$ as traced by near--IR excess emission observed
  toward stars with known spectral types.  Figure adapted from Hillenbrand
  (2008) with the approximate timescales for the formation of solar system
   objects indicated from meteoritic study of extinct radioactive nuclides.
\textit{Right:}
Schematic representation of {\it distribution} of inner disk
	  lifetimes obtained by subtracting adjacent bins in the left panel.}
\label{bigradii}
\end{center} \end{figure}

How long does it take for material in the inner disk to transition
from optically--thick to optically--thin?  Skrutskie et al. (1990)
provided some preliminary answers based on 10 $\mu$m
observations of T Tauri stars.  They
found that most stars lacking 2 $\mu$m excess also lacked
mid--infrared excess emission.  A small handful of objects, the
so--called transition objects, exhibited modest mid--IR excess but
lacked evidence for hot dust.  From the ratio of the number of objects
in transition compared to samples of T Tauri stars (few \% with
respect to T Tauri stars with primordial accretion disks, CTTS, or a
smaller fraction of young stars overall) times the typical age of the
sample stars (1--3 Myr), they estimated the duration of the transition
phase to be very short ($\sim 10^5$ years).  Subsequent work has
verified these estimates.  For example, Silverstone et al. (2006)
found no examples of inner dust disks in systems that lack signatures
of on--going gas accretion from the disk onto the star (cf. Cieza et
al. 2007).  However with surveys of star-forming regions enabled by
the Spitzer Space Telescope, dozens of these rare objects can now be
identified (e.g. Merin et al. 2008).

Much attention is focused on understanding the nature of transition
disks (Najita et al. 2007; Alexander \& Armitage 2007).  Some appear to
have inner cleared regions due to the presence of previously unseen
faint companions at small orbital radii (Ireland \& Kraus, 2008).
Work continues to understand the detailed distribution of gas and dust
in these systems (e.g. Espaillat et al. 2007).  One
troubling feature in all of these disk studies is the general {\it
lack} of correlation between key physical variables and observational
properties of the disks (Watson et al. 2009).
For example, Pascucci et al. (2008) found no
difference in dust properties between binary and single stars.
Some disks can be quite long lived (more
than 10 Myr old) and still appear very similar to typically much
younger classical T Tauri stars (e.g. PDS 66; Cortes et al. 2009).
Often morphological ordering of disk spectra or other properties can
be quite compelling (e.g. Bouwman et al. 2008).  But more often than
not, ranking by estimates of stellar age appear to disturb the
apparent evolutionary sequences.  Although errors in determining
stellar ages are a likely culprit, it does seem that there are
''hidden variables'' contributing significantly to primordial disk
evolution.

As a complement to studies of the dust, can we probe further the
evolution of the gas from which giant planets might form (Najita et
al. 2007)?  For young stars in the Taurus dark cloud, there is an
excellent correspondence between spectroscopic signatures of gas
accretion from the inner disk onto the surface of the star and the
presence of near--IR excess emission (Hartigan, Edwards, and Ghandour,
1995).  Indeed the evolution of accretion rates appears to mimic to
some extent the evolution of hot dust (Hartmann et al. 1998; Gatti et
al. 2008).  Spitzer spectra are starting to
reveal interesting chemistry in the disks young young stars (Carr \&
Najita, 2008; Pascucci et al. 2009).  High resolution near--infrared
spectroscopy combined with high spatial resolution can reveal
interesting offsets between the emitting regions of various molecules
(Pontoppidan et al. 2008).  Millimeter wave observations are required
to trace rotational transitions of cool gas at large radii (e.g. Dutrey
et al. 2007).

Yet the bulk of the mass in these disks is in molecular hydrogen,
which is difficult to detect.  Some efforts have been made to trace
molecular hydrogen directly by observing the pure rotational lines in
the mid--infrared from the ground at high spectral resolution (Bitner
et al. 2008).  The Spitzer Space Telescope also provided a platform to
search for gas using the IRS in high resolution mode.  Based on
equilibrium chemical models of Gorti \& Hollenbach, 2004), Pascucci et
al. (2006) report non--detections from the FEPS survey (Meyer et
al. 2006) for stars with ages between 3--100 Myr that lack signatures
of accretion, but possess optically--thin dust emission.  The upper
limits place constraints of $<$ 10
Myr on the timescale to form gas giants in these systems.  These
timescales are of interest for comparison to models of gas giant
planet formation through classical core accretion (e.g. Lissauer \&
Stevenson 2007) as well as gravitational fragmentation which proceeds
more quickly (Durisen et al.  2007).  Future observations with
Herschel and SOFIA will be powerful
probes of even small amounts of residual emission perhaps placing
constraints on the formation of super-earths and ice giants.  We note
for completeness that circumstellar gas has been detected for some
debris disks (e.g. Dent et al. 2005), which are
the subject of the next section.

\section{Planet Formation and Generation of Debris Dust}

How does remnant disk material evolve when the bulk of the gas capable
of forming giant planets has dissipated?  In the classical theory,
protoplanets initially grow in an orderly way through collisions of
comparable sized bodies.  As gravitational focusing becomes important,
the larger bodies grow fastest in a runaway mode until a modest number
of ''successes'' reach the local isolation mass, essentially consuming
all material within several times their gravitational sphere of
influence (Hill radius).  These oligarchs then perturb each other over
time resulting in handfuls of collisions that create a
small number of planets
(e.g. Nagasawa et al. 2007).  At 1 AU around the Sun, we imagine the
Earth as built through the collision of several Mars-sized
objects.\footnote{The last of these collisions resulting in the
formation of the Moon (e.g. Canup 2004).} It is thought that
similar processes operate (in the presence of gas) to form the cores
of giant planets. In the first phase, we can estimate the frequency of
collisions by knowing the surface density of solids ($\sigma$) as well
as the orbital timescale ($\Omega$):
$$ \tau \sim (R_{body} \times \rho_{body})/(\sigma \times \Omega)$$
where R and $\rho$ are the radius and volume density of the object
built through these collisions in time $\tau$.  If we combine estimates
of the dependence of disk mass on star mass ($\sigma_{disk} \sim M_*$)
and orbital radius ($\sigma_{disk} \sim 1/a$) with the orbital frequency
we get $ \tau \sim a^{5/2} M_{*}^{-3/2}$
for a constant $\rho$.  This implies, within a fixed time interval,
disks around stars of higher mass form:
a) more massive planets at a given orbital distance; and b) planets of a given mass
at larger orbital separation.  Both are consistent with recent radial
velocity results (Johnson et al. 2007).   Yet it appears that primordial
disks evolve more quickly around stars of higher mass
(Carpenter et al. 2006), complicating the implications of this simple
picture for planet formation around stars as a function of their mass.

Observations of debris disks have become powerful tools to study the
evolution of planetary systems and their value has increased as we
have learned more about the asteroid and Kuiper belts in our own Solar
System (Wyatt 2008).  As cooler dust orbiting at larger radii emits
at longer wavelengths, we can use the wavelength dependence of excess
emission as a proxy for its location in the absence of resolved
images.  With the Spitzer Space Telescope, we can detect $>10^{-5}$
Earth masses of dust if it is found in micron--sized particles from
photometric surveys at 24 $\mu$m, efficiently tracing material with
temperatures above 100 K (often tracing radii $<$10 AU around
sun--like stars).  Meyer et al. (2008) report the results from FEPS
for 24 $\mu$m excess emission around an unbiased parent sample of 309
stars.  They find that 10--20 \% of sun--like stars show evidence for
24 $\mu$m excess over an age range from 3--300 Myr with a significant
drop in the frequency of 24 $\mu$m excess for older stars.  As we can
only observe the product of the frequency of this phenomena and its
duration, the interpretation of these results is ambiguous.
They also suggest that the frequency of excess
{\it may} be higher for stars in open clusters compared to field stars
of comparable age though the evidence for this is not significant.
Note that the ages of the open cluster stars are the ''gold standard''
for stellar ages in these studies and thus it is difficult to compare
results between them and field stars.  In contrast, Greaves et
al. (2009) find a surprising lack of emission at 1.3 mm towards
sun--like stars in the Pleiades open cluster despite significant
improvement in sensitivity compared to previous observations.

The above mentioned Spitzer results are consistent with other surveys
for 24 $\mu$m excess around FGK stars as a function of time
(e.g. Siegler et al. 2007).  It is worth
remembering that these survey limits are only able to detect dust
producing planetesimal belts that are about $\times 1000$ brighter
than our own inner zodiacal dust generated from collisions in the
asteroid belt.  Wyatt et al. (2007) compare these observations to
models of collisional evolution for planetesimal belts finding that
some warm debris excesses (e.g. HD 69830) are so large that they
cannot be the result of pure collisional evolution and must
be transient.  Although the models of Kenyon \& Bromley (2004) explain the
observed behavior in a qualitative way,
updates to the input physics continue to
improve the agreement between the models and data (Bromley \& Kenyon
2008).  Models for several debris disks detected with Spitzer require
extended distributions of dust
(Hillenbrand et al. 2008) consistent with resolved images of some
sources (Corder et al. 2009).

What (if any) correlation should we expect between the presence of
dust debris and the frequency of gas giant planets detected through
radial velocity variations?  One might speculate that a disk rich in
heavy elements capable of forming gas giant planets (e.g. Fischer \&
Valenti 2005; Santos et al. 2004) might initially have a high
surface density of solids and thus produce a lot of dust early--on,
outshining a system that lacked enough dust to form giant planets.  If
however, such a system produces several planets unstable
to mutual perturbations, dynamical rearrangement could deplete
dust-producing planetesimals in the inner and outer regions
as suggested by the Nice model for the
early evolution of our Solar system (e.g. Tsiganis et al. 2005).  Such a
system could then become a very weak dust producer at late times
(Figure 2).  It is in part these complexities that prevent us from
making comparisons of Spitzer observations
to what is known about our Solar system.

\begin{figure}[htb]
\begin{center}
\includegraphics[angle=0, width=\textwidth]{15.Meyer.f2.eps}
 \caption{ Graphical representation of dust production versus time for
  the case of a disk with an initially high surface density of solids that
  forms gas giant planets and another with a lower initial surface density
  that does not.  The planet-forming disk outshines the other disk early
  on, but then suffers a dynamical event that removes most
  of the dust-generating planetesimals.  The disk that was never able to
  form giant planets might generate more dust at late times.}
   \label{fig:f2}
\end{center}
\end{figure}

Moro--Martin et al. (2007a) search for a correlation between the
presence or absence of excess with gas giant planets and was unable to
confirm any (though the sample size was modest).  Apai et al. (2008)
also searched (without success) for the presence of gas giant planets around
stars for which large inner holes in the dust debris had been
inferred.  There are, however, remarkable examples of systems with
evidence for planets that also maintain debris which deserve special
study (Moro--Martin et al. 2007b; Lovis et al. 2006) including the
recently announced direct imaging results for Fomalhaut (Kalas et
al. 2008) and HR 8799 (Marois et al. 2008).  We can also ask whether
debris is correlated with the heavy element abundance of the star as
it is famously with the probability of having a gas giant planet.
Greaves, Fischer, \& Wyatt (2006) find that the metallicity
distribution of stars with cold debris detected in the sub--millimeter
is consistent with having been drawn from the same distribution as the
parent sample of stars.  We find a similar result for stars in the
FEPS sample (Najita et al., in preparation).  Perhaps gas giant planet
formation is a {\it threshold} phenomena with regard to the heavy
element content of the primordial circumstellar disk whereas the
requirements for ending up with a dust producing debris disk are more
forgiving.  Bryden et al. (2006) estimate that Spitzer only detects
the tip of the iceberg in terms of dust debris, and survey results to
date are {\it consistent} with our Solar System IR emission being near
the mean for sun--like stars in the Milky Way.

Given the mixed results for the correlation of debris with planets,
can we expect more order in the behavior of debris with stellar
multiplicity?  There is considerable literature on the similarities
and differences in disk evolution between single and binary T Tauri
stars (Monin et al. 2007).  With regard to
debris around one or both components of a binary system, Trilling et
al. (2007) report Spitzer results finding a complex mix of behaviors
including circumbinary debris disks, circumstellar disks in wide
binary systems, as well as the apparition of dust at inferred orbital
distances consistent with the separation of the binary companion!  At
minimum, one can infer that debris dust as detected by Spitzer is not
inhibited in multiple systems.

The ''last word'' from the FEPS program comes from Carpenter et
al. (2008; 2009) in which the extant database and synthesis of results
are described respectively.  With the addition of the IRS spectra from
5--33 $\mu$m for the sample, debris suspected from the 24 $\mu$m
photometry can be confirmed with confidence.  Even more important, the
temperature of the hottest dust detected can be estimated from the
broadband spectrophotometry providing estimates of the inner radius of
the debris disks in the sample.  The detected dust is cooler on
average (and thus located at larger radii) than assumed in Meyer et
al. (2008): the distribution of inner radii for the (often extended)
debris disks detected in the survey range from 3--30 AU, with a peak
at 10 AU.  There is no evidence for evolution of the dust temperature
with age, though the magnitude of the observed excess does decline
over time (with considerable dispersion at any one age).  It appears
that some of the 24 $\mu$m excess emission observed is the Wien tail
of bright, but cool, dust at radii beyond the terrestrial planet zone.
Emission evolves from bright to faint (or in some cases hot to cool)
within 300 Myr.  Yet the picture that emerges overall is one where
most debris is cleared out to radii of 10 AU on timescales of 3--10
Myr!  Whether this represents complete ''mission success'' for planet
formation between 0.1--10 AU or presents a challenge to current theory
remains to be explored.  Constraining the outer disk radii will
require observations at longer wavelengths utilizing Herschel, SOFIA,
or more sensitive sub--millimeter observations (e.g. Roccatagliati et
al. 2009).

It is extremely tempting to compare these results for FKG stars to
those for stars of different temperature \& luminosity in order to
explore diversity in the formation and evolution of planetary systems
as a function of stellar mass.  However, such comparisons require
caution.  For example, in a survey where the sensitivity is limited by
photometric precision of detecting an excess in contrast to the flux
of the star, the amount of detectable dust around a more luminous star
is larger than the detectable amount around one of lower luminosity.
Also dust at a given temperature is located at a larger radius around
a more luminous star.  Any comparison should take this into account in
terms of solid angle for the emission as well as the expected orbital
period and dust surface density distribution.  Overall, one can say
that the magnitude of the excesses observed at 24 and 70 $\mu$m around
A stars are larger, and more common, than those observed around G
stars (Su et al. 2006), yet the timescale for
the duration of the phenomena is slightly shorter around A stars
compared to G stars (Currie et al. 2007; cf. Trilling et al. 2008).
Gautier et al. (2007) find that debris emission around M dwarfs is
even weaker.

\section{Summary and Future Work}

So are planetary systems like our own are common or rare among sun-like
stars in the Milky Way galaxy?  Unfortunately, we cannot yet answer
this question, but we can provide some important constraints that are
stepping--stones to future progress.
{\it Primordial Disk Evolution:} Disks around lower mass stars are
less massive and live longer than their more massive counterparts.
The large observed dispersion in evolutionary times could indicate a
dispersion in initial conditions.  Overall, disk evolution appears to
proceed from inside--out as expected.
{\it Change you can believe in:} The duration of the transition time
from primordial to debris is $\sim$ 10$^5$ yrs.  Planetesimal belts
evolve quickly out to 3--30 AU.  Evidence for 24 $\mu$m excess is largely
gone by 300 Myr.  There is a hint that such excesses might be more
common in open clusters at a given age though more work on this is
needed.
{\it Debris Disk Evolution:} Currently detectable extra--solar debris
systems are all collision-dominated in their evolution.  Debris is
brighter and more common around stars of higher mass.  Evolutionary
paths are diverse but the observed distributions are consistent with
our Solar System debris disk being common among stars $>$ 1 Gyr old.
The connection between debris and planetary systems is unclear.  Yet
it may turn out that debris (and perhaps terrestrial planets) are more
common than their gas giant counterparts.  As we know that nearly all
young stars begin their lives surrounded by primordial disks of gas
and dust capable of making some sort of planetary system, one wonders:
are systems without debris those with dynamically full planetary
systems, or those without any planets whatsoever?

Anyone who has taken a turn leading the blind around the proverbial
elephant (i.e. modelling spectral energy distributions) knows that a
resolved image is worth more than 1024 $\times$ 1024 photometric
points on an SED.  Constraining model parameters with resolved
emission at one or more wavelengths is vital to making progress.  In
addition to high contrast imaging of disks in scattered light from space
and ground--based telescopes equipped with adaptive optics, millimeter
wave interferometry will continue to make crucial contributions.  The
soon to be launched ESA Herschel Space Telescope will also build on
the work of Spitzer, providing dozens of newly resolved debris disks
in thermal emission.  Finally, we look forward to science observations
with ALMA and JWST that will expand our understanding of the formation
and evolution of planetary systems in ways we can scarcely imagine
(provided of course that we first solve the thorny problem of
obtaining accurate stellar ages and uncover the nearest, youngest,
sun--like stars as prime targets of observation).

\acknowledgment The author would like to thank many colleagues whose
work has contributed to his current understanding regarding the
formation and evolution of planetary systems including members of
the FEPS/c2D/Glimpse Legacy Science Teams, the MIPS/IRS/IRAC
Instrument Teams, and the Spitzer Science Center staff.  MRM acknowledges
support from the Legacy Science Program through a contract from
NASA/JPL as well as the LAPLACE node of the NASA Astrobiology
Institute.


\section{Introduction}

All graphs considered in this paper are simple, finite and
undirected. Let $G$ be a nontrivial connected graph with an edge
coloring $c: E(G)\rightarrow \{1,2,\cdots,k\}$, $k\in \mathbb{N}$,
where adjacent edges may be colored the same. A path of $G$ is
called $rainbow$ if no two edges of it are colored the same. An edge
colored graph $G$ is said to be $rainbow ~connected$ if for any two
vertices of $G$ there is a rainbow path of $G$ connecting them.
Clearly, if a graph is rainbow connected, it must be connected.
Conversely, any connected graph has a trivial edge coloring that
makes it rainbow connected, i.e., the coloring such that each edge
has a distinct color. Thus, Chartrand et al. \cite{Chartrand 2}
defined the $rainbow~connection~number$ of a connected graph $G$,
denoted by $rc(G)$, as the smallest number of colors by using which
there is an edge coloring of $G$ such that $G$ is rainbow connected.

Suppose that $G$ is a $\kappa$-connected graph with $\kappa \geq 1$.
It then follows from a well-known theorem of Whitney that for every
integer $k$ with $1\leq k\leq \kappa$ and every two distinct
vertices $u$ and $v$ of $G$, the graph $G$ contains $k$ internally
disjoint $u-v$ paths. Chartrand et al. \cite{Chartrand 2} defined
the $rainbow$~ $k$-$connectivity$ $rc_k(G)$ of $G$ to be the minimum
integer $j$ for which there exists a $j$-edge-coloring of $G$ such
that for every two distinct vertices $u$ and $v$ of $G$, there exist
at least $k$ internally disjoint $u-v$ rainbow paths. Thus by the
definition, $rc_1(G)=rc(G)$ is the rainbow connection number of $G$.
By coloring the edges of $G$ with distinct colors, we see that every
two vertices of $G$ are connected by $\kappa$ internally disjoint
rainbow paths and that $rc_k(G)$ is defined for every integer $k$
with $1 \leq k \leq \kappa$. Furthermore, $rc_k(G)\leq rc_j(G)$ for
$1\leq k\leq j\leq \kappa$.

The concept of rainbow $k$-connectivity has applications in
communication networks. For details we refer to \cite{Chartrand 2}
and \cite{Ericksen}.

In \cite{Chartrand 2},  Chartrand et al. studied the rainbow
$k$-connectivity of the complete graph $K_n$ for various pairs $k,
n$ of integers. It was shown in \cite{Chartrand 2} that for every
integer $k\geq 2$, there exists an integer $f(k)$ such that
$rc_k(K_n)=2$ for every integer $n\geq f(k)$. They also investigated
the rainbow $k$-connectivity of $r$-regular complete bipartite
graphs for some pairs $k, r$ of integers with $2\leq k\leq r$, and
they showed that for every integer $k\geq 2$, there exists an
integer $r$ such that $rc_k(K_{r,r})=3$.

This paper is to continue their investigation. We improve the upper
bound of $f(k)$ from $(k+1)^2$ to $ck^{\frac{3}{2}}+C$ (here $0<c<1$
and $C=o(k^{\frac{3}{2}})$), i.e., from $O(k^2)$ to
$O(k^{\frac{3}{2}})$, a considerable improvement. For notations and
terminology not defined here, we refer to \cite{Bondy}.

\section{Main Results}

In \cite{Chartrand 2} the following result was obtained.

\begin{thm}\label{thm1}(\cite{Chartrand 2}) For every integer $k\geq
2$, there exists an integer $f(k)$ such that if $n\geq f(k)$, then
$rc_k(K_n)=2$. \hfill \rule{4pt}{7pt}
\end{thm}

The authors in \cite{Chartrand 2} then obtained an upper bound
$(k+1)^2$ for $f(k)$, namely $f(k)\leq (k+1)^2$. In the following we
will give a better upper bound for $f(k)$.

Let $K_{\ell[r]}$ denote the complete $\ell$-partite graph each part
of which contains $r$ elements. Let $V=\bigcup_{s=1}^\ell{V_s}$
where $V_s=\{u_{s,1},u_{s,2},\cdots,u_{s,r} \}$ $(1\leq s\leq \ell)$
is the vertex set of each part, and
$U_j=\{u_{1,j},u_{2,j},\cdots,u_{l,j}\}$ $(1\leq j\leq r)$.

We consider the graph $G=K_{\ell^2[r]}$ where $\ell$ is an integer,
and give $G$ a 2-edge-coloring as follows: Let
$\overline{V_i}=\bigcup_{t=1}^{\ell}{V_{(i-1)\ell+t}}$ where $1\leq
i\leq \ell$. We know that the subgraph, denoted by $G_j$, of $G$
induced by $U_j$ is the complete graph $K_{\ell^2}$. Let
$U_j=U_{1,j} \cup \cdots \cup U_{\ell,j}$ where
$U_{i,j}=\{u_{(i-1)\ell+1,j},\cdots,u_{i\ell,j} \}$. Then the
subgraph, denoted by $G_{i,j}$, of $G$ induced by $U_{i,j}$ is the
complete graph $K_\ell$. Similar to the edge coloring in the proof
of Theorem \ref{thm1} in \cite{Chartrand 2}, we first give a
2-edge-coloring of each $G_j$ $(1\leq j\leq r)$ as follows: We
assign the edge $uv$ of $G$ the color 1 if either $uv \in
E(G_{i,j})$ for some $i(1\leq i\leq \ell)$ or if
$uv=u_{(i_1-1)\ell+t,j}~u_{(i_2-1)\ell+t,j}$ for some $i_1,i_2,t$
with $1\leq i_1,i_2,t\leq \ell$ and $i_1\neq i_2$. All other edges
of $G_j$ are assigned the color 2. With a similar argument to
Theorem \ref{thm1} in \cite{Chartrand 2}, there are $\ell-1$
disjoint rainbow $u-v$ paths for any two vertices $u, v$ in the
subgraph $G_j$ including 1 path of length 1 and $\ell-2$ paths of
length 2.

For other edges, that is, the edges between distinct $G_j$s, we use
above two colors as follows: Let $uv=u_{i_1,j_1}u_{i_2,j_2}$ where
$u_{i_1,j_1} \in G_{j_1}, u_{i_2,j_2}\in G_{j_2}$, we give it the
color different from the color of edge $u_{i_1,j_1}u_{i_2,j_1}$ of
graph $G_{j_1}$ or $u_{i_1,j_2}u_{i_2,j_2}$ of graph $G_{j_2}$
(since edges $u_{i_1,j_1}u_{i_2,j_1}$ and $u_{i_1,j_2}u_{i_2,j_2}$
have the same color by above coloring).

Next we will count the number of disjoint rainbow $u-v$ paths for
any two vertices $u,v$ of $G$ with above edge coloring. Without loss
of generality, let $u=u_{1,1}$. We consider four cases:

\textbf{Case 1}. $v=u_{1,j}$ $(2 \leq j\leq r)$, that is, $u$ and
$v$ are in the same part.

By above coloring, edges $u_{1,1}u_{s,j}$ and $u_{s,j}u_{1,j}$ have
distinct colors where $2 \leq s\leq \ell^2$, and so path
$u_{1,1},u_{s,j},u_{1,j}$ is a rainbow $u-v$ path. Similarly, path
$u_{1,1},u_{s,1},u_{1,j}$ is a rainbow $u-v$ path for each $2 \leq
s\leq \ell^2$. And any two such rainbow paths are disjoint, and so
there are at least $2(\ell^2-1)$ disjoint rainbow $u-v$ paths in
$G$.

\textbf{Case 2}. $v=u_{s,1}$ $(2\leq s\leq \ell^2)$, that is, $u$
and $v$ are in the same $G_j$ (here $j=1$).

Then in subgraph $G_1$ there are $\ell-1$ disjoint rainbow $u-v$
paths, and in each subgraph $G_j$ where $(2\leq j\leq r)$, there are
$\ell-2$ disjoint rainbow $u_{1,j}-u_{s,j}$ paths of length 2
$u_{1,j},y,u_{s,j}$ for some $y$s. Since the color of $u_{1,j}y$,
$yu_{s,j}$ is different from that of $u_{1,1}y$, $yu_{s,1}$,
respectively, paths $u_{1,1},y,u_{s,1}$ are $\ell-2$ disjoint
rainbow paths in each $G_j$ where $(2\leq j\leq r)$. So there are
totally $r(\ell-2)+1$ disjoint rainbow $u-v$ paths in $G$.

\textbf{Case 3}. $v=u_{s,j_0}$ where $2\leq s\leq \ell, 2\leq
j_0\leq r$, that is, $u$ and $v$ belong to the same $\overline{V_i}$
(here $i=1$) but in distinct parts and subgraphs $G_j$s.

At first, the edge $u_{1,1}u_{s,j_0}$ is a rainbow $u-v$ path.

Next we consider the monochromatic $u_{1,1}-u_{s,1}$ path
$u_{1,1},y, u_{s,1}$. Then each path $u_{1,1},y, u_{s,j_0}$ is a
rainbow $u_{1,1}-u_{s,j_0}$ path of length 2 where $2\leq s\leq
\ell, 2\leq j_0\leq r$. In $U_1$, we choose $y=u_{(i-1)\ell+t,1}$
where $1\leq i\leq \ell, 2\leq t\leq \ell$ and $t\neq s$. So there
are $\ell(\ell-2)$ such paths.

Similarly, there are $\ell(\ell-2)$ disjoint monochromatic
$u_{1,j_0}-u_{s,j_0}$ paths $u_{1,j_0},y,u_{s,j_0}$ where $y\in
U_{j_0}$ and we can obtain other $\ell(\ell-2)$ disjoint rainbow
$u-v$ paths.

Moreover, in each subgraph $G_j$ where $2\leq j\leq r$ and $j\neq
j_0$, there are $\ell-2$ disjoint rainbow $u_{1,j}-u_{s,j}$ path
$u_{1,j},y,u_{s,j}$ of length 2. Since the color of $u_{1,j}y$ and
$yu_{s,j}$ is different from that of $u_{1,1}y$ and $yu_{s,j_0}$,
respectively, paths $u_{1,1},y,u_{s,j_0}$ are disjoint rainbow $u-v$
paths.

So the number of disjoint rainbow $u-v$ paths in $G$ is
$1+2\ell(\ell-2)+(r-2)(\ell-2)=1+(2\ell+r-2)(\ell-2)$.

\textbf{Case 4}. $v=u_{{(i_0-1)\ell+t_0},j_0}$ where $2\leq i_0\leq
\ell, 1\leq t_0\leq \ell, 2\leq j_0\leq r$, this is, $v$ and $u$ are
in distinct $\overline{V_i}$s (here $v$ is not in $\overline{V_1}$).

\textbf{Subcase 4.1}. $t_0=1$.

Then edge $uv$ is a rainbow path. In subgraph $G_1$, we find the
monochromatic $u-u_{(i_0-1)\ell+1,1}$ path
$u,y,u_{(i_0-1)\ell+1,1}$. We choose any vertex of $U_1\setminus
\{U_{1,1}\cup U_{i,1}\}$ as $y$. Since the color of edge
$yu_{(i_0-1)\ell+1,1}$ is different from that of $yv$, each path
$u,y,v$ is rainbow, and there are $\ell^2-2\ell$ disjoint rainbow
$u-v$ paths.

Similarly, in subgraph $G_{j_0}$, we can find monochromatic paths
$u_{1,j_0},y,u_{(i_0-1)\ell+1,j_0}$, and get other $\ell^2-2\ell$
disjoint rainbow $u-v$ paths.

In each subgraph $G_j$ where $j\neq 1,j_0$, we find the disjoint
rainbow $u_{1,j}-u_{(i_0-1)\ell+1,j}$ paths
$u_{1,j},y,u_{(i_0-1)\ell+1,j}$ of length 2. Since the color of
$u_{1,j}y$ and $yu_{(i_0-1)\ell+1,j}$ is different from that of
$u_{1,1}y$ and $yu_{(i_0-1)\ell+1,1}$, respectively, there are
$\ell-2$ disjoint rainbow $u-v$ paths
$u_{1,1},y,u_{(i_0-1)\ell+1,1}$.

So the number of disjoint rainbow $u-v$ paths in $G$ is
$1+2\ell(\ell-2)+(r-2)(\ell-2)=1+(2\ell+r-2)(\ell-2)$.

\textbf{Subcase 4.2}. $t_0\neq 1$.

Then, edge $uv$ is a rainbow path. In subgraph $G_1$, we find the
monochromatic $u-u_{(i_0-1)\ell+t_0,1}$ path
$u,y,u_{(i_0-1)\ell+t_0,1}$. Let $y=u_{(i-1)\ell+t,1}$ where $i\neq
1, i_0, t\neq 1,t_0$ or $y=u_{t_0,1}$ or $u_{(i_0-1)\ell+1,1}$.
Since the color of edge $yu_{(i_0-1)\ell+t_0,1}$ is different from
that of $yv$, each path $u,y,v$ is rainbow, and so there are
$(\ell-2)(\ell-2)$+2 disjoint rainbow $u-v$ paths.

Similarly, in subgraph $G_{j_0}$, we can find monochromatic paths
$u_{1,j_0},y,u_{(i_0-1)\ell+1,j_0}$, and get other
$(\ell-2)(\ell-2)+2$ disjoint rainbow $u-v$ paths.

In each subgraph $G_j$ where $j\neq 1,j_0$, we find the disjoint
rainbow $u_{1,j}-u_{(i_0-1)\ell+t_0,j}$ paths
$u_{1,j},y,u_{(i_0-1)\ell+t_0,j}$ of length 2. Since the color of
$u_{1,j}y$ and $yu_{(i_0-1)l+t_0,j}$ is different from that of
$u_{1,1}y$ and $yu_{(i_0-1)l+t_0,j_0}$, respectively, there are
$\ell-2$ disjoint rainbow $u-v$ paths
$u_{1,1},y,u_{(i_0-1)\ell+t_0,j_0}$ (here $y\in G_j$ where $j\neq
1,j_0$).

So the number of disjoint rainbow $u-v$ paths in $G$ is
$5+2(\ell-2)(\ell-2)+(r-2)(\ell-2)=5+(2\ell+r-6)(\ell-2)$.

We know here $\ell\geq  2$, and so $5+(2\ell+r-6)(\ell-2)
>r(\ell-2)+1$. Clearly, $1+(2\ell+r-2)(\ell-2) >r(\ell-2)+1$. Let $\ell_0=\lceil
\max \{\sqrt{\frac{k}{2}+1},\frac{k-1}{r}+2 \}\rceil$. We then have
$2(\ell_0^2-1)\geq k$, $r(\ell_0-2)+1\geq k$. So, our following
theorem holds.

\begin{thm}\label{thm2}
For every integer $k\geq 2$, there exists an integer $\ell_0=\lceil
\max \{\sqrt{\frac{k}{2}+1},\frac{k-1}{r}+2 \}\rceil$, such that if
$\ell\geq \ell_0$, then $rc_k(K_{\ell^2[r]})=2.$ \hfill \rule{4pt}{7pt}
\end{thm}

Next we will consider the case for general complete multipartite
graph $G\cong K_{\ell[r]}$ with equal part, where $\ell\geq
\ell_0^2$. Let $\ell_1$ be the integer satisfying $\ell_1^2 \leq
\ell\leq (\ell_1+1)^2$ where $\ell_1 \geq \ell_0$. Then by our
Theorem \ref{thm2}, we need to consider the case $1\leq
q=\ell-\ell_0^2 \leq 2\ell_1$. Now $G$ can be obtained from
$K_{{\ell_1^2}[r]}$ by adding $q$ new parts $P_i$~($1\leq i\leq
q$). Let the vertex set of each corresponding new part be
$V(P_i)=\{v_{i,1},v_{i,2},\cdots,v_{i,r} \}~(1\leq i\leq q)$. We
now update $\overline{V_i}$ as follows: If $1\leq q\leq \ell_1$,
let the new $\overline{V_i}$ be the union of the old
$\overline{V_i}$ and $V(P_i)$; If $\ell_1< q \leq 2{\ell_1}$, let
the new $\overline{V_i}$ be the union of the old $\overline{V_i}$
and $V(P_i)\cup V(P_{\ell_1+i})$ (if there exists) as shown in the
Figure \ref{figure1}. Similarly, we update $U_j~(1\leq j\leq r)$
(also $G_j, U_{i,j}, G_{i,j}$) as shown in the Figure
\ref{figure1} (for example, the new $U_1$).

\begin{figure}[!hbpt]
\begin{center}
\includegraphics[scale=1.000000]{figure1.eps}
\end{center}
\caption{The figure of Theorem \ref{thm3}.}\label{figure1}
\end{figure}

Similar to the proof of Theorem \ref{thm1} in \cite{Chartrand 2}, we
give the 2-edge-coloring of graph $G$ as follows: For each
$G_j~(1\leq j\leq r)$, we assign the edge $uv$ of $G$ the color 1 if
either $uv \in E(G_{i,j})$ for some $i~(1\leq i\leq \ell_1)$ or if
$uv=u_{(i_1-1)\ell_1+t,j}~u_{(i_2-1)\ell_1+t,j}$ or
$uv=v_{i_1,j}~v_{i_2,j}$ or $uv=v_{\ell_1+i_1,j}~v_{\ell_1+i_2,j}$
for some $i_1,i_2,t$ with $1\leq i_1,i_2,t\leq \ell_1$ and $i_1\neq
i_2$. All other edges of $G_j$ are assigned the color 2.

For other edges, that is, edges between distinct $G_j$s, we use
above two colors as follows: If $uv=u_{i_1,j_1}~u_{i_2,j_2}$ where
$u_{i_1,j_1} \in G_{j_1}, ~u_{i_2,j_2}\in G_{j_2}$, we give it the
color different from that of edge $u_{i_1,j_1}~u_{i_2,j_1}$ of graph
$G_{j_1}$ or $u_{i_1,j_2}~u_{i_2,j_2}$ of graph $G_{j_2}$ (since
edges $u_{i_1,j_1}~u_{i_2,j_1}$ and $u_{i_1,j_2}~u_{i_2,j_2}$ have
the same color by above coloring); Similarly, color the edge for the
cases that $uv=u_{i_1,j_1}v_{i_2,j_2}$ and
$uv=v_{i_1,j_1}v_{i_2,j_2}$.

By the proof of our Theorem \ref{thm2}, there are at least $k$
disjoint rainbow paths connecting any two vertices $u,v \in
V(G)\setminus {\bigcup_{i=1}^q {V(P_i)}}$. We need to consider the
paths between $u,v$ where $u\in {\bigcup_{i=1}^q {V(P_i)}}$ and
$v\in V(G)$. Without loss of generality, let $u=v_{1,1}$, and we
consider four cases, which are similar to the four cases in the
proof of our Theorem \ref{thm2}.

\textbf{Case 1}.  $v\in V(P_1)$, that is, $u$ and $v=v_{1,j_0}$
$2\leq j_0\leq r$ are in the same part (here the part is $P_1$).

$G$ contains the disjoint rainbow $u-v$ paths $v_{1,1},y,v_{1,j_0}$,
and we let $y$ be the elements of $U_1 \cup U_{j_0} \setminus
\{v_{1,1}, v_{1,j_0} \}$. So the number of these paths is at least
$2\ell_1^2 \geq 2\ell_0^2 >2(\ell_0^2-1)\geq k$.

\textbf{Case 2}. $v\in U_1$, that is, $v$ and $u$ are in the same
subgraph $G_1$,

In $G_1$, there are at least $\ell_1-1$ rainbow $u-v$ paths; In each
$G_j$ $(2 \leq j\leq r)$ there are at least $\ell_1-2$ rainbow
$u'-v'$ paths of length 2: $u', y, v'$ where $u'$, $v'$ is in the
same part as $u$, $v$, respectively, and we get at least $\ell_1-2$
rainbow $u-v$ paths: $u, y, v$, where $y \in G_j$ $(2 \leq j\leq
r)$.

So the number of disjoint rainbow $u-v$ paths is at least
$1+r(\ell_1-2)\geq 1+r(\ell_0-2)\geq k$.

\textbf{Case 3}. $v \in \overline{V_1}$ but not in $U_1 \cup
V(P_1)$. Without loss of generality, let $v \in U_{j_0}$.

Then, edge $uv$ is a $u-v$ path.

\textbf{Subcase 3.1}. $v=v_{l+1,j_0}$.

Then similar to Case 3 in the proof of of Theorem \ref{thm2}, we
find the monochromatic $u-v_{l+1,1}$ path of length 2 in subgraph
$G_1$ and get at least $\ell_1^2$ disjoint rainbow $u-v$ paths.
Similarly, there are other $\ell_1^2$ disjoint rainbow $u-v$ paths
by finding the monochromatic $v_{1,j_0}-v_{\ell+1,j_0}$ paths in
$G_{j_0}$.

In each $G_j$ $(j\neq 1,j_0)$, similar to Case 3 in the proof of
Theorem \ref{thm2}, we get at least $\ell_1-2$ disjoint rainbow
$u-v$ paths of length 2 by finding rainbow $v_{1,j}-v_{\ell+1,j}$
paths in $G_j$.

So the number of disjoint rainbow $u-v$ paths is at least
$1+2\ell_1^2+
(r-2)(\ell_1-2)>1+2\ell_1(\ell_1-2)+(r-2)(\ell_1-2)=1+(2\ell_1+r-2)(\ell_1-2)\geq
1+(2\ell_0+r-2)(\ell_0-2)\geq k$.

\textbf{Subcase 3.2}. $v=u_{s_0,j_0}$ where $1\leq s_0 \leq \ell_1,
2\leq j_0\leq r$.

With a similar procedure to Subcase 3.1, we can get at least
$1+2\ell_1(\ell_1-1)+ (r-2)(\ell_1-2)> 1+(2\ell_1+r-2)(\ell_1-2)\geq
1+(2\ell_0+r-2)(\ell_0-2)\geq k$ rainbow disjoint $u-v$ paths in
graph $G$.

\textbf{Case 4}. $v$ is not in $\overline{V_1}$ and $U_1$, without
loss of generality, let $v \in \overline{V_2}\setminus U_1$. We
consider two subcases similar to Case 4 in the proof of Theorem
\ref{thm2}.

\textbf{Case 4.1}. $v=v_{2,j_0}$ where $2\leq j_0\leq r$.

Similar to Subcase 4.1 in the proof of Theorem \ref{thm2}, we can
get at least
$1+2\ell_1(\ell_1-2)+(r-2)(\ell_1-2)=1+(2\ell_1+r-2)(\ell_1-2) \geq
1+(2\ell_0+r-2)(\ell_0-2)\geq k$ disjoint rainbow $u-v$ paths in
$G$.

\textbf{Case 4.2}. $v\neq v_{2,j_0}$.

Similar to Subcase 4.2 in the proof of Theorem \ref{thm2}, we can
get at least
$1+2(\ell_1-1)(\ell_1-2)+(r-2)(\ell_1-2)=1+(2\ell_1+r-4)(\ell_1-2)
\geq 1+r(\ell_1-2)\geq 1+r(\ell_0-2)\geq k$ (since $\ell_1\geq 2$)
disjoint rainbow $u-v$ paths in $G$.

With above discussion, we have our following theorem:
\begin{thm}\label{thm3}
For every integer $k\geq 2$, there exists an integer $\ell_0=\lceil
\max \{\sqrt{\frac{k}{2}+1},\frac{k-1}{r}+2 \}\rceil$, such that if
$\ell\geq \ell_0^2$, then $rc_k(K_{\ell[r]})=2.$ \hfill \rule{4pt}{7pt}
\end{thm}

We now obtain a new graph $G'$ from $G$ by adding $p$ new vertices:
$w_1,w_2,\cdots,w_p$ $(1 \leq p\leq r-1)$ and edge $vw_j$ where
$1\leq j\leq p$ and $v \in V(G)$. Color the new edges as follows:
Give color 2 to edges between $U_j$ and $w_j$, and color 1 to other
edges.

Now we count the number of rainbow disjoint $u-v$ paths between any
two vertices of $G$. We need to consider the case that $u=w_j, v\in
V(G')$ $(1\leq j\leq p)$. Without loss of generality, let $u=w_1$.

\textbf{Case 1}. $v \in V(G)$.

\textbf{Subcase 1.1}. $v \in U_1$, without loss of generality, let
$v=u_{1,1}$.

Then $G$ contains the $u-v$ path $u,v$ as well as the $u-v$ rainbow
paths $w_1,y,u_{1,1}$ where $y \in {\overline{V_1}\setminus
\{u_{1,1},\cdots,u_{1,r}\}}$, or $y=u_{(i-1){\ell_1}+1,j} (2\leq
i\leq \ell_1, 1\leq j\leq r )$. So the number of disjoint rainbow
$u-v$ paths is at least $1+2r(\ell_1-1)
>1+r(\ell_0-2) \geq k$.

\textbf{Subcase 1.2}. $v$ is not in $U_1$, without loss of
generality, let $v=u_{1,2}$.

Then $G$ contains the $u-v$ path $u,v$ as well as the $u-v$ rainbow
paths $w_1,y,u_{1,2}$ where $y \in (U_1 \cup U_2) \setminus (U_{1,1}
\cup U_{1,2}\cup \{u_{(i-1){\ell_1+1,j_0}}\}_{i=1}^{\ell_1})$ where
$j_0=1,2$, or $y \in \{u_{(i-1){i_1}+1,j_1} \}_{i=2}^{\ell_1}$ where
$j_1\neq 1,2$, or $y= u_{s,j}$ where $2\leq s\leq \ell_1, j\neq 1,
2$. So the number of disjoint rainbow $u-v$ paths is at least
$1+2({\ell_1}-1)(\ell_1-1)+2(\ell_1-1)(r-2)=1+(\ell_1-1)(2\ell_1+2r-6)
>1+(\ell_1-2)(2\ell_1+2r-6)\geq 1+(\ell_1-2)r \geq k$(here we let $r\geq 2$).

\textbf{Case 2}. $v=w_j$ where $j\neq 1$.

Then $G$ contains the $u-v$ rainbow paths $w_1,y,w_j$ where $y\in
U_1 \cup U_j$. So the number of disjoint rainbow $u-v$ paths is at
least $2\ell_1^2 \geq 2\ell_0^2 >2(\ell_0^2-1) \geq k$.

If $r=1$, then $G'=G$ is complete, so by Theorem \ref{thm1} of
\cite{Chartrand 2} and above discussion, we have the following
theorem:
\begin{thm}\label{thm3}
Let $G$ be a complete $(\ell+1)$-partite graph with $\ell$ parts of
size $r \geq 1$ and a part of size $p$ where $1 \leq p <r$. Then for
every integer $k\geq 2$, if $\ell\geq \ell_0^2$ where $\ell_0=\lceil
\max \{\sqrt{\frac{k}{2}+1},\frac{k-1}{r}+2 \}\rceil$, then
$rc_k(G)=2.$ \hfill \rule{4pt}{7pt}
\end{thm}

We know that the graph in Theorem \ref{thm3} is a spanning
subgraph of the complete $K_{n}$ with $n=\ell r+p$ and $\ell\geq
\ell_0^2$. Now we let $r=r_0=\lceil \sqrt{2k}\rceil$, and $G$ be
the complete graph $K_n$ with $n \geq {\ell_0^2}r_0$. Then, since
$n={\ell_3}{r_0}+p$ where $\ell_3 \geq \ell_0^2, 0\leq p< r_0$, by
Theorem \ref{thm3} we have $rc_k(G)=2$, here $\ell_0= \lceil \max
\{\sqrt{\frac{k}{2}+1},\frac{k-1}{r}+2 \}\rceil = \lceil \max
\{\sqrt{\frac{k}{2}+1},\frac{k-1}{\lceil \sqrt{2k}\rceil}+2
\}\rceil$=$\lceil \frac{k-1}{\lceil \sqrt{2k}\rceil} \rceil+2$.
Thus we have

\begin{cor}\label{cor1}
For every integer $k \geq 2$, let integer $f(k)={\ell_0^2}r_0$. If
$n \geq f(k)$, then $rc_k(K_n)=2,$ where $\ell_0= \lceil
\frac{k-1}{\lceil \sqrt{2k}\rceil} \rceil+2$ and $r_0=\lceil
\sqrt{2k}\rceil$. \hfill \rule{4pt}{7pt}
\end{cor}

From Corollary \ref{cor1}, we know that for the integer $f(k)$, we
have that $f(k)\leq ck^{\frac{3}{2}}+C$ where $0< c< 1$ is a
constant and $C=o(k^{\frac{3}{2}})$, and this upper bound is a
considerable improvement of the bound given in Theorem \ref{thm1} of
\cite{Chartrand 2}.


\section{Introduction}
The study of QCD-like theories using a holographic approach has been a very fruitful line of investigation in the last few years.  Many qualitative features of QCD appear to be reproduced in these holographic models.  In particular, the Sakai-Sugimoto (SS) model \cite{ss1, ss2}, based on the dynamics of D8-branes and \Deighta-branes in the background of near-horizon D4 branes, has yielded many interesting results.  Most studies of the phase diagram \cite{asy, ps, bll1, ucla, stony, bll2, ubc, usc} have focused on the confined phase or on the interplay between the chiral-broken phase and chiral-symmetric phase in the deconfined phase as a function of external parameters such as temperature, density, and electromagnetic fields.

In this paper we will study relativistic interacting fermions at high density and strong magnetic field using this holographic description. This is done in the Sakai-Sugimoto model in the deconfined and chiral-symmetric phase. In this phase the low-energy excitations are charged fermions.

As shown in \cite{bll3, ll1}, when a magnetic field is turned on, the system behaves as if the charge is made out of two components, one which is represented holographically in the bulk by sources located at the horizon and the other by smeared D4-branes inside the D8-brane along the radial direction. The first behaves under an applied electric field as charges in a dissipative neutral medium and the second behaves as if no dissipation is present. In this letter we show that, for a given temperature and density, there is a first-order phase transition as a function of the magnetic field for which there is a jump of the charges of the first kind to charges of the second kind along with a jump in the magnetization.  A similar phenomenon in real materials where the magnetization grows rapidly is known as metamagnetism. The properties of the transition seem to indicate that it is consistent with a picture in which a phase transition of the fermions jumping to the lowest landau level has occurred. The  fermions in the lowest landau level seem to form baryonic-like bound states which are singlets under the $SU(N)$ and thus do not interact with the dissipative bath of gluons.

\section{The model background}

We will consider the SS D4-D8 system in the parallel phase. The D4-D8 intersection has $ND=6$
and so has as its lowest excitations only chiral fermions in four dimensions.
In the phase where the D8-branes and $D\bar{8}$-brane are parallel, chiral symmetry is unbroken
and we have both left- and  right-handed chiral fermions in the fundamental of $SU(N)$.
The fermions are charged under the U(1) symmetry on the D8-branes, and this interaction resembles electromagnetism but without dynamical photons. The system has two free parameters, $L$ which is the distance between the $D8$-brane and the $D\bar{8}$-brane, and the size
$R_{4}$ of the circle in the $x_{4}$ direction. The system goes through various phases
 as a function of these parameters and external conditions such as temperature,
density, and magnetic field. At low temperature the system is in the confined
phase and at higher temperature $T>\frac{1}{2\pi R_{4}}$ it is in the deconfined phase.
In the deconfined phase at high enough temperature (which depends on $L$) the system
 will be in the chiral-symmetric phase. The phase transition we will find occurs at any
 temperature and $L$ provided the density and magnetic fields are large enough.

The metric and background fields of the near horizon limit of the D4-branes is given by
\begin{eqnarray}
\label{deconfined_background}
ds^2 &=& u^{3\over 2} \left(f(u)(dx_0^E)^2 + d{\bf x}^2
+ dx_4^2\right)
+ u^{-{3\over 2}}\left({du^2\over f(u)}
+ u^2 d\Omega_4^2\right) \ , \nonumber\\
e^{\Phi} &=& g_s u^{3/4} \; , \;
F_4 = 3\pi (\alpha')^{3/2}  N_c \, d\Omega_4
\end{eqnarray}
where
\begin{equation}
f(u) = 1 - {u_T^3\over u^3}
\end{equation}
and $u=\frac{U}{R}$,  $x_{\mu}=\frac{X_{\mu}}{R}$, and  $R=(\pi g_{s}N_{c})^{1/3}\sqrt{\alpha'}$.  $u_T$ is related to the temperature, {\em i.e.} the inverse periodicity of the Euclidean time $x_0^E$, as $u_T=(4\pi/3)^2 R^2 T^2$.
In the holographic description the free energy is the action of the D8 branes in the near-horizon limit of the D4-branes.

Baryonic charge is identified with the charge under the $U(1)$ living on the D8-branes.  Adding charges to the system is accomplished by  sourcing the $A_{0}$ component of the $U(1)$ gauge field.  One can turn on a magnetic field in this $U(1)$ as $2\pi \alpha^{'}F_{23}=h$.  At zero magnetic field the charges sit at the horizon, but at non-zero magnetic field, due to the Chern-Simons term in the world volume action of the D8-brane which holographically encodes the axial anomaly, $A_{1}$ is turned on and induces a baryon charge proportional to $h$ along the D8-brane \cite{bll3}.  In addition, an anomaly-driven axial current $j_{A}=\frac{3}{2}h\mu$ is generated in the direction of the magnetic field.

Generally, when a magnetic field is turned on, for a fixed $L$, there is a possibility that the system will favor a chiral-broken phase. However, we can change $L$ at will and, for a given charge density (or chemical potential), delay breaking of chiral symmetry such that the magnetic phase transition occurs before the chiral phase transition. Whether this is true in QCD is hard to say.

\section{Four-dimensional holographic fermions}

The action of the D8 brane in this background includes both a Dirac-Born-Infeld (DBI)  term and a Chern-Simons (CS)
term which embodies the anomaly. Through the CS term the magnetic field couples the $A_{0}$ and the $A_{1}$ fields living on the D8 brane. We work with rescaled variables
\begin{equation}
a_{\mu}=\frac{2\pi \alpha'}{R}A_{\mu} \; , \; h=2\pi \alpha' F_{23}
\end{equation}
resulting in the action \cite{bll3}
\begin{eqnarray}
\label{action}
S_{DBI} &=&   {\cal{N}} \int_{u_T}^\infty du \, u^{5/2} \sqrt{\Big(1
-(a_0'(u))^2 + f(u)(a_1'(u))^2 \Big)\left(1+{h^2\over u^3}\right)} \nonumber \\[5pt]
S_{CS} & = &  - \frac{3}{2}{\cal N}
\int_{u_T}^\infty \left(h a_0(u) a^{'}_{1}(u)
-h a^{'}_{0}(u) a_1(u)\right),
\end{eqnarray}
where we have included both the 8-brane and anti-8-brane parts,
with $\bar{a}_0 = a_0$ and $\bar{a}_1=-a_1$, so
\begin{equation}
{\cal N}=\frac{N_c}{6\pi^{2}}\frac{R^2}{(2 \pi \alpha')^{3}} \ .
\end{equation}

The integrated equations of motion are then given by
\begin{eqnarray}
\label{EOMa0dec}
\frac{\sqrt{u^5+h^2 u^2}\, a_0'(u)}{\sqrt{1 - (a_0'(u))^2 + f(u)(a_1'(u))^2}}
&=& 3ha_1(u) + d \nonumber\\
\label{EOMa1dec}
\frac{\sqrt{u^5+h^2 u^2}\, f(u) a_1'(u)}{\sqrt{1 - (a_0'(u))^2 + f(u)(a_1'(u))^2}}
&=& 3ha_0(u)
\end{eqnarray}
where $d$ is the total rescaled charge density.\footnote{The baryon charge $d$ is related to the physical density D by $D=\frac{2 \pi \alpha' {\cal N}}{R}d$.  In these conventions, quarks (or, more generally, fermions) carry baryon charge $1$ rather than $1/N_c$.} The boundary conditions are $a_{0}(u_{T})=0$ and $a_{1}(\infty)=0$, and there is no constant appearing in the equation of motion for $a_{1}$ due to regularity at the horizon.

At non-zero magnetic field, some of the charge is found above the horizon and is represented by D4-branes smeared inside the D8-brane.  Like ordinary baryons which holographically correspond to D4-branes localized on the D8-brane, these smeared D4-branes have $N_c$ strings stretching between them and the D8-branes and so correspond holographically to bounds states of $N_c$ quarks.  The amount of charge located above a given $u$ is given by $-3ha_1(u)$, and the total charge in the form of smeared D4-branes $d_*$ is then just $d_* = -3ha_1(u_T)$.  The rest, $d-d_* = d+3ha_1(u_T)$, remains at the horizon.

After a little algebra, the equations of motion (\ref{EOMa0dec}) can be put in the form
\begin{eqnarray}
\label{EOMa0dec1}
a_{0}^{'2} &=& \frac{f (3ha_1 + d)^2}{fu^5+fh^2u^2+f (3ha_1 + d)^2-(3ha_0)^2} \nonumber\\
fa_{1}^{'2} &=& \frac{(3ha_0)^2}{fu^5+fh^2u^2+f (3ha_1 + d)^2-(3ha_0)^2} \ .
\end{eqnarray}

\subsection{Zero temperature}

At any non-zero temperature these equations can only be solved numerically. However, at zero temperature $f=1$, so one can actually solve these equations analytically\footnote{Note that at zero temperature one could in principle add a constant of integration to the once integrated $a_{1}$ equation of motion which represents a current in the system, but this is not relevant to our case.} up to a transcendental equation which is solved numerically. Of course, at zero temperature the chiral-symmetric phase is never the preferred phase \cite{ahjk}, but solving these equations in this case provides more control over the numerics and clarifies the results. As we will see, the numerical solution at low temperature is very close to the zero-temperature results.

To solve the zero-temperature equations, one notices that dividing the two equations in (\ref{EOMa0dec1}) gives
\begin{equation}
\frac{a_{0}^{'}}{a_{1}^{'}}=\frac{3ha_{1}+d}{3ha_{0}}
\end{equation}
which can be integrated using the boundary conditions $a_{1}(\infty)=0$ and $a_{0}(\infty)=\mu$.  One then finds that
\begin{equation}
(3ha_1 + d)^2-(3ha_0)^2=d^2-9h^2 \mu^2 \ .
\end{equation}

By defining a new coordinate
\begin{equation}
z=\int_{0}^{u} \frac{3h \ du}{\sqrt{u^5 +h^2 u^2 + d^2-9h^2 \mu^2}}
\end{equation}
where $z_{\infty}=z(u=\infty)$, the equations (\ref{EOMa0dec1}) reduce to
\begin{eqnarray}
\partial_{z} a_{0} &=& a_{1} +\frac{d}{3h} \nonumber \\
\partial_{z} a_{1} &=& a_{0} \ .
\end{eqnarray}
The solution to the equations of motion with the conditions $a_{0}(z=0)=0$ and $a_{1}(z=z_{\infty})=0$ is then
\begin{eqnarray}
a_{0} &=& \frac{d \sinh z}{3h\cosh z_{\infty}} \nonumber \\
a_{1} &=& \frac{d \cosh z}{3h\cosh z_{\infty}}-\frac{d}{3h} \ .
\end{eqnarray}
From these equations we see that
\begin{eqnarray}
\mu &=& \frac{d}{3h}\tanh z_{\infty} \nonumber \\
a_{1}(0) &=& \frac{d}{3h} \left(\frac{1}{\cosh z_{\infty}} -1\right) \ ,
\end{eqnarray}
and thus,
\begin{equation}
\label{zintegralequation}
z_\infty=\int_{0}^{\infty} \frac{3h \ du}{\sqrt{u^5 +h^2 u^2 + \frac{d^{2}}{\cosh^{2}z_{\infty}}}} \ .
\end{equation}

To find the actual solution for $z_{\infty}(h,d)$, one needs to solve (\ref{zintegralequation}) numerically.  We regularize the integral\footnote{Having to insert by hand a regulator is a particular feature of $T=0$.  At non-zero temperature, $u_T$ naturally cuts off integrals over $u$.} by taking the lower limit of the integral defining $z$ to be $\epsilon$ and at the end sending $\epsilon \rightarrow 0$.
For small $d$ and $h$ there are three solution for $z_{\infty}$, but for large enough $h$ only one remains which is $z_{\infty} \sim \log \epsilon  \rightarrow \infty$. Fig.~\ref{zinfinity_fig} illustrates the case where there are three solutions.

\begin{figure}
\centerline{\epsfig{file= zinfinity.eps,width=7cm}}
\caption{A plot showing the three solutions to the integral equation (\ref{zintegralequation}) for $z_{\infty}$ with $d=1$ and regulator $\epsilon = 10^{-3}$.  The dashed red curve is $z_{\infty}$ while the solid blue curve is the regulated integral on the right hand side of (\ref{zintegralequation}).  The values of $z_{\infty}$ at which the curves cross are solutions.  The regulator is responsible for the plateau in the integral; as $\epsilon$ is decreased, the plateau is pushed higher, and when $\epsilon \to 0$ the largest solution is $z_{\infty} = \infty$.}
\label{zinfinity_fig}
\end{figure}

It should be noted that the appearance of three solution and the interesting phase structure which they imply is due to the use of the full DBI action (\ref{action}) rather than just the Yang-Mills approximation.

The free energy of the three solutions is shown in Fig.~\ref{F_vs_h_zeroT_fig}.  At small $h$ the solution $z_{\infty}\sim h$ is preferred, but at some finite $h \sim 0.19$ there is a jump to the branch parametrized by $z_{\infty} \rightarrow \infty$.  This first-order phase transition is accompanied by jumps in both the magnetization and the chemical potential.

\begin{figure}
\begin{tabular}{cc}
\epsfig{file= F_vs_h_zeroT.eps,width=7cm} &
\epsfig{file= M_vs_h_zeroT.eps,width=7cm}
\end{tabular}
\caption{Three solutions for (a) the free energy $F$ and (b) the magnetization $M$ at $T=0$ with $d =1$.  There is a first-order phase transition from the solid blue $z_\infty \sim h$ solution to the dashed red $z_\infty \to \infty$ solution at $h = 0.19$.  The dotted grey solution, which corresponds to the middle solution in Fig.~\ref{zinfinity_fig}, connects the two stable solutions and is an unstable maximum of the free energy.}
\label{F_vs_h_zeroT_fig}
\end{figure}

As we can see, the preferred solution at large $h$ has
\begin{equation}
\label{muandF}
\mu=\frac{d}{3h} \ \ ,\ \ F=\frac{d^2}{6h} \ .
\end{equation}
We also find that $a_{0} = 0$ and $a_{1} = -\frac{d}{3h}$ are constant all the way up to $u \rightarrow \infty$ where they jump to their asymptotic values  $a_{0} = \mu$ and $a_{1} = 0$.  Not only is all the charge smeared inside the D8-branes, $d_* = d$, but it is in fact located right near the boundary at $u=\infty$.

\subsection{Non-zero temperature}

We now turn to solving these equations in the more physical case of non-zero temperature. We will see that the properties seen for zero temperature persist. At high temperature there is only one solution, which means a single phase. As the temperature is lowered, there is a critical temperature $T_{c}(d)$ below which one finds three solutions to the equations of motion for some range of $h$.  One way to see this in the numerics is to plot $a_{1}(\infty)$ as a function of $a_{1}(u_{T})$.  At high temperature the graph (at all values of $h$) cross the horizontal axis only once.  However, at lower temperature there is a range of $h$ when there are three possible values of $a_{1}(u_{T})$ which gives $a_{1}(\infty)=0$. This is shown in Fig.~\ref{F_vs_h_fig}(a).

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\epsfig{file= pg_vs_bg.eps,width=7cm} &
\epsfig{file=  F_vs_h.eps,width=7cm}
\end{tabular}
\caption{(a) Three solutions for $A_1(\infty)$ as a function of $A_1(u_T)$ for $n=1$, $T=0.07$, and $h =0.2$.  (b) The free energy $F$ as a function of $h$ for $n=1$ and $T=0.09$.  There are two stable branches, the solid blue curve and the dashed red curve. The phase transition, where the blue and red curves cross, is at $h=0.235$.}
\label{F_vs_h_fig}
\end{center}
\end{figure}

Again, one of the solution is unstable and two are stable. The free energy of the two stable solutions as a function of $h$ can be seen in Fig.~\ref{F_vs_h_fig}(b). We see that there is a phase transition at some non-zero value of $h$. At a temperature slightly higher then the critical temperature  both $\mu(h)$ and $M(h)$ develop what looks like a  wiggle; see Fig.~\ref{mu_and_M_vs_h_smooth_fig}.  As the temperature is lowered, we enter a regime where there is a phase transition; the chemical potential and the magnetization become discontinuous, as shown in Fig.~(\ref{mu_and_M_vs_h_jump_fig}).  At zero temperature, the jump of the chemical potential is such that the axial current $j_{A}=\frac{3}{2}h\mu$ attains its maximum value of $d/2$ and does not change any more as $h$ is increased.  This implies that in the large $h$ phase the system is fully polarized.  At non-zero temperature, $j_{A}$ jumps close to the maximum value and asymptotes to it at large $h$.  Similarly if we had turned on an axial chemical potential rather then a vector chemical potential, there would be a jump in the vector current in the direction of the magnetic field.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\epsfig{file= mu_vs_h_smooth.eps,width=7cm} &
\epsfig{file= M_vs_h_smooth.eps,width=7cm}
\end{tabular}
\caption{(a) $\mu$ and (b) $M$ are smooth functions of $h$ for $d=1$ and $T=0.102$ which is just above the critical point at $T=0.101$.}
\label{mu_and_M_vs_h_smooth_fig}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\epsfig{file= mu_vs_h_jump.eps,width=7cm} &
\epsfig{file= M_vs_h_jump.eps,width=7cm}
\end{tabular}
\caption{(a) $\mu$ and (b) $M$ as functions of $h$ for $d=1$ and $T=0.09$, below the critical point.  There are now two branches of stable solutions, and the phase transition between them occurs at $h = 0.235$.}
\label{mu_and_M_vs_h_jump_fig}
\end{center}
\end{figure}

To further describe the phase transition and to try to understand it better, we look at the value of the magnetic field at which the transition occurs as a function of the density and at fixed temperature.  The results are plotted in Fig.~\ref{d-T_critical_line_fig}(a) and closely fit
\begin{equation}
\label{phasetransition}
h \sim d^{2/3} \ .
\end{equation}
We also find that even at non-zero temperature the free energy of the phase at large $h$ is well-approximated by
\begin{equation}
F \sim \frac{d^{2}}{6h} \ .
\end{equation}
As was expected, the behavior here is similar to the zero-temperature case but with finite temperature corrections.  One qualitative difference is in the location of the charges in the high $h$ phase.   While almost all the charges are in the form of smeared D4-branes, they are no longer all near the boundary at $u=\infty$ but are instead spread across all values of $u$.

In terms of the behavior as a function of the temperature, we find that for a given charge density $d$ above a certain temperature there will be no phase transition for any $h$; thus, the line of first-order phase transitions ends at a critical point above which there is a smooth cross-over. The critical line in the $T-d$ plane above which there is no phase transition is given in Fig.~\ref{d-T_critical_line_fig}(b) and behaves at large $d$ as
\begin{equation}
T \sim \log d \ .
\end{equation}

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\epsfig{file=  d-h_phase_diagram.eps,width=7cm} &
\epsfig{file= d-T_critical_line.eps,width=7cm}
\end{tabular}
\caption{(a) The phase diagram in the $d$-$h$ plane at $T=0.07$, with the critical point at $d=0.16$ shown as a blue dot, and (b) the critical line in the $T$-$d$ plane.}
\label{d-T_critical_line_fig}
\end{center}
\end{figure}

It appears that no matter how high the temperature is, one can find a large enough density for which a phase transition will occur at some strong magnetic field.  Of course, at these parameters, for a given $L$, the preferred phase may be the chiral-broken phase.  However, as explained before, we can always take $L$ to be large enough that the chiral-symmetric phase is preferred.

\subsection{Transport properties}

The conductivity of this system was computed in \cite{ll1} with the result
\begin{eqnarray}
\sigma_{longitudinal} &=& \frac{\sqrt{u_{T}^{8}+h^2u_{T}^{5}+u_{T}^{3}(d-d^{*})^{2}}}{u_{T}^{3}+h^2} \nonumber\\
\sigma_{Hall} &=& -\frac{h(d-d_{*})}{{u_{T}^{3}+h^2}}-\frac{d^{*}}{h}
\end{eqnarray}
where, as before, $d_{*}=-3ha_{1}(u_{T})$ is the charge carried by the smeared D4 branes.  These charges, located above the horizon in $SU(N_c)$ singlet states, behave as if they do not interact with the dissipative bath.

The phase transition discussed above is a transition in which $d_{*}$ changes discontinuously.  Consequently, the transport properties also change discontinuously; the Hall conductivity grows and the longitudinal conductivity shrinks.  Note that at zero temperature, in accordance with Lorentz invariance, at any non-zero $h$ the longitudinal conductivity is zero and the Hall conductivity is $-d/h$.  Only at non-zero temperature do the different interactions with the dissipative bath result in a discontinuous conductivity.

Because the D4-branes are essentially smeared baryons made of a delocalized collection of quarks, one might have thought that gluons would at some level be able to interact with the individual quarks, leading to dissipation.  However, the thermal bath is holographically associated with the horizon, and since the smeared D4-branes are located above the horizon, their size in the boundary theory is much smaller than the wavelength of the thermal gluons.  As a result, as seen by the gluons, the D4-branes are effectively localized $SU(N_c)$ singlets with which they don't interact.

\section{Some interpretation}

To try to understand some of the physics of this transition, we explore the phase that is dominant at large $h$.  At least some of its properties are similar to the properties of a free, massless fermion gas in four dimensions in its lowest Landau level.

A massless fermion in four dimensions with charge $e$ in a magnetic field $B$ has the following energy spectrum:
\begin{equation}
E=\sqrt{k_{1}^{2}+2eBn}
\end{equation}
where $k_{1}$ is the momentum in the direction of the magnetic field and $n$ is a natural number labeling the Landau levels in the transverse directions. The degeneracy of each state is roughly $B$.  If all fermions are in the lowest Landau level, the energy of the gas is given by
\begin{equation}
E_{tot} \sim B\int_{0}^{k_{max}} dk \ k =\frac{1}{2} B k_{max}^{2} \ ,
\end{equation}
and the density of fermions is
\begin{equation}
n_{f}\sim B k_{max} \ ,
\end{equation}
giving a chemical potential and  energy
\begin{equation}
\label{freefermionmuandE}
\mu \sim \frac{n_f}{B}, \ \ \ E\sim \frac{n_{f}^{2}}{B} \ .
\end{equation}
The lowest Landau level is not spin degenerate, thus when there's a jump to the lowest Landau level, there is an increase in the magnetization.  We can estimate when the system crosses from the lowest to the first Landau level; this occurs when it is energetically favorable to increase $n$ rather than add to the parallel momentum, meaning $k^{2}_{max} \sim B$, which corresponds to
\begin{equation}
\label{freefermionphasetransion}
B \sim n_{f}^{2/3} \ .
\end{equation}

Many of the properties of the large $h$ phase agree with those expected from free fermions in the lowest Landau level in four dimensions.  The behavior of the free energy and chemical potential (\ref{muandF}) match the free fermion result (\ref{freefermionmuandE}), and phase transition (\ref{phasetransition}) resembles that of a transition into the lowest Landau level (\ref{freefermionphasetransion}).

On the supergravity side, in the large $h$ phase almost all the baryonic charge\footnote{At $T=0$ this will be all the baryonic charge.} is represented by smeared D4-branes that crept up the D8-brane.  Recently, there have been other indications that smeared D4-branes seem to be related to fermions in the lowest Landau level.  For example, in \cite{sonthom} it was argued that in the confined, large $h$, pion-gradient phase the smeared D4-branes also behave as if they are free fermions and reproduced the thermodynamics of the lowest Landau level.

As shown in \cite{bll3}, in the chiral-symmetric phase a baryon chemical potential in a background magnetic field generates an axial current.  This anomaly-driven current is also present in a gas of free fermions and is due only to the fermions in the lowest Landau level \cite{metzit}. In the supergravity description, since there is no constant of integration in equation (\ref{EOMa1dec}), the five-dimensional current is located above the horizon; consequently, the axial current is due to the smeared D4-branes rather than the charges at the horizon.

Furthermore, the smeared D4-branes holographically correspond to bound states of $N_c$ fermions, making up what look like smeared  baryons. This phenomena may be related to the fact that in the lowest Landau level fermions are confined to move only in one spatial dimension, and thus any attractive potential will make them bind, even one which would not bind them in three spatial dimensions.  Such an occurrence has been demonstrated to happen for a different situation related to the magnetically-induced chiral-symmetry breaking \cite{kabat}.

Because the Sakai-Sugimoto model provides a robust holographic model of QCD, it would be interesting to see if the phenomena described here could be found, for example, at RHIC in a strong magnetic field.  We see the onset of anomaly-driven behavior as soon as a magnetic field is turned on, but this may be an artifact of exactly massless quarks.  In real QCD, a very strong magnetic field may be required before any of these phenomena become manifest.

There are a few non-relativistic fermionic systems which resemble in some way the relativistic system discussed here.  In particular, several condensed matter systems also exhibit first-order quantum phase transitions with discontinuous magnetizations.  In the case of metamagnetism \cite{meta}, the magnetization, which comes from spin ordering, jumps due to a large increase in the density of states near the Fermi surface.  This effect sometimes occurs in paramagnetic materials with itinerant electrons in their outer shells.  The magnetization, as a function of the external magnetic field, can have a large rise and sometimes a discontinuity due to a rapid transition of many fermion spins from anti-parallel to the magnetic field to parallel.

Another phenomenon that can cause a jump in the magnetization is based on the de Haas-van Alphen (dHvA) effect which is due to orbital angular momentum.  At low temperature free fermions in four dimensions develop oscillations in their magnetization and chemical potential, among other quantities, as a function of the inverse magnetic field.\footnote{For a recent computation of these oscillations for massless fermions see \cite{cme}.}  These oscillations occur when the the Fermi surface sweeps through the Landau levels.

Because the charges feel both the background magnetic field and field produced by the other charges, the magnetization $M$ of the material is a function of the magnetic inductance $B$, which itself is a function of both $H$ and $M$.  The function $M(B)=M(H,M)$ may therefore have more then one solution for $M$ for a given $H$ if the dHvA oscillations become large \cite{pippard, condon}.  In this case, a first-order phase transition may occur when the system transitions from one Landau level to the next.  This phase transition, which happens in real metals only at very low temperatures, has been observed mainly in diamagnetic metals and is therefore called a diamagnetic phase transition.\footnote{For a review see \cite{gordon}.}  Depending on the geometry of the sample, the phase transition may lead either to a homogenous phase or to an inhomogeneous phase, with multiple Condon domains of different magnetisms.

The phase transition we find in the SS model appears to have some resemblance to metamagnetism but also some differences.  We start with a paramagnetic state and see a jump in the magnetization at a particular value of the magnetic field.  However, after the jump, the magnetization decreases, while in materials exhibiting metamagnetism, the phase after the transition is ferromagnetic.  In addition, while we find evidence the large magnetic field phase in the SS model is associated with the lowest Landau level, metamagnetism, which occurs at more modest magnetic fields, is not related to lowest Landau level physics.

The diamagnetic phase transition is associated with transitions between Landau levels, and it occurs each time the Fermi surface crosses a Landau level;  we, however, see only one phase transition rather than a whole series.  Indeed, in our system we do not observe the dHvA oscillations at all, even at zero temperature, which may indicate that there is no well-defined Fermi surface.\footnote{The absence of a signal of the Fermi surface was also observed in \cite{parna1}.} Furthermore, in the SS model, we have only a non-dynamical background electromagnetic field, thus $B=H$.  Hence, this is quite different than the diamagnetic phase transition.

We are left then without a truly compelling interpretation of our results.  In addition to serving as a holographic model of QCD, the SS model describes a system of strongly-coupled relativistic fermions, which to some degree reproduces phenomena seen in some condensed matter systems.  There seems to be some analogy with metamagnetism, but this analogy is incomplete.

\centerline{\bf{Acknowledgments}}
We wish to thank Alex Gordon and Ady Stern for very useful explanations and discussions. This work is supported in part by Israel Science Foundation under grant no. 568/05.