Invariant d'Hermite des jacobiennes de graphes pond�r�s
A tout graphe pond�r� de premier nombre de Betti $b$ est naturellement associ� un r�seau de dimension $b$, d�fini de mani�re analogue que la jacobienne pour une surface de Riemann. Cette classe de r�seaux g�n�r�e par des graphes est particuli�rement int�ressante. Nous d�montrons ici une majoration de l'invariant d'Hermite d'un tel r�seau en fonction de $b$ dont l'ordre de grandeur est $\ln b$. Cet ordre de grandeur est optimal : il est r�alis� par l'invariant d'Hermite de la jacobienne d'un graphe systoliquement �conomique.
reseaugraphe.tex
\documentclass[french,10pt]{article} 
\usepackage[latin1]{inputenc}
\usepackage{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{babel}
\usepackage[all]{xy}
\newtheorem{lemme}{Lemme}
\newtheorem{theorem}{Th\'eor\`eme} 
\newtheorem{definition}{D\'efinition} 
\newtheorem{corollary}{Corollaire} 
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question} 
\newtheorem{conjecture}{Conjecture} 
\newtheorem{demonstration}{D�monstration} 




\def\R{{\mathbb R}} 
\def\Z{{\mathbb Z}} 
\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}} 
\def\K{{\mathbb K}}
\def\T{{\mathbb T}}

\def\ga{{\gamma}} 
\def\del{{\delta}} 
\def\si{{\sigma}} 
\def\Si{{\Sigma}} 
\def\t{{\tau}} 

\def\E{{\cal E}} 
\def\G{{\cal G}} 
\def\A{{\cal A}} 
\def\F{{\cal F}} 
\def\C{{\cal C}} 

\def\V{\text{Vol}}
\def\s{\text{sys}}
\def\ls{\text{lsys}}
\def\mms{\text{mm}}
\def\mmz{\text{mm}_2}
\def\D{\text{Diam}}
\def\Ls{\text{Lsys}}
\def\Ai{\text{Aire}}
\def\l{\text{long}} 
\def\inj{\text{Inj}}
\def\ss{\text{sys}_0}


\def\g{{\tilde{g}}} 
\def\h{{\widehat{h}}} 
\def\v{{\nu}} 
\def\B{{\cal B}_{st}} 
\def\T{{\mathbb T}} 
\def\J{{\cal J}}  



 








\begin{document}


