<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%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*{Shallow vertex minors, stability, and dependence}
%

% Pour le sommaire
\addcontentsline{toc}{section}{A. Auteur 1 et B. Auteur 2 : Titre du talk}
%

% Pour la liste des auteurs
\index{Auteur 1, A.}\index{Auteur 2, B.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Hector Buffière}, IRIF, Université Paris Cité, et CAMS, EHESS, {\tt
hector.buffiere@ens.fr}\\
\indent
Eunjung Kim, School of Computing, KAIST, {\tt eunjungkim78@gmail.com}\\ 
\indent
Patrice Ossona de Mendez, CAMS, EHESS, {\tt pom@ehess.fr}\\

%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le rÃ©sumÃ©
	\emph{Stability} and \emph{dependence} are model-theoretic notions that have
	recently proved  highly effective in the study of structural and algorithmic
	properties of hereditary graph classes \cite{1,2}, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of \emph{nowhere dense} class). The theory of sparsity was initially built on the notion of \emph{shallow minors} and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.

	In this work, we follow a similar path, where \emph{shallow vertex minors} replace
	shallow minors. Vertex minors are a containment relation that is well suited for the
	study of hereditary and dense classes of graphs, related to the notions of flips and
	pivot minors. They generalize several properties of classical graph minors to dense
	graphs. Their shallow variant is newer and this work advocates for its usefulness in
	the structural study of hereditary classes of graphs. In this setting, we provide a neat characterization of stable/dependent hereditary classes of graphs: A hereditary class of graphs $\mathcal C$ is
	\begin{itemize}
		\item 	\emph{dependent} if and only if it does not contain all permutation graphs and, for each integer $r$,  it excludes some split interval graph as a depth-$r$ vertex minor;
		\item  	\emph{stable} if and only if, for each integer $r$,  it excludes some half-graph as a depth-$r$ vertex minor.
	\end{itemize}

	A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors. We extend this preservation result to binary structures and get, as a direct consequence, that bounded depth shallow vertex minors of graphs with bounded twin-width have bounded twin-width.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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{thebibliography}{99}

\bibitem{1}
J. Dreier, and I. Eleftheriadis, and N. M{\"a}hlmann, and R. McCarty, and M. Pilipczuk,
and S. Toru{\'n}czyk,
 \emph{First-Order Model Checking on Monadically Stable Graph Classes},
 {arXiv preprint 2311.18740 [cs.LO]},
{2023}.

\bibitem{2}
{J. Dreier, and N. M\"ahlmann, and S. Toru\'nczyk},
  \emph{Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes},
  {arXiv preprint 2403.15201v1 [math.CO]},
  {2024}.




\end{thebibliography}


\vfill
\end{document}

</pre></body></html>