text:
# Universal extra dimensions and 𝑍→𝑏𝑏̄

## I Introduction

Models with large extra dimensions Arkani-Hamed:1998nn ; Arkani-Hamed:1998rs ; Antoniadis:1990ew ; Antoniadis:1994jp  have been extensively studied in recent years, and have served as a major source of inspiration in the ongoing search of physics beyond the Standard Model (SM). The general idea behind these scenarios is that the ordinary four dimensional SM emerges as the low energy effective theory of more fundamental models living in five or more dimensions with the extra dimensions compactified. The effects of the extra dimensions are communicated to the four dimensional world through the presence of infinite towers of Kaluza-Klein (KK) modes, which modify qualitatively the behavior of the low-energy theory. In particular, the non-renormalizability of the theory is found when summing the infinite tower of KK states. The size of the extra dimensions can be surprisingly large without contradicting present experimental data (see for instance Antoniadis:1994yi ; Pomarol:1998sd ; Antoniadis:1999bq ; Nath:1999mw ; Masip:1999mk ; Delgado:1999sv ; Rizzo:1999br ; Carone:1999nz ; Nath:1999fs ; Muck:2001yv ; Muck:2002er ). This offers the exciting possibility of testing these models in the near future, since the lowest KK states, if light enough, could be produced in the next generation of accelerators.

Extra dimensions may or may not be accessible to all known fields, depending on the specifics of the underlying, more fundamental theory. Scenarios where all SM fields live in higher dimensions have been the focal point of particular attention Carone:1999nz ; Appelquist:2000nn ). This type of extra dimensions is refered to in the literature as “universal extra dimensions” (UED). From the phenomenological point of view, the most characteristic feature of such theories is the conservation of the KK number at each elementary interaction vertex Carone:1999nz ; Appelquist:2000nn . As a result, and contrary to what happens in the non-universal case, the coupling of any excited (massive) KK mode to two zero modes is prohibited. This fact alters profoundly their production mechanisms: using normal (zero-mode) particles as initial sates, such modes cannot be resonantly produced, nor can a single KK mode appear in the final states, but instead they must be pair-produced. In addition, the conservation of the KK number leads to the appearance of heavy stable (charged and neutral) particles, which seem to pose cosmological complications (e.g. nucleosynthesis) Appelquist:2000nn ; however, one-loop effects may overcome such problems Servant:2002aq . Finally, this conservation yields the additional important feature that, the constraints on the size of the extra dimensions which are obtained from SM precision measurements are less stringent; this is so because the extra modes do not affect the tree-level predictions, and make their presence felt only through loop corrections. This last point merits particular attention, given its phenomenological importance, together with the fact that loop calculations in the context of such theories constitute a relatively unexplored territory.

In general the precision electroweak observables most sensitive to radiative corrections, whether from within the SM or from its extensions, are those enhanced by the large top-quark mass : $`R_b`$, or equivalently, the process $`Zb\overline{b}`$ Akhundov:1986fc ; Bernabeu:1988me ; Bernabeu:1991ws ; Beenakker:1988pv , the $`B\overline{B}`$ -mixing Buchalla:1996vs , and the $`\rho `$ parameter. These observables have already been considered in models with extra dimensions. Thus, $`R_b`$ was considered, for instance, in Papavassiliou:2000pq ; Appelquist:2000nn ; DelAguila:2001pu , $`B\overline{B}`$ was considered first in Papavassiliou:2000pq  and, recently, it has been studied in the context of UED in Chakraverty:2002qk ; Buras:2002ej , In the case of theories with UED the study of the corrections to the $`\rho `$ parameter has yielded a lower bound on the size of the compactification scale, the inverse of the compactification radious, $`R`$, of about 300 GeV Appelquist:2000nn . In this paper we will study in detail the bound obtained on the size of a single UED from the process $`Zb\overline{b}`$. Our experience with the radiative corrections induced by the SM particles suggests that the bounds obtained from this process could in principle be comparable to those extracted from the $`\rho `$ parameter; the reason is that the aforementioned enhancement induced by the dependence on the mass of the top-quark takes place in both cases. A simple one-loop calculation, motivated by the behavior of the theory in its gaugeless limit and subsequently corroborated by a more detailed analysis, reveals that, contrary to what has been claimed in Appelquist:2000nn , the leading corrections to the left-handed $`Zb\overline{b}`$ coupling, $`g_L`$, due to the KK modes corresponding to a single UED, display a strong dependence on the mass of the top-quark (they are proportional to $`m_t^4`$). This fact makes the bounds obtained from $`R_b`$ comparable to those obtained from the $`\rho `$ parameter; in particular we find $`R^1>300`$ GeV at 95% CL.

The paper is organized as follows: In section II we start from the five-dimensional Lagrangian and after standard manipulations we derive the corresponding four-dimensional interactions and mass spectrum, paying particular attention to the interactions involving top and bottom quarks. In section III we first discuss the physical arguments which suggest a strong dependence of the result on the top-quark mass; then we present a more detailed one-loop calculation which demonstrates precisely the announced leading behavior. The subleading corrections, e.g. terms suppressed by an additional factor $`𝒪(M_W^2/m_t^2)`$ are also estimated. Finally, in section IV we present our conclusions.

## II The Lagrangian

We will concentrate on the electroweak part, $`SU(2)_L\times U(1)_Y`$, of the SM Lagrangian, written in five dimensions; we will denote by $`x`$ the four normal coordinates, and by $`yx^4`$ the fifth one, which will undergo compactification.

The Lagrangian $``$ assumes the form

$$=_0^{\pi R}𝑑y(_A+_H+_F+_Y),$$
(1)
where

$`_A`$ $`=`$ $`{\displaystyle \frac{1}{4}}F^{MNa}F_{MN}^a{\displaystyle \frac{1}{4}}F^{MN}F_{MN},`$
$`_H`$ $`=`$ $`(D_M\mathrm{\Phi })^{}D^M\mathrm{\Phi }V(\mathrm{\Phi }),`$
$`_F`$ $`=`$ $`\overline{Q}(i\mathrm{\Gamma }^MD_M)Q+\overline{U}(i\mathrm{\Gamma }^MD_M)U+\overline{D}(i\mathrm{\Gamma }^MD_M)D,`$
$`_Y`$ $`=`$ $`\overline{Q}\stackrel{~}{Y}_u\mathrm{\Phi }^cU\overline{Q}\stackrel{~}{Y}_d\mathrm{\Phi }D+\text{h.c.}`$ (2)
In the above formulas $`M,N=0,1,2,3,4`$ are the five-dimensional Lorentz indices, $`F_{MN}^a=_MW_N^a_NW_M^a+gϵ^{abc}W_M^bW_N^c`$ is the field strength associated with the $`SU(2)_L`$ gauge group, and $`F_{MN}=_MB_N_NB_M`$ that of the $`U(1)_Y`$ group. The covariant derivative is defined as $`D_M_Mi\stackrel{~}{g}W_M^aT^ai\stackrel{~}{g}^{}B_MY`$, where $`\stackrel{~}{g}`$ and $`\stackrel{~}{g}^{}`$ are the five-dimensional gauge coupling constants of $`SU(2)_L`$ and $`U(1)_Y`$, respectively, and $`T^a`$ and $`Y`$ are the corresponding generators. $`\mathrm{\Gamma }_M`$ denote the five dimensional gamma matrices, $`\mathrm{\Gamma }_\mu =\gamma _\mu `$ and $`\mathrm{\Gamma }_4=i\gamma _5`$, and the metric convention is $`g_{MN}=(+,,,,)`$. The fermionic fields $`Q`$, $`D`$ and $`U`$ are four-component spinors and carry the same quantum numbers as the corresponding SM fields. $`SU(2)`$ and color indices have been suppressed. Finally, $`\mathrm{\Phi }`$ and $`\mathrm{\Phi }^c=i\tau ^2\mathrm{\Phi }^{}`$ denote the standard Higgs doublet and its charge conjugated field, and $`\stackrel{~}{Y}_u`$ are the Yukawa matrices in the five dimensional theory; they mix different generations, whose indices are suppressed. We do not include lepton or gluon couplings because they are not relevant for our discussion.

Next, as usual, we assume that the fifth dimension is compactified on a circle of radius $`R`$ in which the points $`y`$ and $`y`$ are identified (e.g. an orbifold $`S^1/_2`$). Fields even under the $`_2`$ symmetry will have zero modes and will be present in the low energy theory. Fields odd under $`_2`$ will only have KK modes and will disappear from the low energy spectrum. One chooses the Higgs doublet to be even under the $`_2`$ symmetry in order to have a standard zero mode Higgs field. Then we carry out the Fourier expansion of the fields,