\title{Invariant d'Hermite des jacobiennes de graphes pond�r�s}


\author{Florent BALACHEFF\footnote{UMR 5149, Institut de Math\'ematiques et de Mod�lisation
de  Montpellier, Universit\'e Montpellier II  Case Courrier 051 - Place Eug\`ene Bataillon 34095
 Montpellier CEDEX 5, France e-mail: balachef@math.univ-montp2.fr}} 

\date{}

\maketitle



\bigskip

\begin{abstract}

A tout graphe pond�r� de premier nombre de Betti $b$ est naturellement associ� un r�seau de dimension $b$, d�fini de mani�re analogue que la jacobienne pour une surface de Riemann. Cette classe de r�seaux g�n�r�e par des graphes est particuli�rement int�ressante. Nous d�montrons ici une majoration de l'invariant d'Hermite d'un tel r�seau en fonction de $b$ dont l'ordre de grandeur est $\ln b$. Cet ordre de grandeur est optimal : il est r�alis� par l'invariant d'Hermite de la jacobienne d'un graphe systoliquement �conomique.
\end{abstract}

\bigskip



\noindent {\it Mathematics Subject Classification (2000) :} 05C35, 05C38, 11H31.

\noindent {\it Mots clefs :} Constante systolique, complexit�, graphe, invariant d'Hermite, jacobienne, systole.
\bigskip


\section*{Introduction}


Soit $n$ un entier non nul. L'�tude de la densit� des r�seaux d'un espace euclidien $(\R^n,<.,.>)$ est un sujet classique et prend la forme suivante :  �tant donn� un r�seau $\Lambda \subset \R^n$, nous d�finissons le d�terminant de $\Lambda$, not� $\det(\Lambda)$, comme le carr� du volume euclidien du domaine fondamental du r�seau et sa norme minimale par la formule
$$
||\Lambda||= \min \{<\lambda,\lambda> \mid \lambda \in \Lambda \setminus \{0\}\}.
$$
 L'invariant d'Hermite du r�seau est la quantit�
$$
\mu(\Lambda)=\frac{||\Lambda||}{\sqrt[n]{\det(\Lambda)}}
$$
et code la densit� du r�seau. La densit� maximale en dimension $n$ correspond � la {\it constante d�Hermite} :
\begin{equation}  \label{herm}
\gamma_n=\sup\{ \mu(\Lambda) \mid \Lambda \text{ r�seau de } \R^n\}. 
\end{equation}
Cette quantit� est bien d�finie et v�rifie l'encadrement suivant (voir \cite{conslo}) :
\begin{equation} \label{herm2}
\frac{n}{2\pi e} \lesssim \gamma_n \lesssim \frac{1.744 n}{2\pi e}.
\end{equation}

Dans la d�finition (\ref{herm}), on peut consid�rer la borne sup�rieure non plus sur tous les r�seaux mais sur un sous-ensemble de r�seaux de $\R^n$. P. Buser et P. Sarnak ont �tudi� dans \cite{busesarn94} la borne sup�rieure des invariants d'Hermite des r�seaux symplectiques et ont montr� qu'elle v�rifiait l'in�galit� inf�rieure dans la formule (\ref{herm2}). Ils ont �galement montr� le r�sultat suivant : la borne sup�rieure des invariants d'Hermite sur l'ensemble des r�seaux form� des jacobiennes de surfaces de Riemann de genre $g$, que l'on notera $\eta_{2g}$, v�rifie 
\begin{equation} \label{herm3}
c \ln g \lesssim \eta_{2g} \lesssim \frac{3}{\pi} \ln (4g+3),
\end{equation}
o� $c$ est une constante positive.

\medskip

Le but de cet article est de prouver un r�sultat analogue pour la jacobienne des graphes pond�r�s. Rappelons tout d'abord quelques d�finitions. Un {\it graphe} $\Gamma=(V,E)$ est un complexe simplicial de dimension 1. C'est la donn\'ee  d'une paire d'ensembles $(V,E)$, o\`u $V$ d\'esigne les sommets et $E$ les ar\^etes. La {\it valence} d'un sommet est le nombre d'ar�tes incidentes � ce sommet et un graphe sera dit {\it $k$-r�gulier}, pour $k\in \N^\ast$, si la valence de chacun de ses sommets est constante �gale � $k$. 
Dans ce qui suit, les graphes seront suppos�s  connexes, finis et leurs sommets de valence au moins $2$.  Un {\it graphe pond\'er\'e} est une paire $(\Gamma,w)$ o\`u $\Gamma=(V,E)$ est un graphe et $w$ est une {\it fonction poids} sur les ar\^etes $w:E \rightarrow \mathbb R_+$. Nous dirons d'un graphe pond�r� $(\Gamma,w)$ qu'il est {\it combinatoire} si sa fonction poids est constante �gale � $1$, et nous le noterons simplement $\Gamma$. Le type d'homotopie d'un graphe donn� $\Gamma=(V,E)$ est caract�ris� par le nombre $b_1(\Gamma)$ de cycles ind�pendants, appel� {\it premier nombre de Betti} ou {\it nombre cyclomatique}. On a la formule $b_1(\Gamma)=|E|-|V|+1$ o� $|X|$ d�signe le cardinal d'un ensemble fini $X$. Notons qu'� premier nombre de Betti fix�, les graphes consid�r�s sont en nombre fini � hom�omorphisme pr�s.

Etant donn� un graphe pond�r� $(\Gamma,w)$ de premier nombre de Betti $b\geq 1$, nous choisissons pour chaque ar�te une orientation arbitraire et nous noterons ${\mathbb E}=\{e_i\}_{i=1}^k$ l'ensemble de ces ar�tes orient�es. Soit 
$$
{\cal{C}}(\Gamma,\R) =\{ \sum_{i=1}^k a_i.e_i \mid  a_i \in \R \text{ pour } i=1, \ldots, k\}
$$
l'espace vectoriel engendr� par les ar�tes orient�es. Cet espace co\"incide avec l'espace des cha�nes simpliciales du complexe simplicial $\Gamma$. Il est muni du produit scalaire naturel $<e_i,e_j>_w=w(e_i)\delta_{ij}$ pour $1\leq i \leq j\leq k$, o� $\delta_{ij}$ d�signe le symbole de Kronecker (voir \cite{bacharnag97}, p. 191). L'homologie de $\Gamma$ de dimension $1$ � coefficients r�els $H_1(\Gamma,\R)$ est plong�e dans ${\cal{C}}(\Gamma,\R)$ comme un sous-espace vectoriel de dimension $b$ et on note encore $<.,.>_w$ la restriction du produit scalaire � ce sous-espace. L'homologie de $\Gamma$ de dimension $1$ � coefficients entiers $H_1(\Gamma,\Z)$, en l'absence de torsion dans ce cadre unidimensionnel, constitue un r�seau du sous-espace 
$H_1(\Gamma,\R)$ (comparer avec \cite{bacharnag97}). 

On note $\Lambda(\Gamma,w)= H_1(\Gamma,\Z)\subset (H_1(\Gamma,\R),<.,.>_w)$ le r�seau de dimension $b$ ainsi d�fini et on l'appelle {\it jacobienne} du graphe pond�r� $(\Gamma,w)$ : il est clair que l'invariant d'Hermite de ce r�seau ne d�pend pas des orientations d'ar�tes initialement choisies. Posons
$$
\rho_b=\sup \{ \mu(\Lambda(\Gamma,w)) \mid (\Gamma,w) \text{ graphe pond�r� de premier nombre de Betti } b \}.
$$

Notre r�sultat principal s'�nonce alors de la mani�re suivante.
\medskip

\noindent {\bf Th�or�me} {\it Pour $b$ suffisamment grand,  
\begin{equation} \label{theo1}
\frac{1}{6e}\log_2 b \lesssim \rho_b \lesssim 4\log_2 (\frac{8}{3}b),
\end{equation}
o� $\log_2$ d�signe le logarithme en base $2$.
}

\medskip

Nous pouvons, sous certaines restrictions, am�liorer ces deux in�galit�s.

\noindent 1) Pour une infinit� de valeurs $\{b_m\}_m$, il existe un graphe combinatoire \linebreak $3$-r�guliers $G_m$ de premier nombre de Betti $b_m$ (construit dans \cite{marg88}) pour lequel (voir in�galit� (\ref{amelio2})) 
$$
\mu(\Lambda(G_m))\gtrsim \frac{4}{9e} \log_2 b_m,
$$



\noindent 2) Tout graphe combinatoire $\Gamma$, dont la valence en chaque sommet est au moins $3$, v�rifie (voir in�galit� (\ref{amelio1}))
$$
\mu(\Lambda(\Gamma)) \lesssim 2\log_2 b.
$$

