%Compiler avec pdflatex, le rÃ©sultat ne doit pas dÃ©passer une page
%Merci de respecter scrupuleusement ce modÃ¨le.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{F. Galliot, S. Gravier, I. Sivignon  : Composantes connexes $(k-2)$-linéaires d'un hypergraphe de rang $k$}
%

% Pour le sommaire
\addcontentsline{toc}{section}{F. Galliot, S. Gravier, I. Sivignon : Composantes connexes $(k-2)$-linéaires d'un hypergraphe de rang $k$}
%

% Pour la liste des auteurs
\index{Galliot, F.}\index{Gravier, S.}\index{Sivignon, I.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Florian Galliot}, Institut Fourier, Grenoble, {\tt florian.galliot@univ-grenoble-alpes.fr}\\
\indent
Sylvain Gravier, Institut Fourier, Grenoble, {\tt sylvain.gravier@univ-grenoble-alpes.fr}\\
\indent
Isabelle Sivignon, GIPSA-lab, Grenoble, {\tt isabelle.sivignon@grenoble-inp.fr}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le rÃ©sumÃ©


Un \textit{chemin linéaire} dans un hypergraphe est une suite d'arêtes $(e_1,\ldots,e_L)$ telle que $|e_i \cap e_{i+1}|=1$ et $e_i \cap e_j = \emptyset$ si $|i-j|>1$. Notre motivation première est le problème de connectivité associé aux chemins linéaires dans les hypergraphes 3-uniformes (cf. Figure \ref{figure_galliot}). Si l'existence de tels chemins fait l'objet de nombreux résultats extrémaux dans la littérature, aucun outil de nature qualitative, adapté à des hypergraphes moins denses, n'a été développé. Nous étudions ici les composantes connexes linéaires, introduisant pour cela des concepts qui se généralisent aux hypergraphes de rang $k \geq 4$ en remplaçant la linéarité par une notion nouvelle de \textit{$(k-2)$-linéarité}.

\medskip

Nous définissons un \textit{chemin $q$-linéaire} dans un hypergraphe $H$ comme une suite d'arêtes $(e_1,\ldots,e_L)$ telle que $|e_i \cap e_{i+1}| \in [\![1,q]\!]$ et $e_i \cap e_j = \emptyset$ si $|i-j|>1$. Dans ce travail, nous étudions le cas $q=k-2$ où $k$ est le rang de $H$, c'est-à-dire qu'on interdit dans le chemin les intersections d'arêtes de taille $k-1$. Le cas des chemins linéaires dans les hypergraphes 3-uniformes correspond à $k=3$ i.e. $q=1$. Nous présentons deux résultats liés, l'un structurel et l'autre algorithmique : nous décrivons la structure d'\textit{archipel} du sous-hypergraphe induit par une composante connexe $(k-2)$-linéaire, via une preuve algorithmique qui fournit un algorithme de calcul d'une composante connexe $(k-2)$-linéaire en temps $O(m^2k)$ où $m=|E(H)|$.

\medskip

Mentionnons deux applications du résultat algorithmique. La première résout la complexité du jeu positionnel \textit{Maker-Breaker} sur les hypergraphes de rang 3 : le vainqueur est décidé en temps polynomial. La seconde concerne le problème NP-complet \textsc{PAFP} d'existence d'un chemin induit bleu entre deux sommets donnés d'un graphe arête-bicoloré : il y a correspondance entre chemins $(k-2)$-linéaires dans $H$ et chemins induits bleus dans un \textit{line graph bicoloré} de $H$, ainsi chaque classe de line graphs bicolorés reconnaissable efficacement mettrait au jour une nouvelle instance polynomiale de \textsc{PAFP}.


%Veillez Ã  ce que le rÃ©sumÃ© n'excÃ¨de pas {\bf 1 page}, en ne modifiant
%ni la taille de la police, ni les marges, ni l'Ã©cart entre les
%  lignes, ni l'Ã©cart entre les mots, ni l'Ã©cart entre les
%  lettres\footnote{et en Ã©vitant de mettre des notes de bas de page
%    pour caser plus de texte ni vu ni connu!}.
%
%\smallskip
%
%Si vous souhaitez ajouter une figure, faites-en sorte qu'elle soit
%compilable par {\tt pdflatex} (pas de {\tt pstricks} ou d'{\tt eps}). Vous pouvez aussi
%utiliser tikz si vous le souhaitez.
%
%\smallskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Eventuellement, une figure, pdf ou png (PAS eps)
%\begin{figure}[htb]
%\begin{center}
%\includegraphics[height=3cm]{gtree}
%\caption{Un graphe.
%\label{fig:graphe}}
%\end{center}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[htb]
\begin{center}
\includegraphics[height=.75cm]{Galliot_JGA.png}
\caption{Un chemin linéaire 3-uniforme entre $x$ and $y$. 
\label{figure_galliot}}
\end{center}
\end{figure}

%Vous pouvez Ã©galement ajouter des rÃ©fÃ©rences, comme~\cite{nk1} ci-dessous.



%\begin{thebibliography}{99}
%
%\bibitem{nk1}
%N.~Trotignon and K.~Vu{\v s}kovi{\'c}, \emph{A structure theorem for graphs with no cycle with a unique chord and
%  its consequences}, J. Graph Theory {\bf 63(1)} (2010), 31--67.
%
%\end{thebibliography}


\vfill
\end{document}