$`A_\mu (x,y)`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{\pi R}}}A_\mu ^{(0)}(x)+{\displaystyle \frac{\sqrt{2}}{\sqrt{\pi R}}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}A_\mu ^{(n)}(x)\mathrm{cos}\left({\displaystyle \frac{ny}{R}}\right),`$
$`A_5(x,y)`$ $`=`$ $`{\displaystyle \frac{\sqrt{2}}{\sqrt{\pi R}}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}A_5^{(n)}(x)\mathrm{sin}\left({\displaystyle \frac{ny}{R}}\right),`$
$`Q(x,y)`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{\pi R}}}Q_L^{(0)}(x)+{\displaystyle \frac{\sqrt{2}}{\sqrt{\pi R}}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left[Q_L^{(n)}(x)\mathrm{cos}\left({\displaystyle \frac{ny}{R}}\right)+Q_R^{(n)}(x)\mathrm{sin}\left({\displaystyle \frac{ny}{R}}\right)\right],`$
$`U(x,y)`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{\pi R}}}U_R^{(0)}(x)+{\displaystyle \frac{\sqrt{2}}{\sqrt{\pi R}}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left[U_R^{(n)}(x)\mathrm{cos}\left({\displaystyle \frac{ny}{R}}\right)+U_L^{(n)}(x)\mathrm{sin}\left({\displaystyle \frac{ny}{R}}\right)\right],`$ (3)
where the expansion for $`A_\mu `$ applies to any of the gauge fields and (after suppressing the Lorentz index $`\mu `$) for the Higgs doublet, whereas that of $`A_5`$ applies to the fifth component of the gauge fields. Similarly, the expansion for $`U`$ is valid also for $`D`$. The above expansions allow us to carry out the standard $`y`$ integration in Eq. (1), and obtain the KK spectrum and the relevant interaction terms. We will mainly be interested in third generation quarks, thus, $`Q_t^{(n)}`$ and $`Q_b^{(n)}`$ will refer to the upper and lower parts of the doublet $`Q`$ and the $`U^{(n)}`$ will be KK modes of right-handed top quarks. In particular, the relation between the mass- and gauge-eigenstates of the KK quarks can be expressed as

$$\left[\begin{array}{c}Q_t^{(n)}\\ U^{(n)}\end{array}\right]=\left[\begin{array}{cc}\gamma _5\mathrm{cos}(\alpha _n^t)& \mathrm{sin}(\alpha _n^t)\\ \gamma _5\mathrm{sin}(\alpha _n^t)& \mathrm{cos}(\alpha _n^t)\end{array}\right]\left[\begin{array}{c}Q_t^{(n)}\\ U^{(n)}\end{array}\right],$$
(4)
and the mixing angle is given by $`\mathrm{tan}(2\alpha _n^t)=m_t/m_n`$, where $`m_nn/R`$. The case of $`Q_b^{(n)}`$ is similar but since we are neglecting all mass scales except $`m_t`$ and $`m_n`$ the mass eigenstate is simply $`Q_b^{(n)}=\gamma _5Q_b^{(n)}`$. The mass spectrum assumes the form (we remove the primes)

$$m_{Q_b^n}=m_n,m_{Q_t^n}=m_{U^n}=\sqrt{m_t^2+m_n^2}.$$
(5)
The couplings between the quarks and the scalar modes are important to our purposes, because they are proportional to $`m_t`$. In contrast to what happens within the SM, they will be physical degrees of freedom, i.e. they cannot be gauged away by choosing, for example, a unitary-type of gauge. After dimensional reduction, the fifth components of the charged gauge fields, $`W_5^{(n)}`$, mix with the KK modes of the charged component $`\mathrm{\Phi }^{(n)}`$ of the Higgs doublet. After diagonalization one obtains a physical boson, $`\mathrm{\Phi }_P^{(n)}`$, and a Goldstone boson $`\mathrm{\Phi }_G^{(n)}`$ that will contribute to the mass of the KK gauge bosons. In particular,

$`\mathrm{\Phi }_G^{(n)}`$ $`=`$ $`{\displaystyle \frac{m_nW_5^{(n)}+iM_W\mathrm{\Phi }^{(n)}}{\sqrt{m_n^2+M_W^2}}}\stackrel{\stackrel{n0}{M_W0}}{}W_5^{(n)},`$ (6a)
$`\mathrm{\Phi }_P^{(n)}`$ $`=`$ $`{\displaystyle \frac{iM_WW_5^{(n)}+m_n\mathrm{\Phi }^{(n)}}{\sqrt{m_n^2+M_W^2}}}\stackrel{\stackrel{n0}{M_W0}}{}\mathrm{\Phi }^{(n)}.`$ (6b)
As seen from the expansion, the $`W_5`$ has no zero mode, there is no physical zero mode $`\mathrm{\Phi }_P^{(0)}`$ and the zero mode Goldstone boson comes entirely from the zero mode Higgs field. On the other hand, for $`1/RM_W`$ the KK Goldstone bosons are mainly the $`W_5^{(n)}`$, while the physical scalars are mainly the KK modes of the Higgs doublet $`\mathrm{\Phi }^{(n)}`$. Their couplings are exactly the same as those of the Goldstone bosons of the SM, e.g.

$$_Y=\frac{\sqrt{2}}{v}m_tV_{tj}\overline{U}_R^{(n)}Q_{jL}^{(0)}\mathrm{\Phi }^{+(n)}+\text{h.c.},$$
(7)
where we have written only the third quark generation and in the following we will neglect the mixings, $`V_{tj}\delta _{tj}`$.

The electroweak symmetry breaking proceeds by minimizing a Higgs potential of the standard form, e.g. $`V(\mathrm{\Phi })=\mu ^2\mathrm{\Phi }^{}\mathrm{\Phi }+\stackrel{~}{\lambda }(\mathrm{\Phi }^{}\mathrm{\Phi })^2`$. The mass terms of the different KK scalar modes are given by $`m_{\mathrm{\Phi }^n}^2=\mu ^2+m_n^2`$, in such a way that if $`\mu <R^1`$ only the neutral component of the fundamental mode, $`\mathrm{\Phi }_0^{(0)}`$, gets a vacuum expectation value (VEV), $`\mathrm{\Phi }_0^{(0)}=v/\sqrt{2}`$. At low energy, when no KK modes can be produced, and at tree-level this model coincides exactly with the SM. In particular, the VEV of the zero mode Higgs doublet induces mixing between $`W_{\mu 3}^{(0)}`$ and $`B_\mu ^{(0)}`$ giving rise to a massless photon, $`A_\mu ^{(0)}`$, and a massive $`Z`$ boson, $`Z_\mu ^{(0)}`$.

After a bit of algebra one arrives to the expression of the couplings of the $`Z`$ boson with the KK modes of the rest of the fields, given by

$$_Z=\frac{g}{2c_w}Z_\mu ^{(0)}[J^{\mu (0)}+J^{\mu (n)}+J_\mathrm{\Phi }^{\mu (n)}],$$
(8)
where the $`J^{\mu (0)}`$ is the usual SM neutral current, and

$`J^{\mu (n)}`$ $`=`$ $`\left(1{\displaystyle \frac{4}{3}}s_w^2\right)\overline{Q}_t^{(n)}\gamma ^\mu Q_t^{(n)}\left(1{\displaystyle \frac{2}{3}}s_w^2\right)\overline{Q}_b^{(n)}\gamma ^\mu Q_b^{(n)}\left({\displaystyle \frac{4}{3}}s_w^2\right)\overline{U}^{(n)}\gamma ^\mu U^{(n)}+\mathrm{},`$
$`J_\mathrm{\Phi }^{\mu (n)}`$ $`=`$ $`(1+2s_w^2)\mathrm{\Phi }^{+(n)}i^\mu \mathrm{\Phi }^{(n)}+\text{h.c.}.`$ (9)
Here $`Q_t^{(n)}`$, $`Q_b^{(n)}`$ and $`U^{(n)}`$ are Dirac spinors, and the ellipses denote the contribution of $`D^{(n)}`$ fields, which are not relevant for our calculation. Similarly, the interaction of the charged bosons with the quarks is given by

$$_W=\frac{g}{\sqrt{2}}[\overline{b}_L\gamma ^\mu W_\mu ^{(n)}Q_{tL}^{(n)}i\overline{b}_LW_5^{(n)}Q_{tR}^{(n)}+h.c.].$$
(10)
The couplings of the photon may be derived similarly. From the above equations it is straightforward to extract the necessary Feynman rules for our calculations. The couplings of the photon may be derived similarly.

## III Calculating $`Zb\overline{b}`$

In this section we will compute the corrections to the effective $`Zb\overline{b}`$ coupling due to the presence of a single UED. Shifts in the $`Zb\overline{b}`$ coupling due to radiative corrections, either from within the SM or from new physics, affect observables such as the branching ratio $`R_b=\mathrm{\Gamma }_b/\mathrm{\Gamma }_h`$, where $`\mathrm{\Gamma }_b=\mathrm{\Gamma }(Zb\overline{b})`$ and $`\mathrm{\Gamma }_h=\mathrm{\Gamma }(Z\mathrm{hadrons})`$, or the left right asymmetry $`A_b`$. These type of corrections can be treated uniformly by expressing them as a modification to the tree level couplings $`g_{L(R)}`$ defined as

$$\frac{g}{c_W}\overline{b}\gamma ^\mu (g_LP_L+g_RP_R)bZ_\mu .$$
(11)
$`Z`$ and $`b`$’s are SM fields, $`P_{L(R)}`$ are the chirality projectors and

$`g_L`$ $`=`$ $`{\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{3}}s_W^2+\delta g_L^{\mathrm{SM}}+\delta g_L^{\mathrm{NP}},`$ (12a)
$`g_R`$ $`=`$ $`{\displaystyle \frac{1}{3}}s_W^2+\delta g_R^{\mathrm{SM}}+\delta g_R^{\mathrm{NP}},`$ (12b)
where we have separated radiative corrections coming from SM contributions and from new physics, (NP). It turns out that, both within the SM as well as in most of its extensions, only $`g_L`$ receives corrections proportional to $`m_t^2`$ at the one loop level, due to the difference in the couplings between the two chiralities. In particular, a shift $`\delta g_L^{NP}`$ in the value of $`g_L`$ due to new physics translates into a shift in $`R_b`$ given by

$$\delta R_b=2R_b(1R_b)\frac{g_L}{g_L^2+g_R^2}\delta g_L^{\mathrm{NP}},$$
(13)
and to a shift in the left-right asymmetry $`A_b`$ given by

$$\delta A_b=\frac{4g_R^2g_L}{(g_L^2+g_R^2)^2}\delta g_L^{\mathrm{NP}}.$$
(14)
These equations, when compared with experimental data, will be used to set bounds on the compactification scale.

By far the easiest way to compute the leading top-quark-mass dependent one-loop corrections to $`\delta g_L`$ from the SM itself, $`\delta g_L^{\mathrm{SM}}`$, is to resort to the gaugeless limit of the SM Lytel:1980zh , e.g. the limit where the gauge couplings $`g`$ and $`g^{}`$, corresponding to the gauge groups $`SU(2)_L`$ and $`U(1)_Y`$ respectively, are switched off. In that limit the gauge bosons play the role of external sources and the only propagating fields are the quarks, the Higgs field, and the charged and neutral Goldstone bosons $`G^\pm `$ and $`G^0`$. As explained in Barbieri:1993dq ; Barbieri:1992nz  one may relate the one-loop vertex $`Zb\overline{b}`$ to the corresponding $`G^0b\overline{b}`$ vertex by means of a Ward identity; the latter is a direct consequence of current conservation, which holds for the neutral current before and after the Higgs doublet acquires a vacuum expectation value $`v`$.

In practice, carrying out the calculation in the aforementioned limit amounts to the elementary computation of the one-loop off-shell vertex $`G^0b\overline{b}`$. In the gaugeless limit and for massless $`b`$-quarks the only contribution to this vertex is depicted in Fig. 1, where the cross in the top-quark line represents a top-quark mass insertion needed to flip chirality (an insertion in the other top-quark line is assumed). This diagram gives a derivative coupling of the Goldstone field to the $`b`$-quarks which can be gauged (or related to the $`Z`$ vertex through the Ward identity) to recover the $`Zb\overline{b}`$ vertex. Then, one immediately finds

$$\delta g_L^{\mathrm{SM}}\frac{\sqrt{2}G_Fm_t^4}{(2\pi )^4}\frac{id^4k}{(k^2m_t^2)^2k^2}=\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2},$$
(15)
where $`G_F`$ is the Fermi constant, and the $`m_t^4`$ dependence coming from three Yukawa couplings and one mass insertion is partially compensated by the $`1/m_t^2`$ dependence coming from the loop integral.

In the case of a single UED this argument persists: one must simply consider the analog of diagram in Fig. 1, where now the particles inside the loop have been replaced by their KK modes, as shown in Fig. 2. If we denote by $`\delta g_L^{UED}`$ the new physics contributions in the UED model (the SM contributions are not included) the result is

$`\delta g_L^{\mathrm{UED}}`$ $``$ $`{\displaystyle \frac{\sqrt{2}G_Fm_t^4}{(2\pi )^4}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{id^4k}{(k^2m_{Q_t^n}^2)^2(k^2m_n^2)}}`$ (16)
$`=`$ $`{\displaystyle \frac{\sqrt{2}G_Fm_t^4}{(4\pi )^2}}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle _0^1}{\displaystyle \frac{dxx}{xm_t^2+m_n^2}}{\displaystyle \frac{\sqrt{2}G_Fm_t^4}{(4\pi )^2}}{\displaystyle \frac{\pi ^2R^2}{12}},`$
and depends quartically on the mass of the top quark. Notice that there are several differences with respect to the SM: (i) The cross now represents the mixing mass term between $`Q_t^{(n)}`$ and $`U^{(n)}`$, which is proportional to $`m_t`$; (ii) The $`\mathrm{\Phi }^{\pm (n)}`$, for $`n0`$, are essentially the physical KK modes of the charged Higgses as shown in Eq.(6b); (iii) From the virtual momentum integration one obtains now a factor $`1/m_n^2`$, instead of the factor $`1/m_t^2`$ of the SM case.

This simple calculation allows us to understand easily the leading corrections arising from extra dimensions.

A more standard calculation of the $`Zb\overline{b}`$ vertex in UED yields exactly the same result.

In this case the radiative corrections to the $`Zb\overline{b}`$ vertex stem from the diagrams of Fig. 3.

If we neglect the $`b`$-quark mass and take $`M_ZR^1`$, the result, for each mode, can be expressed in terms of a single function, $`f(r_n)`$, defined as

$$i^{(n)}=i\frac{g}{c_w}\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2}f(r_n)\overline{u}^{}\gamma ^\mu P_Luϵ_\mu ,$$
(17)
where $`u`$ and $`u^{}`$ are the spinors of the $`b`$ quarks and $`ϵ_\mu `$ stands for the polarization vector of the $`Z`$ boson. The argument of the function $`f`$ is $`r_n=m_t^2/m_n^2`$.

Although the complete result is finite, partial results are divergent and are regularized by using dimensional regularization. The contributions of the different diagrams in Fig. 3 are

$`f^{(a)}(r_n)`$ $`=`$ $`\left(1{\displaystyle \frac{4}{3}}s_w^2\right)\left[{\displaystyle \frac{r_n\mathrm{log}(1+r_n)}{r_n}}\right],`$
$`f^{(b)}(r_n)`$ $`=`$ $`\left({\displaystyle \frac{2}{3}}s_w^2\right)\left[\delta _n1+{\displaystyle \frac{2r_n+r_n^22(1+r_n^2)\mathrm{log}(1+r_n)}{2r_n^2}}\right],`$
$`f^{(c)}(r_n)`$ $`=`$ $`\left({\displaystyle \frac{1}{2}}+s_w^2\right)\left[\delta _n+{\displaystyle \frac{2r_n+3r_n^22(1+r_n)^2\mathrm{log}(1+r_n)}{2r_n^2}}\right],`$
$`f^{(d)}(r_n)+f^{(e)}(r_n)`$ $`=`$ $`\left({\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{3}}s_w^2\right)\left[\delta _n+{\displaystyle \frac{2r_n+3r_n^22(1+r_n)^2\mathrm{log}(1+r_n)}{2r_n^2}}\right],`$ (18)
where $`\delta _n2/ϵ\gamma +\mathrm{log}(4\pi )+\mathrm{log}(\mu ^2/m_n^2),`$ and $`\mu `$ is the ’t Hooft mass scale. From Eq. (18) it is straightforward to verify that all terms proportional to $`\delta _n`$ cancel, and so do all terms proportional to $`s_w^2`$, as expected from the gaugeless limit result. Thus, finally, the only term which survives is the term in $`f^{(a)}(r_n)`$ not proportional to $`s_w^2`$, yielding the following (per mode) contribution to $`g_L`$:

$$\delta g_L^{(n)}=\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2}\left[\frac{r_n\mathrm{log}(1+r_n)}{r_n}\right],$$
(19)
which is precisely the one obtained from the gaugeless limit calculation, e.g. Eq. (16) with the elementary integration over the Feynman parameter $`x`$ already carried out. Notice also that the above result is consistent with the decoupling theorem since the contribution for each mode vanishes when its mass is taken to infinity, e.g. $`r_n0`$.

In order to compute the effect of the entire KK tower, it is more convenient to first carry out the sum and then evaluate the Feynman parameter integral; this interchange is mathematically legitimate since the final answer is convergent. Thus,

$$\delta g_L^{\mathrm{UED}}=\underset{n=1}{\overset{\mathrm{}}{}}\delta g_L^{(n)}=\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2}_0^1𝑑x\underset{n=1}{\overset{\mathrm{}}{}}\frac{r_nx}{1+r_nx}=\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2}F_{\mathrm{UED}}(a),$$
(20)
where $`a=\pi Rm_t`$, and

$`F_{\mathrm{UED}}(a)`$ $`=`$ $`{\displaystyle \frac{1}{2}}+{\displaystyle \frac{a}{2}}{\displaystyle _0^1}𝑑x\sqrt{x}\mathrm{coth}(a\sqrt{x})`$ (21)
$``$ $`{\displaystyle \frac{a^2}{12}}{\displaystyle \frac{a^4}{270}}+𝒪(a^6).`$
It is instructive to compare the above result with the one obtained in the context of models where the extra dimension is not universal. In particular, in the model considered in Papavassiliou:2000pq  the fermions live in four dimensions, and only the gauge bosons and the Higgs doublet live in five Pomarol:1998sd . In this case there is no KK tower for the fermions, and therefore, in the loop-diagrams appear only the SM quarks interacting with the KK tower of the Higgs fields. The result displays a logarithmic dependence on the parameter $`a`$, which gives rise to a relatively tight lower bound on $`R^1`$, of the order of 1 TeV. Specifically, the corresponding $`F(a)`$ is given by<sup>1</sup><sup>1</sup>1Note that, unlike in ref. Papavassiliou:2000pq , the $`F(a)`$ does not include the SM contribution.

$`F(a)`$ $`=`$ $`1+2a{\displaystyle _0^{\mathrm{}}}𝑑x{\displaystyle \frac{x^2}{(1+x^2)^2}}\mathrm{coth}(ax)`$ (22)
$``$ $`\left({\displaystyle \frac{2}{3}}\mathrm{log}(\pi /a){\displaystyle \frac{1}{3}}{\displaystyle \frac{4}{\pi ^2}}\zeta ^{}(2)\right)a^2,`$
where the expansion on the second line holds for small values of $`a`$, and $`\zeta ^{}`$ is the derivative of the Riemann Zeta function. The appearance of the $`\mathrm{log}(a)`$ in $`F(a)`$ and its absence from $`F_{\mathrm{UED}}(a)`$ may be easily understood from the effective theory point of view. Due to the KK-number conservation in UED models, the tree-level low energy effective Lagrangian when all KK modes are integrated out is exactly the Standard Model; there are no additional tree-level operators suppressed by the compactification scale. Since one-loop logarithmic contributions, $`\mathrm{log}(a)`$, can be obtained in the effective theory by computing the running of operators generated at tree level, it is clear that in the UED no $`\mathrm{log}(a)`$ can appear at one loop in low energy observables. The situation is completely different if higher dimension operators are already generated at tree level, as is the case of the model considered in ref. Papavassiliou:2000pq , where the leading logarithmic corrections can be computed by using the tree-level effective operators in loops.

We next turn to the bounds on $`R^1`$. We will use the SM prediction $`R_b^{\mathrm{SM}}=0.21569\pm 0.00016`$ and the experimentally measured value $`R_b^{\mathrm{exp}}=0.21664\pm 0.00068`$. Combining Eq. (13) and Eq. (20), we obtain $`F_{\mathrm{UED}}(a)=0.24\pm 0.31`$, and making a weak signal treatment Feldman:1998qc  we arrive at the 95% CL bound $`F_{\mathrm{UED}}(a)<0.39`$. The results for a single UED can be easily derived from (21), yielding

$$R^1>230\text{GeV}.$$
(23)
The SM prediction for the left-right asymmetry $`A_b^{SM}=0.9347\pm 0.0001`$ and the measured value $`A_b^{exp}=0.921\pm 0.020`$ gives a looser bound.

Above we have computed only the leading contribution, which goes as $`G_Fm_t^4R^2`$. There are also formally subleading contributions, suppressed by (at least) an additional factor $`M_W^2/m_t^2`$; given that this factor is not so small such corrections could be numerically important, and should be estimated. The dominant contributions of this type come from diagrams with $`W_\mu ^{\pm (n)}`$ and $`W_5^{\pm (n)}`$ running in the loops. Since these corrections are still proportional to $`m_t^2`$ they can be estimated using again the Ward identity that relates the $`G^0`$ couplings to the $`Z`$ couplings. The relevant diagrams are shown in Fig. 4.

Their contribution modify the value of $`\delta g_L^{\mathrm{UED}}`$ as follows:

$$\delta g_L^{\mathrm{UED}}=\frac{\sqrt{2}G_Fm_t^2}{(4\pi )^2}F_{\mathrm{UED}}(a)\left(1+3\frac{M_W^2}{m_t^2}\right).$$
(24)
Taking these corrections into account leads to a slight modification of the bound on the compactification scale, $`R^1>300\text{GeV}`$. Evidently, this bound is absolutely comparable to the one obtained from the $`\rho `$ parameter.

## IV Conclusions

We have computed the leading contributions, for a large top-quark mass, to $`Zb\overline{b}`$ in a model with one universal extra dimension. These contributions depend quartically on the top-quark mass and can be evaluated easily in the gaugeless limit of the theory, where only one diagram contributes.

There are subleading corrections, formally suppressed by a factor $`M_W^2/m_t^2`$, which, in principle, can be important. We have estimated them by considering the diagrams with the KK modes of the $`W^{(n)}`$ and the $`W_5^{(n)}`$ running in the loop, and found that they contribute a $`+65\%`$ of the correction.

None of the contributions contains logarithmic ($`\mathrm{log}(R)`$) corrections. This can be understood from the KK-number conservation, which leads to the absence of tree-level low-energy operators (containing only SM fields). These results have been used to set a bound on the compactification scale $`R^1>300`$ GeV at 95% CL which is comparable to the bounds obtained from the contributions of KK modes to the $`\rho `$ parameter Appelquist:2000nn  in this model, and which is much weaker than bounds obtained in models with no KK-number conservation Papavassiliou:2000pq .

What are the consequences of these results for further studies of UED in b-physics? In Bernabeu:1997zh  it was shown that the vertex $`Zb\overline{b}`$ and $`B\overline{B}`$ mixing are highly correlated, and that it is very difficult to obtain a relatively large contribution to $`B\overline{B}`$ mixing evading the bounds coming from $`R_b`$. This was corroborated explicitly in Papavassiliou:2000pq  in a model with only scalars and gauge bosons in extra dimensions. Recently $`B\overline{B}`$ mixing has also been considered in UED Chakraverty:2002qk ; Buras:2002ej . Although the simple argument, developed in Bernabeu:1997zh , was based on the logarithmic corrections and it is not applicable in the case of UED because of the absence of logarithmic corrections both in $`Zb\overline{b}`$ and in $`B\overline{B}`$ mixing, we believe that some correlation still exists. This will be further explored in a future work.

###### Acknowledgements.

This work has been funded by the MCYT under the Grant BFM2002-00568, by the OCYT of the “Generalitat Valenciana” under the Grant GV01-94 and by the CICYT under the Grant AEN-99-0692.


format: text

text:
# Magnetic nanographite

## Abstract

Hydrogenated nanographite can display spontaneous magnetism. Recently we proposed that hydrogenation of nanographite is able to induce finite magnetization. We have performed theoretical investigation of a graphene ribbon in which each carbon is bonded to two hydrogen atoms at one edge and to a single hydrogen atom at another edge. Application of the local-spin-density approximation to the calculation of the electronic band-structure of the ribbon shows appearance of a spin-polarized flat band at the Fermi energy. Producing different numbers of mono-hydrogenated carbons and di-hydrogenated carbons can create magnetic moments in nanographite.

preprint: Mag-nano-2002

Recent reports on magnetic carbon have stimulated renewed interest in carbon systems as possible new magnetic materials made exclusively of light elements. These investigations include experiments suggesting ferromagnetic behavior in polymerized fullerenes made using photo-assisted oxidationMurakami and Suematsu (1996) or high-pressure treatment.Makarova et al. (2001) A nanometer-scale graphite called nanographite may yield another magnetic carbon system. Some experiments have demonstrated the existence of anomalous magnetic behavior unexpected in diamagnetic bulk graphite.Shibayama et al. (2000); Prasad et al. (2000); Kopelevich et al. (2000)

Several theoretical investigations of nanographite have been carried out prior to or parallel to these experiments.Fujita et al. (1996); Nakada et al. (1996); Fujita et al. (1997); Wakabayashi et al. (1998); Miyamoto et al. (1999); Harigaya (2001a, b); Okada and Oshiyama (2001); Harigaya and Enoki (2002) An important finding was that $`\pi `$ electrons in nanometer-scale graphite are strongly affected by structure of edges. A typical edge is the zigzag edge. The zigzag edge was found in STM images of nanometer scale graphene,Land et al. (1992); Nagashima et al. (1994) although the armchair edge has lower energy than the zigzag edge.Thess et al. (1996); Lee et al. (1997) Fujita and coworkers suggested that the $`\pi `$ electrons on a mono-hydrogenated zigzag edge may create a ferrimagnetic spin structure on the edge.Fujita et al. (1996) Magnetism with localized spin moments is possible due to the existence of non-bonding localized states at the zigzag edge. These states are called edge states and are highly degenerate at the Fermi level and may be spin polarized. Such an edge state does not appear on an armchair edge. Klein has studied another edge of graphene strips, considering a zigzag edge with an atomic site having a $`\pi `$-orbital on the edge.Klein (1994); Klein and Bytautas (1999) Examining a tight-binding model of $`\pi `$ electrons, he found degenerate surface states on the edge, which is referred to here as a bearded edge.

The total spin moment of a graphene ribbon, however, should be zero, if both of the two edges of the ribbon are zigzag edges, or if both of them are bearded edges. This is because, the structure of the $`\pi `$ network becomes a bipartite lattice having the same number of sublattice sites. In such cases, an argument using the Hubbard model results in zero spin moment, following the Lieb theorem.Fujita et al. (1996); Lieb (1989) Naively, we may say that local magnetic moments at the two edges are coupled anti-ferromagnetically.Fujita et al. (1996)

In this paper, we show that a hydrogenated graphene ribbon can have a finite total magnetic moment. A key point is the structure of the two edges of the ribbon. In our ribbon, one of the edges is composed of mono-hydrogenated carbon atoms and another is made of di-hydrogenated ones. By a first-principles electronic-state calculation, we will show that the system is stable and has a fully spin-polarized flat band. A finite spontaneous magnetization appears in the graphene ribbon.

We present here our idea to find magnetic nanographite. If a graphene ribbon has a bearded edge on one side and a zigzag edge on the other side, the $`\pi `$ network becomes a bipartite lattice with different numbers of sublattice sites.Wakabayashi and Sigrist (2000); Kusakabe and Takagi (2002) Then, a flat band appears at the Fermi level. The band is fully spin polarized if inter-electron interactions e.g. the Hubbard repulsion $`U`$ is considered.Lieb (1989) In addition, the flat band consists of edge states, so that the magnetic moments are localized at both edges and the distribution of moments shows exponential decay in the $`\pi `$ network.Kusakabe and Takagi (2002) However, to design a realistic material, we also have to specify the atomic configuration of the bearded edge.

We found that one solution is a zigzag edge whose end carbon atoms are di-hydrogenated.Kusakabe and Maruyama (2002) In order to present an example of magnetic nanographite, we will show the electronic band structure of the ribbon which has a completely spin-polarized flat band at the Fermi energy. The magnetism will be explained using a Hubbard model.

To investigate the stability and magnetic structure of the nanographite, we used an electronic-state calculation with a local spin-density approximation (LSDA) based on the density functional theory.Hohenberg and Kohn (1964); Kohn and Sham (1965) An LSDA functional given by Perdew and WangPerdew and Wang (1992) was utilized as the exchange-correlation energy functional. The ultra-soft pseudopotential generated using the Vanderbilt strategy was adopted.Vanderbilt (1990) The valence wave functions were expanded in a plane-wave (PW) basis set. To achieve convergence in the total energy, we used an energy cut-off $`E_c`$ of 49Ry for structural optimization in a fixed unit cell. To reduce computation time, we adopted $`E_c=25`$Ry to optimize the size of the unit cell before the final optimization of inner coordinates. Structural optimization was performed until each component of the interatomic force became less than $`8\times 10^5`$ H/a.u. The calculations were done using a computer program called the Tokyo ab-initio program package (TAPP).Yamauchi et al. (1996)

To check the accuracy of our calculation, we obtained the structural parameters of a hydrogen molecule, a CH4 molecule, a C2H4 molecule, diamond and graphite. The bond length of each molecule and the bond angles of CH4 and C2H4 were obtained with relative errors less than 3.3%. The vibrational energy $`\mathrm{}\omega _e`$ of H2 was $`1.92\times 10^2`$ \[H\], which is about 4% smaller than $`2.00\times 10^2`$ \[H\] observed. For cubic diamond, the lattice constant, the bulk modulus and its pressure derivative were 6.677 a.u., 4.66 Mbar and 3.68. For hexagonal graphite, the lattice constants were $`a=4.616`$ a.u. and $`c=12.67`$ a.u. These values are in reasonable agreement with the values determined experimentally or by previous calculations.Furthmuller et al. (1994) Band structures of the solids also reproduced previous results.Furthmuller et al. (1994)

Consider the graphene ribbon shown in Fig. 1. In this structure, each dark circle represents the position of a carbon atom. Solid lines represent $`\sigma `$ bonds. Each open circle is a hydrogen atom. For convenience, we number atoms and name them C(1) $`\mathrm{}`$ C(2n) and H(1) $`\mathrm{}`$ H(3) in a unit cell. Here, $`n`$ is a positive integer. On the left edge, each carbon atom is bonded to a hydrogen atom and has a $`\pi `$ orbital. On the right edge, each carbon atom has bonds to two hydrogen atoms and two neighboring carbon atoms. If we consider that the di-hidrogenated carbon atom C(2n) forms sp3 bonds instead of sp2 bonds, C(2n) loses a $`\pi `$ electron. Since there remain $`2n1`$ carbon atoms having a $`\pi `$ electron per each in a unit cell, the $`\pi `$ network might become a bipartite lattice with different numbers of sublattice sites.

We can consider ribbons with various widths. However, we know that the optimum width is given by $`n510`$ for nanographite ribbons with zigzag edges.Nakada et al. (1996) In any case, the essential properties should be the same irrespective of the width. Thus we first consider a ribbon with $`n=5`$ and discuss dependence of magnetism on the width of the graphene ribbon at the end of the paper.

To examine our idea, we have performed an LSDA calculation. Below, we assume a periodic boundary condition. Since the structure is one-dimensional, we are allowed to use $`k`$ points along the $`y`$ axis as $`(0,k_y,0)`$ for the structural optimization. We used 6 $`k`$ points uniformly distributed in the Brillouin zone for most simulations. We determined the equilibrium lattice constant of the ribbon, which became 4.674 a.u. For the calculation to optimize the inner parameters, the size of the cell was taken to be 40.27 $`\times `$ 4.647 $`\times `$ 18.60 (a.u.)3. The spacing between neighboring ribbons became 19.5 a.u. in the $`x`$ direction and 15.3 a.u. in the $`z`$ direction. The structure was optimized by a conjugate gradient method. The obtained results did not change when we used 12 $`k`$ points instead. The bond length of C-C ranged from about 2.64 $``$ 2.70 a.u. for neighboring carbon pairs except for 2.59 a.u. between C(8) and C(9) and 2.76 a.u. between C(9) and C(10). Bond angles H(2)-C(10)-H(3) and C(9)-C(10)-C(9) are 100.7 and 114.8. These structure parameters suggest that the end carbon C(10) forms sp3 bonds.

An electronic band structure of the graphene ribbon is shown in Fig. 2. In the first Brillouin zone, the $`\mathrm{\Gamma }`$-Y line corresponds to a one-dimensional axis on which a $`k`$ vector is parallel to the ribbon. A flat band appears at the Fermi level. The band is almost dispersionless in the whole Brillouin zone and is completely spin polarized. That is, only the spin-up branch is filled and the spin-down branch is empty. Splitting between polarized flat bands for up-electrons and down-electrons is approximately 0.5 $``$ 0.6 eV and the gap between them is $`0.2`$ eV. These values give a rough energy scale of stiffness for the magnetic ground state. The total spin $`S_{tot}`$ becomes 1/2 times number of unit cells $`N_c`$. Stability of the polarized flat band was confirmed by using a unit cell which was doubled in the $`y`$ direction.

The flat band is the center band of 9 well-characterized $`\pi `$-bands. See band dispersion around the $`Y`$ point in Fig. 2. The dispersion relation of these $`\pi `$ bands is roughly the same as those obtained for a simple tight binding model with 9 $`\pi `$-orbitals on a graphene ribbon. In Fig. 2, all branches for up-electrons and down-electrons are split by spin polarization. This result implies that a magnetic moment appears on every atom. We show obtained spin density in Fig. 3. A ferrimagnetic spin structure is clearly seen. A local spin moment exists on every carbon atom. Interestingly, finite spin moments appear on two hydrogen atoms which have bondings with C(10). The reason will be explained below. Thus, the graphene ribbon is confirmed to be magnetic in the LSDA model. We call this structure magnetic nanographite.

We found a curious characteristic of the wave functions of the flat band. We surmise that only 9 carbon atoms in the unit cell possess $`\pi `$ orbitals which contribute to the $`\pi `$ bands. This is because sp3 bonds are created at the di-hydrogenated carbon atom C(10). Wave functions on the flat band were non-bonding edge states with finite amplitude on only odd-numbered carbon atoms, but not on even-numbered ones. An interesting point is that a finite amplitude was found on two hydrogen atoms H(2) and H(3). Therefore, we have to consider 1s orbitals on these hydrogen atoms in order to analyze the spin-polarized flat band.

Let us introduce two sets of orthogonal coordinates, $`(xyz)`$ and $`(x^{}y^{}z^{})`$ as defined in Fig. 1. Four sp3 orbitals on C(10) may be represented as $`\varphi _1=\varphi _s+\varphi _x^{}+\varphi _y^{}+\varphi _z^{}`$, $`\varphi _2=\varphi _s\varphi _x^{}\varphi _y^{}+\varphi _z^{}`$, $`\varphi _3=\varphi _s+\varphi _x^{}\varphi _y^{}\varphi _z^{}`$, and $`\varphi _4=\varphi _s\varphi _x^{}+\varphi _y^{}\varphi _z^{}`$. Here, $`\varphi _s`$ is a 2s orbital and $`\varphi _m`$ ($`m=x^{},y^{},z^{}`$) are three 2p orbitals on C(10). $`\varphi _1`$ and $`\varphi _2`$ point to H(2) and H(3), respectively. We take linear combinations of $`\varphi _1`$ and $`\varphi _2`$ as well as 1s orbitals $`\phi _1`$ and $`\phi _2`$ on H(2) and H(3) and define $`\overline{\varphi }_\pm =(\varphi _1\pm \varphi _2)/\sqrt{2}`$ and $`\overline{\phi }_\pm =(\phi _1\pm \phi _2)/\sqrt{2}`$. Note that $`\overline{\varphi }_{}=\varphi _z`$, i.e. a $`\pi `$ orbital on C(10). By symmetry, $`\overline{\varphi }_{}`$ and $`\overline{\phi }_{}`$ hybridize with the $`\pi `$ orbitals of the host $`\pi `$ system of the graphene sheet, but not with $`\sigma `$ orbitals in the honeycomb lattice. Therefore, we must utilize $`\overline{\varphi }_{}`$ and $`\overline{\phi }_{}`$ as well as the $`\pi `$ orbitals on C(i) ($`i=1,\mathrm{}9`$) to analyze the $`\pi `$ network in the magnetic nanographite.

If we adopt the above representation, we obtain an effective model describing the ribbon. The model consists of 11 local orbitals in a unit cell. Here we ignore overlap integrals between orbitals for simplicity. Introducing the operator representation $`c_{i,\sigma }`$ for a $`\pi `$ electron on a carbon atom and $`d_{l,\sigma }`$ for an electron in $`\overline{\phi }_{}`$ in the $`l`$-th unit cell, we obtain an effective Hamiltonian.

$`H`$ $`=`$ $`{\displaystyle \underset{i,j}{}}{\displaystyle \underset{\sigma }{}}t_{i,j}(c_{i,\sigma }^{}c_{j,\sigma }+H.c.)+{\displaystyle \underset{i}{}}Un_{i,}n_{i,}`$ (1)
$`{\displaystyle \underset{i,l}{}}{\displaystyle \underset{\sigma }{}}t_{i,l}^{}(c_{i,\sigma }^{}d_{l,\sigma }+H.c.)+{\displaystyle \underset{l}{}}U^{}m_{l,}m_{l,}`$
$`+\epsilon {\displaystyle \underset{l}{}}{\displaystyle \underset{\sigma }{}}m_{l,\sigma }`$
Here, an index $`i`$ specifying a carbon atom runs over all carbon sites. Two kinds of number operators are defined as $`n_{i,\sigma }c_{i,\sigma }^{}c_{i,\sigma }`$ and $`m_{l,\sigma }d_{l,\sigma }^{}d_{l,\sigma }`$. Bond connections given by non-zero $`t_{i,j}`$ and $`t_{i,l}^{}`$ are the same as those in a graphene ribbon with a zigzag edge and a bearded edge.Kusakabe and Takagi (2002) We set the origin of the energy at the orbital energy of the 2p orbital $`\epsilon _{2p}`$ on carbon. $`\epsilon _{1s}`$ denotes the energy of a 1s electron on a hydrogen atom and $`\epsilon `$ is given by $`\epsilon =\epsilon _{1s}\epsilon _{2p}`$. Since $`\epsilon <0`$, a band mainly composed of $`\overline{\phi }_{}`$ is separated in energy from other $`\pi `$ bands. This property is also seen in the LSDA band structure, where the 17th band on the $`K`$-$`Y`$ line in Fig. 2 is the corresponding band.

Consider a periodic boundary condition for a finite system with $`N_c`$ unit cells. If $`\epsilon =0`$ and if $`U^{}=U`$, Lieb’s theorem is applicable and the ground state becomes a ferrimagnetic state with a total magnetization $`S_{\mathrm{tot}}=|N_AN_B|/2`$. Here the difference in sublattice sites $`|N_AN_B|`$ equals $`N_c`$. This magnetic ground state is thought to be stable against perturbation like $`\epsilon <0`$, since 1) there is a finite gap between the flat band and other $`\pi `$ bands both in the tight-binding description and in the LSDA result in Fig. 2, 2) we have confirmed that a small difference of $`\epsilon _{1s}`$ and $`\epsilon _{2p}`$ does not break the flatness of the center band in the tight-binding model. Thus the magnetism found in an LSDA calculation can be understood as the appearance of ferrimagnetism in a flat-band Hubbard model.

The formation energy of a di-hydrogenated edge has been evaluated by comparing the total energy within LSDA. We denote $`E_{H_2}`$, $`E_{G1}`$ and $`E_{G2}`$ as the energy of a hydrogen molecule, that of a graphene ribbon with mono-hydrogenated zigzag edges and that of a magnetic nanographite ribbon, respectively. The latter two are energy per a unit cell including $`2n`$ carbon atoms. Our calculation shows that $`E_{G2}(E_{G1}+E_{H_2}/2)0.3`$eV for $`n=5`$. Thus, the hydrogenation of nanographite with mono-hydrogenated zigzag edges is confirmed to be an endothermic reaction. Utilization of proper catalysts in catalytic reduction may be important in the synthesis of magnetic nanographite.

To see how our conclusion is affected by changing the width of the ribbon, we performed the LSDA calculation for ribbons with a width from $`n=2`$ to $`n=4`$. A ferrimagnetic structure was found even in these narrow ribbons. These ribbons do not show the Peierls distortion, which is similar to conclusions on the mono-hydrogenated zigzag ribbons.Kertesz and Hoffmann (1983); Fujita et al. (1997); Miyamoto et al. (1999)

We have shown that a spin-polarized flat band appears in the LSDA band structure of a graphene ribbon. The origin of the magnetism is explained as a realization of the flat-band ferromagnetism. An orbital $`\overline{\phi }_{}`$ on two hydrogen atoms H(2) and H(3) is an anti-bonding orbital and has symmetry $`p_z`$. Thus, hydrogenation of a carbon atom is identified as the addition of a $`\pi `$ orbital at a zigzag edge. The structure may be regarded as a realization of the bearded edge. We can expect magnetism for any hydrogenated ribbon with $`|N_AN_B|>0`$, even if di-hydrogenation of the zigzag edge is not perfect. The same effect is also expected with fluorination.Maruyama and Kusakabe (2002) In this report we have considered a ribbon with a flat graphene structure, but the method is also applicable to nanotubes with zigzag edges. Thus it appears that, a magnetic nanotube may be designed.Kusakabe and Maruyama (2002)

###### Acknowledgements.

One of the authors K.K. is grateful for fruitful discussions with Professor T. Enoki and Dr Takai. This work has been supported by a Grant-in-Aid from the Ministry of Education, Culture, Sports, Science and Technology of Japan. The calculation was partly performed at the computer facility of ISSP, University of Tokyo.


text:
# Characterizing Matchings as the Intersection of Matroids An earlier version appears as an extended abstract in the Proceedings of COMB’01 [5].

## 1 Introduction

Many combinatorial optimization problems can be viewed as optimization problems over independence systems. Some of them are polynomially solvable, e.g., spanning trees in graphs, the branching problem in digraphs, or the matching problem. Others are known to be NP-complete, like the traveling salesman problem (TSP) or the stable set problem (cf. ). Among the problems with a polynomial-time algorithm, the matching problem is generally recognized as one of the “hardest”, and the famous blossom algorithm by Edmonds  is one of the highlights of combinatorial optimization.

Another seminal result on the optimization in independence systems was also given by Edmonds , who proved that the optimization problem over the intersection of two matroids is solvable in polynomial time. Algorithms for this problem were given by Edmonds , Frank , and Lawler . Unfortunately, this cannot be generalized to the case of three or more matroids: As the NP-complete TSP can be written as an optimization problem over the intersection of three matroids, it is highly unlikely that a polynomial-time algorithm exists.

In this paper, we consider a problem that combines aspects of both problems that were solved by Edmonds: How many matroids need to be intersected to characterize the matchings of a graph? This problem is somewhat related to work by Jenkyns  and Korte and Hausmann , who described approximation guarantees for the greedy algorithm; these guarantees depend on the rank quotient, which depends on the number of matroids needed for characterizing the independence system. Clearly, we are not primarily interested in these approximation guarantees for matching. However, we believe that the problem of describing an independence system as the intersection of few matroids is an interesting combinatorial problem in its own right.

The rest of this paper is organized as follows. After some technical preliminaries in Section 2, Section 3 gives a number of general structural results. In particular, we give a precise characterizations of graphs for which the set of matchings can be represented as the intersection of two matroids, and an Integer Programming formulation for the problem of minimizing the number of matroids that are necessary for representing the matchings of an input graph. In Section 4 we prove that $`K_n`$ needs at least $`\mathrm{\Omega }(\mathrm{log}\mathrm{log}n)`$ matroids, while Section 5 establishes an upper bound of $`O(\mathrm{log}n/\mathrm{log}\mathrm{log}n)`$ for the number of matroids needed for any graph with $`n`$ vertices. The final Section 6 describes the actual values of matroids that are necessary for graphs with up to 15 vertices.

## 2 Preliminaries

Let $`S`$ be a finite set and $``$ be a family of subsets of $`S`$. $``$ is an independence system on $`S`$ if $`\mathrm{}`$ and if $`J^{}J`$ and $`J`$ then $`J^{}`$. The subsets of $`S`$ belonging to $``$ are called independent, otherwise dependent. The minimal dependent subsets of $`S`$ are the circuits of $``$. The circuit system $`𝒞`$ of $``$ is the set of circuits of $``$ and $`=\{JS:CJ\text{ for all }C𝒞\}`$. A maximal independent subset of a set $`AS`$ is a basis of $`A`$. An independence system $``$ on $`S`$ is a matroid if for every subset $`AS`$ all its bases have the same cardinality. For further background, see Oxley  and Welsh . Here we just state another useful fact.

###### Proposition 1

The circuit system $`𝒞`$ of an independence system $``$ is the circuit system of a matroid if and only if for all $`C_1C_2𝒞`$ with $`C_1C_2\mathrm{}`$ and for all $`cC_1C_2`$ there exists $`C𝒞`$ such that $`CC_1C_2\{c\}`$.

Any independence system is the intersection of finitely many matroids: Let $`𝒞`$ be the set of circuits of $``$. For $`C𝒞`$, let $`_C`$ be the matroid on $`S`$ with circuit system $`\{C\}`$, i.e., $`_C=\{JS:CJ\}`$. Then $`=\{_C:C𝒞\}`$. This, however, may not be the most economical way to describe $``$, because we may be able to cover several circuits by the same matroid. In the following, we write $`\mu ()`$ for the minimum number of matroids necessary for this task. Throughout the rest of this paper, $``$ is the set of matchings of a graph, which we describe in the following.

Consider a finite graph $`G=(V,E)`$. A matching in $`G`$ is a set of edges that are pairwise disjoint. The set $`M(G)`$ of matchings in $`G`$ forms an independence system on $`E`$. For simplicity, we write $`\mu (G)`$ for $`\mu (M(G))`$, i.e.,

$$\mu (G)=\mathrm{min}\{m:M(G)\text{ is the intersection of }m\text{ matroids}\}.$$

Furthermore, $`\mu (n)`$ is used for the maximum $`\mu (G)`$ on graphs with $`|V|n`$, i.e.

$$\mu (n)=\mathrm{max}\{\mu (G):|V|n\}.$$

It is easy to see that the circuits of $`M(G)`$ are the sets that consist of two intersecting edges. (The reader should keep in mind that throughout the rest of this paper, the term circuit refers to such a pair of edges.) We call a circuit an $`i`$-circuit if its edges intersect in vertex $`i`$. We denote the circuit $`\{ij,ik\}`$ with the two edges $`ij`$ and $`ik`$ by $`i^{jk}`$.

## 3 General Characterizations

The following easy lemma implies that $`\mu (n)=\mu (K_n)`$.

###### Lemma 2

Let $`G^{}=(V^{},E^{})`$ be a subgraph of $`G=(V,E)`$. Then $`\mu (G^{})\mu (G)`$.

Proof: Let $`M(G)`$ be the intersection of matroids $`_1,\mathrm{},_m`$ on $`E`$. For $`a=1,\mathrm{},m`$, let $`_a^{}:=\{J:JE^{},J_a\}`$ be the restriction of $`_a`$ to $`E^{}`$. Then $`M(G^{})`$ is the intersection of the matroids $`_1^{},\mathrm{},_m^{}`$ on $`E^{}`$. $`\mathrm{}`$

As a consequence of this lemma, the number of matroids needed to represent the matchings in the complete graph $`K_n`$ on $`n`$ vertices is a natural upper bound for the number of matroids needed to represent the matching independence system of any graph on at most $`n`$ vertices, i.e., $`\mu (n)=\mu (K_n)`$.

### 3.1 Matchings as the Intersection of Two Matroids

We present a complete characterization of the graphs for which the set of matchings is the intersection of at most two matroids, by generalizing the concept of bipartite graphs.

For a bipartite graph $`G=(V_1\times V_2,E)`$, the set of matchings $`M(G)`$ is the intersection of two (partition) matroids. More generally, we get the following.

###### Theorem 3

Let $`G=(V,E)`$ be an $`m`$-partite graph. Then $`M(G)`$ is the intersection of at most $`m`$ matroids on $`E`$.

Proof: Let $`V_1\times \mathrm{}\times V_m`$ be an $`m`$-partition of $`G`$. Use the partition matroids

$$_i:=\{JE:|J\delta (v)|1\text{ for all }vV_i\},i=1,\mathrm{},m.\mathrm{}$$

As we will see in Section 5, this upper bound has quite a bit of slack for large $`\mu (G)`$. Moreover, there are non-bipartite graphs $`G`$ with $`\mu (G)=2`$, as can be seen from the following characterization.

###### Theorem 4

The set of matchings $`M(G)`$ of a graph $`G=(V,E)`$ is the intersection of two matroids if and only if $`G`$ contains no odd cycle of cardinality $`5`$ and each triangle of $`G`$ has at most one vertex with degree $`>2`$.

Proof: a) Let $`G`$ be a graph that contains no odd cycle of cardinality $`5`$ and all triangles of $`G`$ have at most one vertex with degree $`>2`$. We call a triangle isolated if all its vertices have degree $`2`$. Let $`G^{}`$ be the graph that we obtain from $`G`$ by contracting all isolated triangles and by deleting from any other triangle the edge that connects the two vertices of degree $`2`$. Then $`G^{}`$ is a bipartite graph with bipartition $`V_1^{}\times V_2^{}`$. For $`a=1,2`$, let $`V_a`$ consist of all vertices $`vV`$ that correspond to vertices of $`V_a^{}`$ in $`G^{}`$. Let $`𝒞_a`$ consist of all circuits $`i^{jk}`$ of $`M(G)`$ such that $`iV_a`$ or $`\{i,j,k\}`$ is a triangle of $`G`$ and $`j,kV_a`$. Then $`𝒞_a`$ is the circuit system of the matroid $`_a:=\{JECJ\text{ for all }C𝒞_a\}`$ and $`M(G)`$ is the intersection of $`_1`$ and $`_2`$.

b) Let $`M(G)`$ be the intersection of two matroids $`_1`$ and $`_2`$ on $`E`$. Suppose $`G`$ contains an odd cycle $`v_1,v_2,\mathrm{},v_{2k+1}`$, $`k2`$. Then $`\{v_1v_2,v_2v_3\}`$, $`\{v_2v_3,v_3v_4\}`$, $`\mathrm{},`$ $`\{v_{2k+1}v_1,v_1v_2\}`$ are circuits of $`M(G)`$ and hence circuits in at least one of the matroids. W.l.o.g. we obtain that $`\{v_1v_2,v_2v_3\}`$ and $`\{v_2v_3,v_3v_4\}`$ are circuits of $`_1`$, in contradiction to $`\{v_1v_2,v_3v_4\}`$ being a matching, see Proposition 1. Suppose $`G`$ contains a triangle $`\{u,v,w\}`$ with two additional edges $`uz`$ and $`vz^{}`$ (possibly $`z=z^{}`$). There are three $`u`$-circuits $`\{uv,uw\}`$, $`\{uv,uz\}`$, and $`\{uw,uz\}`$. W.l.o.g. all three are circuits of $`_1`$. Because $`\{vw,uz\}`$ is a matching it follows that $`\{uw,vw\}`$, $`\{uv,vw\}`$ are circuits of $`_2`$ and hence also $`\{uv,uw\}`$. But because $`\{uw,vz^{}\}`$ is a matching, $`\{uv,vz^{}\}`$ cannot be a circuit in any of the two matroids, a contradiction. Consequently, $`G`$ contains no odd cycle of cardinality $`5`$ and each triangle of $`G`$ has at most one vertex with degree $`>2`$. $`\mathrm{}`$

### 3.2 IP-Formulation

Next we describe a characterization of the problem whether the set of matchings in a graph $`G=(V,E)`$ on $`n`$ vertices can be represented as the intersection of at most $`m`$ matroids in terms of necessary and sufficient conditions. This characterization leads in a natural way to an IP-formulation of the introduced problem, which can be solved by standard IP-solvers, for at least not too large values of $`n`$ and $`m`$.

Suppose first that the set of matchings $`M(G)`$ of $`G`$ is the intersection of $`m`$ matroids $`_1,_2,\mathrm{},_m`$ on $`E`$. Any matching of $`G`$ must be independent in each of these matroids and any circuit of $`M(G)`$ must be dependent (and hence a circuit) in at least one of these matroids. For any matroid $`_a`$ and any circuit $`\{ij,ik\}`$ of $`M(G)`$ with $`j<k`$, we introduce a $`0/1`$-variable $`x_{ij,ik}^a`$ which is $`1`$ if the circuit $`\{ij,ik\}`$ is dependent (and hence a circuit) in $`_a`$ or $`0`$ otherwise, i.e.,

$$x_{ij,ik}^a=\{\begin{array}{cc}\hfill 1:& \{ij,ik\}\text{ is dependent in }_a,\hfill \\ \hfill 0:& \text{otherwise.}\hfill \end{array}$$

Cover condition. Because any circuit is dependent in at least one of the matroids, we obtain the following cover-inequalities

$$\underset{a=1}{\overset{m}{}}x_{ij,ik}^a1\text{for all }ij,ikE,j<k.$$
(1)
Claw condition. For any $`i,j,k,l`$ different, it is not possible that exactly two of the three circuits $`\{ij,ik\}`$, $`\{ij,il\}`$, and $`\{ik,il\}`$ of $`M(G)`$ are circuits in the same matroid $`_a`$, i.e., we have

$$x_{ij,ik}^a+x_{ij,il}^a+x_{ik,il}^a2\text{for all }ij,ik,ilE,j<k<l,\text{ for all }a.$$

This is modeled by the following claw-inequalities:

$$\begin{array}{cccccccccc}\hfill +& \hfill x_{ij,ik}^a& \hfill +& \hfill x_{ij,il}^a& \hfill & \hfill x_{ik,il}^a& & 1\hfill & & \text{for all }ij,ik,ilE,\hfill \\ \hfill +& \hfill x_{ij,ik}^a& \hfill & \hfill x_{ij,il}^a& \hfill +& \hfill x_{ik,il}^a& & 1\hfill & \}\hfill & j<k<l,\hfill \\ \hfill & \hfill x_{ij,ik}^a& \hfill +& \hfill x_{ij,il}^a& \hfill +& \hfill x_{ik,il}^a& & 1\hfill & & \text{for all }a\hfill \end{array}$$
(2)
Triangle condition. For any $`ij,ik,jkE`$ different, it is impossible that exactly two of the three circuits $`\{ij,ik\}`$, $`\{ji,jk\}`$, and $`\{ki,kj\}`$ of $`M(G)`$ are circuits in the same matroid $`_a`$, i.e., we have

$$x_{ij,ik}^a+x_{ji,jk}^a+x_{ki,kj}^a2\text{for all }ij,ik,jkE,i<j<k,\text{ for all }a.$$

We obtain the triangle-inequalities:

$$\begin{array}{cccccccccc}\hfill +& \hfill x_{ij,ik}^a& \hfill +& \hfill x_{ji,jk}^a& \hfill & \hfill x_{ki,kj}^a& & 1\hfill & & \text{for all }ij,ik,jkE,\hfill \\ \hfill +& \hfill x_{ij,ik}^a& \hfill & \hfill x_{ji,jk}^a& \hfill +& \hfill x_{ki,kj}^a& & 1\hfill & \}\hfill & i<j<k,\hfill \\ \hfill & \hfill x_{ij,ik}^a& \hfill +& \hfill x_{ji,jk}^a& \hfill +& \hfill x_{ki,kj}^a& & 1\hfill & & \text{for all }a\hfill \end{array}$$
(3)
Matching condition. For any $`i,j,k,l`$ different with $`ij,klE`$, $`\{ij,kl\}`$ is a matching in $`G`$. Hence, it is not possible that both circuits $`\{ij,ik\}`$ and $`\{ki,kl\}`$ of $`M(G)`$ are circuits in the same matroid $`_a`$. This leads us to the matching-inequalities:

$$\begin{array}{cccccc}\hfill x_{ij,ik}^a& \hfill +& \hfill x_{ki,kl}^a& & 1\hfill & \text{for all }ij,ik,klE,j<k,i<l,jl,\text{ for all }a\hfill \\ \hfill x_{ik,ij}^a& \hfill +& \hfill x_{ki,kl}^a& & 1\hfill & \text{for all }ij,ik,klE,k<j,i<l,jl,\text{ for all }a\hfill \\ \hfill x_{ik,ij}^a& \hfill +& \hfill x_{kl,ki}^a& & 1\hfill & \text{for all }ij,ik,klE,k<j,l<i,jl,\text{ for all }a\hfill \end{array}$$
(4)
###### Theorem 5

The set of matchings $`M(G)`$ of a graph $`G`$ is the intersection of at most $`m`$ matroids if and only if there exists $`x_{ij,ik}^a\{0,1\}`$ for all $`ij,ikE,j<k`$, for all $`a=1,\mathrm{},m`$ such that all the inequalities in (1), (2), (3), (4) are satisfied.

Proof: We have to show that any feasible solution of the given system leads to $`m`$ matroids such that $`M(G)`$ is their intersection. Let $`(x_{ij,ik}^a)_{i,j,k,a}`$ be such a feasible solution. For $`a=1,2,\mathrm{},m`$, define

$$𝒞_a:=\{\{ij,ik\}:ij,ikE,j<k,x_{ij,ik}^a=1\}.$$

Due to the claw-, triangle-, and matching-inequalities, $`𝒞_a`$ is the circuit system of a matroid. Its associated matroid is $`_a=\{JE:CJ\text{ for all }C𝒞_a\}.`$ We claim that $`M(G)`$ is the intersection of $`_1,_2,\mathrm{},_m`$.

Let $`JM(G)`$. Because any circuit of $`_a`$ is a circuit of $`M(G)`$, $`J`$ is an element of $`_1\mathrm{}_m`$. Now let $`J`$ be an element of this intersection. Suppose $`J`$ is not in $`M(G)`$. Then there is some circuit $`\{ij,ik\}`$ $`(j<k)`$ in $`M(G)`$ which is contained in $`J`$. Due to the cover-inequalities, $`\{ij,ik\}`$ is a circuit in at least one matroid $`_a`$, in contradiction to $`J`$ being $`_a`$-independent. $`\mathrm{}`$

For most IP-solvers it is more efficient to solve an optimization problem instead of solving a feasibility problem. We transform the feasibility problem into an optimization problem by introducing additional $`0/1`$-variables $`y_{ij,ik}`$ for any circuit $`\{ij,ik\}`$ $`(j<k`$) of $`M(G)`$. We replace the cover-inequalities (1) by the inequalities

$$\underset{a=1}{\overset{m}{}}x_{ij,ik}^ay_{ij,ik}0\text{for all }ij,ikE,j<k$$

and try to maximize the sum of the new $`y`$-variables, i.e., $`\mathrm{max}_{ij,ikE,j<k}y_{ij,ik}.`$ This means we want to cover as many circuits as possible. Consequently, the original feasibility problem has a feasible solution if and only if the new program has a feasible solution in which all $`y`$-variables are equal to $`1`$. Note that the $`0`$-vector is a feasible starting solution for this integer program.

Nevertheless, these problems are still hard to solve. The integer programs that we explore are quite large and grow very fast because the problems have $`𝒪(mn^3)`$ variables and $`𝒪(mn^4)`$ constraints. Therefore, current IP-solvers, e.g., CPLEX111CPLEX Linear Optimizer 6.0 (with Mixed Integer & Barrier Solvers); © ILOG Inc., Incline Village, NV, USA. or SIP222Solving Integer Programs 1.1 by Alexander Martin (TU Darmstadt, Germany), unpublished., are unable to handle them in reasonable time even for moderate values of $`n`$ and $`m`$ (e.g., $`G=K_n`$ with $`n=13`$, $`m=4`$).

## 4 Lower Bounds

In the following, we use the notation $`\nu (m)`$ to indicate the largest $`n`$ for which $`\mu (n)m`$, i.e.,

$$\nu (m)=sup\{n:\mu (n)m\}.$$

The following result shows that $`\nu (m)`$ is indeed finite and grows at most doubly exponentially.

###### Theorem 6

$`\nu (m)2^{2^{3m}1}1`$.

Proof: Let $`G=(V,E)`$ be the complete graph $`K_n`$ on $`n`$ vertices and $`\mu (n)m`$. We start by introducing some technical terms. For a vertex $`i`$, consider all directed edges $`ij,jV\{i\}`$. (The difference between $`ij`$ and $`ji`$ is only important for the following definition.) If an $`i`$-circuit involving edge $`ij`$ is covered by matroid $`_a`$, we say that $`ij`$ has color $`a`$. The set of colors of an edge defines its color type. The color class of any vertex $`i`$ is the set of color types of all the edges $`ij`$, $`jV\{i\}`$. Finally, a degenerate triangle consists of three different vertices $`i,j,k`$, such that all three circuits $`\{ij,ik\}`$, $`\{ji,jk\}`$, $`\{ki,kj\}`$ are covered by the same matroid, say, $`_a`$. For such a triangle, it is an easy consequence of the matching condition described in Section 3.2 that none of the other circuits involving the edges $`ij,ik,jk,ji,ki,kj`$ may be covered by $`_a`$; i.e., for $`l\{i,j,k\}`$, none of the circuits $`\{ij,il\}`$, $`\{ik,il\}`$, $`\{ji,jl\}`$, $`\{jk,jl\}`$, $`\{ki,kl\}`$, $`\{kj,kl\}`$ may be covered by $`_a`$ as well.

We start by eliminating covers with degenerate triangles. If there are any degenerate triangles in a circuit cover with $`m`$ matroids, we can construct a circuit cover with $`3m`$ matroids that is free of degenerate triangles: For each degenerate triangle covered by matroid $`_a`$, cover one circuit by matroid $`_a`$, the other two by the additional matroids $`_a^{}`$ and $`_{a^{\prime \prime }}`$. By the observation at the end of the preceding paragraph, this does not affect any other circuits already covered by $`_a`$, so all conditions described in Section 3.2 are still valid. Therefore, this yields indeed a feasible set of matroids.

Now consider the situation in the absence of degenerate triangles. As any (directed) edge $`ijE`$ is part of some circuit, and each circuit is covered by some matroid, there can be at most $`2^m1`$ different color types for $`m`$ different matroids. Moreover, there are at most $`2^{2^m1}1`$ different color classes of vertices. Furthermore, any $`i`$-circuit formed by a pair of edges $`ij`$, $`ik`$ with $`jk`$ must be covered by some matroid, so no two color types in any valid color class can be disjoint.

Assume that we have two vertices ($`i`$ and $`j`$) of the same color class. Then their connecting edge $`ij`$ is part of a circuit $`\{ij,ik\}`$ that is covered by some matroid $`_a`$; at the same time, there must be a circuit $`\{ji,jl\}`$ that is also covered by $`_a`$. If $`kl`$, we get a violated matching condition. If $`k=l`$, we use the fact that $`\{i,j,k\}`$ is not a degenerate triangle, and we conclude that we get a violated triangle condition.

Therefore, there can be at most $`2^{2^m1}1`$ vertices in the absence of degenerate triangles, and not more than $`2^{2^{3m}1}1`$ in general. $`\mathrm{}`$

Quite clearly, upper bounds for $`\nu (m)`$ correspond to lower bounds for $`\mu (n)`$. In particular, we get

###### Corollary 7

$`\mu (n)\mathrm{\Omega }(\mathrm{log}\mathrm{log}n)`$.

## 5 Upper Bounds

Using a recursive construction, we can show that $`m`$ matroids suffice to generate the matchings of any graph with $`O(\sqrt[3]{m!})=2^{O(m\mathrm{log}m)}`$ vertices. As above, this yields an upper bound for $`\mu (n)`$. More precisely, we show

###### Theorem 8

$$\nu (m)3\underset{i=0}{\overset{\frac{m}{3}2}{}}(m3i).$$

Proof: We proceed by induction. Clearly, the claim is true for $`m=1,2,3`$, as all three circuits of $`K_3`$ can be covered by the circuit system of just one matroid. Now suppose the claim was true for $`m3`$. Consider $`m`$ vertex sets $`V_1,\mathrm{},V_m`$, each consisting of $`\nu (m3)`$ vertices.

For proving the overall claim, it suffices to describe circuit systems $`𝒞_1,\mathrm{},𝒞_m`$ that satisfy the following conditions.

1. All circuits $`v^{uw}`$ with $`v,u,wV_k`$ are contained in some $`𝒞_i`$.
2. All circuits $`v^{uw}`$ with $`vV_k`$, $`u,wV_k`$ are contained in some $`𝒞_i`$.
3. All circuits $`v^{uw}`$ with $`v,uV_k`$, $`wV_k`$ are contained in some $`𝒞_i`$.
4. Each resulting $`𝒞_i`$ is the circuit system of a matroid.

In the following, indices are taken modulo $`m`$. By the induction hypothesis, the set of matchings on $`V_k`$ is the intersection of $`m3`$ matroids. Denote the corresponding circuit systems by $`𝒞_1^k,\mathrm{},𝒞_{m3}^k`$. For $`i=1,\mathrm{},m`$ define

$$𝒞_i^{}:=𝒞_1^{i+2}𝒞_2^{i+3}\mathrm{}𝒞_{m3}^{i2}=\underset{j=1}{\overset{m3}{}}𝒞_j^{i+1+j}.$$

In particular, $`𝒞_{ki1}^k𝒞_i^{}`$ is the set of all circuits within $`V_k`$ that are covered by $`C_i^{}`$. Then $`𝒞_i^{}`$ is a circuit system on $`E`$ and $`𝒞_1^{},\mathrm{},𝒞_m^{}`$ satisfy condition (1). The circuit systems $`𝒞_1,\mathrm{},𝒞_m`$ arise now by adding $`𝒞_i^{}`$ to $`𝒞_i`$ and for $`k=1,\mathrm{},m`$:

* Add $`\{v^{uw}:vV_k,u,wV_k\}`$ to $`𝒞_k`$.
Add $`\{v^{uw}:vV_k,u,wV_{k+1}\}`$ to $`𝒞_{k1}`$.
Add $`\{v^{uw}:vV_k,u,wV_kV_{k+1}\}`$ to $`𝒞_{k+1}`$.
* Now consider $`V_k=\{v_{(k1)\nu (m3)+1},\mathrm{},v_{k\nu (m3)}\}`$.
Add the following circuits to $`𝒞_k`$

$$\{v_i^{v_jw}:i<j,v^i,v^jV_k,wV_k\}\{v_i^{v_jv_l}:i<j,l,v^i,v^j,v^lV_k\}.$$

Add the following circuits to $`𝒞_{k1}`$

$$\{v_i^{v_jw}:i>j,v^i,v^jV_k,wV_{k+1}\}\{v_i^{v_jv_l}:i>j,l,v^i,v^j,v^lV_k\}.$$

Add the following circuits to $`𝒞_{k+1}`$

$$\{v_i^{v_jw}:i>j,v^i,v^jV_k,wV_kV_{k+1}\}\{v_i^{v_jv_l}:i>j,l,v^i,v^j,v^lV_k\}.$$

See Fig. 1 for an illustration. There, arrowheads point away from the central vertices of circuits.

The resulting circuit systems $`𝒞_1,\mathrm{},𝒞_m`$ satisfy conditions (1), (2), and (3). In order to see that each $`𝒞_i`$ is the circuit system of a matroid, we need to verify the claw-, triangle-, and matching-conditions described in Section 3.2.

Claw condition: We need to verify that for any two circuits $`v^{uw_1}`$, $`v^{uw_2}`$ that are both contained in some $`𝒞_i`$, $`v^{w_1w_2}`$ is also contained in $`𝒞_i`$.

Let $`vV_k`$. If $`i\{k1,k,k+1\}`$, then the involved circuits must be completely within $`V_k`$ and they are all covered by $`𝒞_{ki1}^k𝒞_i`$. Otherwise, $`i\{k1,k,k+1\}`$ and the property is easily verified.

Triangle and matching conditions: Let $`v^{uw_1}𝒞_i`$ for some $`i`$. We need to verify that if $`u^{vw_2}𝒞_i`$ for some $`w_2`$ then $`w_2=w_1`$ and $`w_1^{uv}𝒞_i`$.

Let $`vV_k`$. If $`i\{k1,k,k+1\}`$, then the involved circuits must be completely within $`V_k`$ and hence, being in $`𝒞_i`$ means being in $`𝒞_{ki1}^k`$. Because $`𝒞_{ki1}^k`$ is the circuit system of a matroid, the triangle and matching conditions are satisfied. In the following $`i\{k1,k,k+1\}`$. It suffices to show that no $`u^{vw_2}`$ is contained in $`𝒞_i`$. If $`uV_kV_{k+1}`$ then $`i=k`$ or $`i=k+1`$. On the other hand, none of the circuits $`u^{vw_2}`$ is in $`𝒞_k`$ or $`𝒞_{k+1}`$. If $`uV_{k+1}`$ it follows by our construction that $`i=k`$ or $`i=k1`$ while $`u^{vw_2}`$ is in $`𝒞_{k+2}`$ or $`𝒞_{k+1}`$. Finally, we consider $`uV_k`$. Let $`v=v_h`$ and $`u=v_j`$. If $`h<j`$ then $`i=k`$ while $`u^{vw_2}`$ is in $`𝒞_{k1}`$ or $`𝒞_{k+1}`$. If $`h>j`$ then $`i=k1`$ or $`i=k+1`$ while $`u^{vw_2}`$ is in $`𝒞_k`$.

Consequently, $`𝒞_1,\mathrm{},𝒞_m`$ are circuit systems of matroids, say $`_1,\mathrm{},_m`$, and all circuits of $`M(G)`$ are covered by some $`𝒞_i`$. Hence, $`M(G)`$ is the intersection of the matroids $`_1,\mathrm{},_m`$. Therefore, $`\nu (m)m\nu (m3)`$. With $`\mu (j)3`$ for $`j\{1,2,3\}`$ we obtain

$$\nu (m)3\underset{i=0}{\overset{\frac{m}{3}2}{}}(m3i).$$

$`\mathrm{}`$

Now the lower bound on $`\nu (m)`$ implies an upper bound on $`\mu (n)`$:

###### Corollary 9

$`\mu (n)O(\mathrm{log}n/\mathrm{log}\mathrm{log}n)`$.

Proof: For $`ns=2^{cm\mathrm{log}m}`$, i.e., $`m\mathrm{log}m=\frac{\mathrm{log}s}{c}`$, we get $`\mathrm{log}m+\mathrm{log}\mathrm{log}m=\mathrm{log}(m\mathrm{log}m)=\mathrm{log}\mathrm{log}s\mathrm{log}c`$. This implies $`2\mathrm{log}m\mathrm{log}\mathrm{log}s`$ for sufficiently large $`m`$. Therefore, $`\frac{2\mathrm{log}n}{c\mathrm{log}\mathrm{log}n}\frac{2\mathrm{log}s}{c\mathrm{log}\mathrm{log}s}m`$. $`\mathrm{}`$

## 6 Tight Bounds for $`\mu (n)`$

Lawler mentioned in  that the nonbipartite matching problem can be formulated as an intersection problem involving two partition matroids, but with additional constraints in the form of symmetry conditions. Nevertheless, we can give an elementary proof of the following.

###### Theorem 10

$`\mu (n)=4`$ for $`n=5,\mathrm{},12`$.

Proof: From Theorem 8 we obtain $`\nu (4)12`$, hence, $`\mu (n)4`$ for $`n12`$.

We complete the proof by showing that $`\mu (5)4`$. Let $`G`$ be the complete graph $`K_5`$ with vertex set $`\{1,2,3,4,5\}`$ and $`M(G)`$ the set of matchings of $`G`$. Suppose $`M(G)`$ is the intersection of three matroids $`_1,_2`$, and $`_3`$ on $`E`$.

Consider the circuits that correspond to one vertex with incident edges $`a,b,c,d`$. These are $`\{a,b\}`$, $`\{a,c\}`$, $`\{a,d\}`$, $`\{b,c\}`$, $`\{b,d\}`$, $`\{c,d\}`$.

Suppose exactly three of them are $`_1`$-circuits, w.l.o.g., $`\{a,b\},\{a,c\},\{b,c\}`$. Without loss of generality, $`\{a,d\}`$ and $`\{b,d\}`$ and hence $`\{a,b\}`$ are $`_2`$-circuits. There exist edges $`e`$ and $`f`$ such that $`\{a,b,e\}`$ and $`\{b,d,f\}`$ are triangles:

Because $`\{c,e\}`$ is a matching $`\{a,e\}`$ is no $`_1`$-circuit and because $`\{d,e\}`$ is a matching $`\{a,e\}`$ is no $`_2`$-circuit, hence, $`\{a,e\}`$ is an $`_3`$-circuit, Similarly we obtain $`\{b,e\}`$ is an $`_3`$-circuit. Consequently, $`\{a,b\}`$ is an $`_1`$-, an $`_2`$-, and an $`_3`$-circuit. Because $`\{a,f\}`$ is a matching, there is no possibility for $`\{b,f\}`$ to be a circuit in one of the three matroids, a contradiction.

Hence, it is not possible that any matroid has exactly three of the six circuits that correspond to one vertex as circuits. If a matroid has at least four of the six circuits that correspond to one vertex as circuits then all six circuits are its circuits. Therefore, all six circuits are circuits in the same matroid or each of the three matroids has exactly two of the six circuits as circuits, these must be disjoint. Consequently, there are $`i_1,i_2,i_3,i_4,i_5\{1,2,3\}`$ such that $`\{12,15\}`$ and $`\{13,14\}`$ are $`_{i_1}`$-circuits, $`\{12,23\}`$ and $`\{24,25\}`$ are $`_{i_2}`$-circuits, $`\{23,34\}`$ and $`\{13,35\}`$ are $`_{i_3}`$-circuits, $`\{34,45\}`$ and $`\{14,24\}`$ are $`_{i_4}`$-circuits, and $`\{45,15\}`$ and $`\{25,35\}`$ are $`_{i_5}`$-circuits. Up to symmetry, we obtain $`i_1=i_2`$, i.e., $`\{12,15\}`$, $`\{13,14\}`$, $`\{12,23\}`$, and $`\{24,25\}`$ are $`_{i_1}`$-circuits, in contradiction to $`\{15,23\}`$ being a matching. $`\mathrm{}`$

We can also give a positive result concerning matching and the intersection of three matroids:

###### Theorem 11

Let $`G=(V,E)`$ be a $`4`$-partite graph. Then the set of matchings $`M(G)`$ of $`G`$ is the intersection of at most three matroids on $`E`$.

Proof: Let $`V_1\times V_2\times V_3\times V_4`$ be a $`4`$-partition of $`G`$. For $`a=1,2,3`$, let $`𝒞_a`$ consist of all $`V_a`$-circuits and of all $`V_4`$-circuits $`i^{jk}`$ with $`j,kV_a`$ ($`iV_4`$). Then $`𝒞_a`$ is the circuit system of a matroid. Its associated matroid is $`_a=\{JE:CJ\text{ for all }C𝒞_a\}`$. It is easy to see that $`M(G)`$ is the intersection of the matroids $`_1,_2,_3`$ on $`E`$. $`\mathrm{}`$

This implies that the set of matchings of any subgraph of $`K_5`$ is the intersection of at most three matroids, i.e., $`K_5`$ is the smallest graph for which the set of matchings is not the intersection of three matroids.

Theorem 8 implies that $`\nu (5)15`$, hence, $`\mu (n)5`$ for $`n=13,14,15`$. Using refined versions of the techniques for the lower bound described in Section 4, we can show the following:

###### Theorem 12

$`\mu (n)=5`$ for $`n=13,14,15`$.

The proof proceeds by showing that for $`m=4`$, there are at most 12 “basic” color classes, i.e., color classes that cannot be simplified by deleting some of the circuits from some of the matroids. This implies the claim in the absence of degenerate triangles, as there cannot be any two vertices from the same basic color class. Furthermore, any pair of vertices from the same basic color class (which forces a degenerate triangle) eliminates another basic color class; again, the claim follows.

As full details are rather tedious and probably not of sufficient interest to the reader, they are omitted.