\bigskip

La suite de cet article est consacr� aux d�monstrations de ces r�sultats. Nous allons montrer que l'�tude de l'invariant d'Hermite de la jacobienne d'un graphe pond�r� est �quivalente � l'�tude du probl�me combinatoire suivant : �tant donn� un graphe, borner la complexit� de ce graphe par sa systole (voir la section $1$ pour les d�finitions de ces quantit�s). Dans la premi�re partie de ce papier, nous donnons la d�monstration de l'in�galit� sup�rieure dans la formule (\ref{theo1}). Dans la seconde partie, nous majorons pour tout graphe sa complexit� par son volume unidimensionnel, et obtenons ainsi  � l'aide de graphes systoliquement �conomiques - graphes dont le rapport volume sur systole est suffisamment petit - l'estim�e inf�rieure annonc�e pour $\rho_b$. Nous d�montrons pour finir les am�liorations 1) et 2).

\bigskip

\section{Complexit� et systole d'un graphe} 



Nous allons montrer la proposition suivante, qui d�montrera la majoration de $\rho_b$ annonc�e dans le th�or�me par un calcul d'�quivalent �l�mentaire.

\begin{proposition}
Pour tout graphe pond�r� $(\Gamma,w)$ de premier nombre de Betti $b\geq 2$,
\begin{equation} \label{sup}
\mu(\Lambda(\Gamma,w))\leq 4 \left (\prod_{k=2}^b\log_2 (\frac{8}{3} k)\right )^{1/b}.
\end{equation}
\end{proposition}
 


\medskip


\noindent {\bf D�monstration.} Commen\c cons par r�duire le probl�me. On peut construire facilement un graphe $3$-r�gulier $\Gamma'=(V',E')$  et une fonction poids $w'$ sur $\Gamma'$ tels que $(\Gamma,w)$ soit obtenu � partir de $(\Gamma',w')$ en contractant les ar�tes de poids nul en un point. Notons que $\mu(\Lambda(\Gamma,w))=\mu(\Lambda(\Gamma',w'))$. Comme l'application 
\begin{eqnarray} 
\nonumber  \mu_{\Gamma'} : \R^{|E'|} & \rightarrow &  \R_+ \\
\nonumber w & \rightarrow & \mu(\Lambda(\Gamma',w))
\end{eqnarray}
est continue et invariante par composition avec les dilatations, on en d�duit que pour tout $\epsilon>0$, il existe une fonction poids $w_\epsilon$ sur $\Gamma'$ telle que :


\noindent  - Pour toute ar�te $e \in E', w_\epsilon(e) \in \N$,


\noindent  - $| \mu(\Lambda(\Gamma,w))-\mu(\Lambda(\Gamma',w_\epsilon))|< \epsilon$.

Il suffit donc de d�montrer le r�sultat annonc� pour un graphe combinatoire ($w=1$) dont les sommets sont de valence $2$ ou $3$. 

\medskip

Etant donn� un graphe combinatoire $\Gamma$, nous pouvons exprimer l'invariant d'Hermite de sa jacobienne en fonction des quantit�s suivantes :

\noindent - La {\it systole}, qui dans le cas d'un graphe pond�r� $(\Gamma,w)$ est d�finie comme la plus petite longueur d'un circuit simple de $\Gamma$ et est not�e $\s(\Gamma,w)$. Dans le cas d'un graphe $\Gamma$ combinatoire, nous noterons simplement $\s(\Gamma)$ cette quantit�. 

\noindent - La {\it complexit�}, qui est d�finie comme le nombre d'arbres maximaux du graphe $\Gamma$ (voir \cite{biggs}) et est not�e $\kappa(\Gamma)$. 

D'apr�s \cite{bacharnag97}, �tant donn� un graphe combinatoire $\Gamma$,
\begin{center}
$||\Lambda(\Gamma)||=\s(\Gamma)$ et $\det(\Lambda(\Gamma))=\kappa(\Gamma)$.
\end{center}
\noindent On en d�duit l'�galit�
$$
\mu(\Lambda(\Gamma))=\frac{\s(\Gamma)}{\sqrt[b]{\kappa(\Gamma)}}.
$$

\bigskip


Supposons pour la suite de cette d�monstration que $\Gamma$ est un graphe combinatoire dont les sommets sont de valence $2$ ou $3$. Notre majoration revient donc � estimer inf�rieurement la complexit� d'un tel graphe par sa systole. Nous obtenons le r�sultat suivant, qui implique l'estim�e (\ref{sup}) :
\begin{lemme}
\begin{equation} \label{estsup}
\kappa(\Gamma)\geq \frac{\s(\Gamma)^b}{4^b \prod_{k=2}^b \log_2 (\frac{8}{3} k)}. 
\end{equation}
\end{lemme}


\medskip




\noindent {\bf D�monstration du lemme.} Tout d'abord, supposons que $b=2$. Comme les sommets de $\Gamma$ sont de valence $2$ ou $3$, on a deux classes d'hom�omorphismes possibles pour $\Gamma$ : la classe $8_1$ et la classe $8_2$ (voir figure 1).

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{huit.eps}
\caption{Les graphes $8_1$ et $8_2$}
\end{center}
\end{figure}

Il est clair que $\kappa(8_1) \geq (\s(8_1))^2$ et $\kappa(8_2) \geq (\s(8_2)/2)^2$, d'o� (\ref{estsup}) dans ce cas.

\medskip

On suppose maintenant $b>2$. Si 
$$
\left[\frac{\s(\Gamma)}{2 \log_2 (\frac{8}{3} b)}\right]=0,
$$
o� $[n]$ d�signe la partie enti�re d'un entier $n$, le r�sultat est imm�diat comme la complexit� d'un graphe est un entier non nul. Supposons donc 
$$
\left[\frac{\s(\Gamma)}{2 \log_2 (\frac{8}{3} b) }\right]\geq 1.
$$ 


On note $\tilde{\Gamma}$ le graphe d�fini � partir de $\Gamma$ de la mani�re suivante. Etant donn� un sommet $v$ de valence $2$, on consid�re le graphe obtenu en supprimant le sommet $v$ et les deux ar�tes $e_1$ et $e_2$ incidentes � ce sommet, et en ajoutant une nouvelle ar�te reliant les deux sommets de $e_1$ et $e_2$ restants (voir figure $2$). 
\begin{figure}[h]
\begin{center}
\includegraphics[width=4cm]{contraction.eps}
\caption{Elimination d'un sommet de valence $2$}
\end{center}
\end{figure}
On r�p�te l'op�ration pour tout sommet de valence $2$ et on obtient ainsi le graphe $\tilde{\Gamma}$. C'est un graphe $3$-r�gulier et on note $f : \Gamma \rightarrow \tilde{\Gamma}$ l'application topologique naturelle qui envoie uniform�ment une suite maximale d'ar�tes adjacentes de $\Gamma$ dont les sommets interm�diaires sont de valence $2$ sur l'ar�te correspondante de $\tilde{\Gamma}$. Soit $\tilde{\gamma}$ une courbe r�alisant sa systole et $\gamma$ son image inverse par $f$. La systole est estim�e sup�rieurement pour les graphes $3$-r�guliers de premier nombre de Betti $b$ de la mani�re suivante (voir \cite{erdosach63}) : 
$$
\s(\tilde{\Gamma}) \leq [2 \log_2 (\frac{2}{3} b) +3].
$$
 Donc il existe une ar�te $e \in \tilde{\gamma} \subset \tilde{\Gamma}$ telle que, si $C=f^{-1}(e)$, on ait 
$$
\l(C) \geq \left[\frac{\s(\Gamma)}{2 \log_2 (\frac{8}{3} b) }\right].
$$
En effet, sinon, $\l(\gamma) < \s(\Gamma)$, d'o� une contradiction. 

Soit $\Gamma \setminus C$ le compl�mentaire de la suite d'ar�tes adjacentes $C$ dans $\Gamma$ : c'est un sous-graphe de $\Gamma$ v�rifiant $b_1(\Gamma \setminus C)=b_1(\Gamma)-1$. Tout arbre maximal $T$ du graphe $\Gamma \setminus C$ fournit de mani�re �vidente au moins $[\s(\Gamma)/(2 \log_2 (\frac{8}{3} b) )]$ arbres maximaux $T'$ de $\Gamma$, et tous les arbres maximaux ainsi obtenus, lorsque l'on fait varier l'arbre initial $T$ parmi les arbres maximaux de $\Gamma \setminus C$,  sont deux � deux distincts. On en d�duit :
$$
\kappa(\Gamma) \geq \kappa(\Gamma\setminus C).\left [\frac{\s(\Gamma)}{2 \log_2 (\frac{8}{3} b) }\right]\geq \kappa(\Gamma\setminus C).\frac{\s(\Gamma)}{2( 2\log_2 (\frac{8}{3} b))}.
$$

Comme $\s(\Gamma \setminus C) \geq \s(\Gamma)$, on obtient le r�sultat par r�currence. \hspace{\stretch{1}} $\Box$\\



\noindent {\it Remarque.} Nous avons donc reli� la complexit� et la systole de tout graphe $\Gamma$ de premier nombre de Betti $b\geq 2$ de la mani�re suivante :
$$
\sqrt[b]{\kappa(\Gamma)}\geq \frac{\s(\Gamma)}{4\left (\prod_{k=2}^b(\log_2 (\frac{8}{3} k) )\right )^{1/b}}\geq \frac{\s(\Gamma)}{4\log_2 (\frac{4}{3} b)}. 
$$
De l'in�galit� (\ref{estinf}), nous d�duisons que l'ordre de grandeur dans cette estim�e inf�rieure est optimale.

\medskip

%Comme $$\sqrt[b]{\prod_{k=2}^b \log_2 k} \sim \ln b$$ lorsque $b \rightarrow +\infty$,  on obtient l'estim�e sup�rieure dans (\ref{theo1}).


\section{Complexit� et volume d'un graphe} 

Nous allons dans cette section d�finir la notion de constante systolique pour un graphe pond�r�, et ainsi pouvoir introduire une famille de graphes systoliquement �co\-nomiques. Cette famille nous permet, � l'aide d'une majoration de la complexit� d'un graphe par son volume, de d�montrer l'in�galit� inf�rieure annonc�e dans la formule (\ref{theo1}).

\medskip


Etant donn� un graphe pond�r� $(\Gamma,w)$ de premier nombre de Betti $b\geq 2$, le probl�me systolique peut �tre formul� comme suit. On d�finit la {\it constante systolique} de $\Gamma$ par
$$
\sigma(\Gamma)=\inf_w \frac{\V(\Gamma,w)}{\s(\Gamma,w)}
$$
o� $\V(\Gamma,w)$ d�signe le $1$-volume de $\Gamma$ (la somme des poids de ses ar�tes) et o� l'infimum est pris sur l'ensemble des fonctions poids de $\Gamma$. Nous avons, d'apr�s \cite{bolsze02}, 
\begin{equation} \label{syst}
\sigma(\Gamma)\geq \frac{3}{2}\frac{b-1}{\log_2 (b-1)+\log_2 \log_2 (b-1)+4}. 
\end{equation}
D'autre part, comme il a �t� d�montr� dans  \cite{babebala04}, il existe pour chaque $b\geq 2$ un graphe combinatoire de premier nombre de Betti $b$ que nous noterons $\Gamma_b$ et que nous appelerons {\it systoliquement �conomique} v�rifiant asymptotiquement
$$ 
\frac{\V(\Gamma_b)}{\s(\Gamma_b)} \lesssim 6 \frac{b}{\log_2 b},
$$ 
o� $\V(\Gamma_b)$ est le $1$-volume de $\Gamma_b$ pour la fonction poids constante �gale � $1$.

\medskip



Nous pouvons minorer l'invariant d'Hermite de la jacobienne d'un graphe pond�r� par sa constante systolique comme suit :
\begin{proposition}
Pour tout graphe pond�r� $(\Gamma,w)$ de premier nombre de Betti $b \geq 1$, on a 
$$
\mu(\Lambda(\Gamma,w))\geq \frac{\sqrt[b]{b!}}{\sigma(\Gamma,w)}.
$$
\end{proposition}


\medskip

\noindent {\bf D�monstration.} De m�me que dans le d�but de la section 1, nous nous ramenons � un graphe combinatoire. On estime sup�rieurement la complexit� de ce graphe par son volume de la mani�re suivante. Tout arbre maximal $T$ de $\Gamma$ est enti�rement d�termin� par les $b$ ar�tes de  $\Gamma \setminus T$, d'o�
$$
\kappa(\Gamma) \leq C_{\V(\Gamma)}^b \leq \frac{\V(\Gamma)^b}{b!}.
$$
On en d�duit imm�diatement le r�sultat. \hspace{\stretch{1}} $\Box$\\


Les graphes $\Gamma_b$ v�rifient donc
$$
\mu(\Lambda(\Gamma_b))\gtrsim \frac{1}{6}\frac{ \sqrt[b]{b!}}{b} \log_2 b,
$$
d'o� la minoration annonc�e en (\ref{theo1}) par application de la formule de Stirling :
\begin{equation} \label{estinf}
\mu(\Lambda(\Gamma_b))\gtrsim \frac{1}{6e} \log_2 b. 
\end{equation}

\bigskip

Nous expliquons maintenant les am�liorations 1) et 2) annonc�es dans l'introduction.

\medskip

\noindent 1) Nous pouvons, en utilisant les familles de graphes � grand tour de taille mises en �vidence dans \cite{marg88}, am�liorer pour certaines valeurs de $b$ l'estim�e (\ref{estinf}).  \linebreak G.A. Margulis a construit, pour une famille infinie $\{b_m\}_m$ de valeurs, une famille $\{G_m\}_m$ de graphes $3$-r�guliers de premier nombre de Betti $\{b_m\}_m$ pour lesquels 
$$
\s(G_m) \gtrsim \frac{4}{3} \log_2 b_m.
$$
Nous en d�duisons
\begin{equation} \label{amelio2}
\mu(\Lambda(G_m))\gtrsim \frac{4}{9e} \log_2 b_m.
\end{equation}

\medskip

2) Si l'on se restreint � certains graphes, nous pouvons estimer sup�rieurement l'invariant d'Hermite de la jacobienne par la constante systolique :
\begin{proposition}
Pour tout graphe combinatoire $\Gamma$ dont chaque sommet est de valence au moins trois et de premier nombre de Betti $b\geq 2$, 
$$
\mu(\Lambda(\Gamma))\leq \frac{3(b-1)}{\sigma(\Gamma)}.
$$
\end{proposition}


\noindent {\bf D�monstration.} Comme la valence en chaque sommet du graphe est au moins $3$, on a l'in�galit� 
$$
\V(\Gamma) \leq 3(b-1),
$$
donc
$$
\mu(\Lambda(\Gamma)) =\frac{\s(\Gamma)}{\sqrt[b]{\kappa(\Gamma)}} \leq  \s(\Gamma) \leq  \V(\Gamma)\frac{\s(\Gamma)}{\V(\Gamma)} \leq  \frac{3(b-1)}{\sigma(\Gamma)}.
$$
 \hspace{\stretch{1}} $\Box$\\

On en d�duit une am�lioration de l'in�galit� (\ref{sup}) pour cette classe de graphes, en vertu de l'estim�e systolique (\ref{syst}) : pour tout graphe $\Gamma$ dont chaque sommet est de valence au moins trois et de premier nombre de Betti $b\geq 2$, 
\begin{equation} \label{amelio1}
\mu(\Lambda(\Gamma))\leq 2(\log_2(b-1)+\log_2\log_2(b-1)+4) \lesssim 2\log_2 b.
\end{equation}

\bigskip

\noindent {\bf Remerciements.} Je remercie Roland Bacher de m'avoir sugg�rer cette �tude, ainsi que Ivan Babenko pour les nombreuses discussions que nous avons partag�.


\begin{thebibliography}{99}



\bibitem{babebala04}
Babenko, I. \& Balacheff, F.: {\it G\'eom\'etrie systolique des sommes connexes et des rev\^etements cycliques}. A para�tre dans Mathematische Annalen, publi� en ligne sur
 http://www.springerlink.com/ link.asp?id=g604234337273863.
  
\bibitem{bacharnag97}
Bacher, R., de la Harpe, P. \& Nagnibeda, T. : {\it Lattices defined by finite graphs}. Bull. Soc. Math. France {\bf 125} (1997), 167-198.

%\bibitem{bala05}
%Balacheff, F. : {\it Volume entropy, systole and stable norm on graphs}. Soumis, preprint consultable sur www.arxiv.org/abs/math.MG/0411578.



\bibitem{biggs}
Biggs, N. : {\it Algebraic graph theory}. Cambridge University Press, 1974.

\bibitem{bolsze02}
Bollob\'as, B. \& Szemer\'edi, E. : {\it Girth of sparse graphs}. J. Graph
Theory {\bf 39} (2002), 194-200.

\bibitem{busesarn94}
Buser, P. \& Sarnak, P. : {\it On the period matrix of a Riemann surface of
  large genus}. Inv. Math. {\bf 117} (1994), 27-56.


\bibitem{conslo}
Conway, J. \& Sloane, N. : {\it Sphere packings, lattices and groups}. Springer-Verlag, New-York, 1998.

\bibitem{erdosach63} 
Erd\"os, P. \& Sachs, H.: {\it Regul\"are Graphen gegebener Taillenweite mit minimaler Knotenzahl.} 
Wiss. Z. Martin-Luther-Univ.Halle-Wittenberg \textbf{12}  (1963), 251-257.



\bibitem{marg88} 
Margulis, G.A. : {\it Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators}. J.Probl.Inf.Transm. {\bf 24} (1988), no 1, 39-46.



\end{thebibliography}

\end{document}
math0506616.extracted_bib
\begin{thebibliography}{99}



\bibitem{babebala04}
Babenko, I. \& Balacheff, F.: {\it G\'eom\'etrie systolique des sommes connexes et des rev\^etements cycliques}. A para�tre dans Mathematische Annalen, publi� en ligne sur
 http://www.springerlink.com/ link.asp?id=g604234337273863.
  
\bibitem{bacharnag97}
Bacher, R., de la Harpe, P. \& Nagnibeda, T. : {\it Lattices defined by finite graphs}. Bull. Soc. Math. France {\bf 125} (1997), 167-198.

%\bibitem{bala05}
%Balacheff, F. : {\it Volume entropy, systole and stable norm on graphs}. Soumis, preprint consultable sur www.arxiv.org/abs/math.MG/0411578.



\bibitem{biggs}
Biggs, N. : {\it Algebraic graph theory}. Cambridge University Press, 1974.

\bibitem{bolsze02}
Bollob\'as, B. \& Szemer\'edi, E. : {\it Girth of sparse graphs}. J. Graph
Theory {\bf 39} (2002), 194-200.

\bibitem{busesarn94}
Buser, P. \& Sarnak, P. : {\it On the period matrix of a Riemann surface of
  large genus}. Inv. Math. {\bf 117} (1994), 27-56.


\bibitem{conslo}
Conway, J. \& Sloane, N. : {\it Sphere packings, lattices and groups}. Springer-Verlag, New-York, 1998.

\bibitem{erdosach63} 
Erd\"os, P. \& Sachs, H.: {\it Regul\"are Graphen gegebener Taillenweite mit minimaler Knotenzahl.} 
Wiss. Z. Martin-Luther-Univ.Halle-Wittenberg \textbf{12}  (1963), 251-257.



\bibitem{marg88} 
Margulis, G.A. : {\it Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators}. J.Probl.Inf.Transm. {\bf 24} (1988), no 1, 39-46.



\end{thebibliography}