% $Header:
% /cvsroot/latex-beamer/latex-beamer/solutions/conference-talks/conference-ornate-20min.en.tex,v %%@
%1.6 2004/10/07 20:53:08 tantau Exp $

\documentclass{beamer}



\usepackage{xmpmulti}
\DeclareGraphicsRule{*}{mps}{*}{}  

\mode<presentation> {
  \usetheme{Boadilla}
\useinnertheme[shadow]{rounded}
%\usecolortheme{crane}
\usecolortheme{orchid}



  \setbeamercovered{invisible}
 %\setbeamercovered{transparent}}
}
% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

\usepackage[english]{babel}
\usepackage{times}
\usepackage[T1]{fontenc}
\definecolor{DarkGreen}{rgb}{0.1,0.6,0.2}   %define a custom color
\definecolor{violet}{rgb}{0.95,0,0.8}
\definecolor{DarkBlue}{rgb}{0,0,0.6}
\definecolor{DDarkBlue}{rgb}{0,0,0.2}
\definecolor{LightBlue}{rgb}{0.8,0.8,1}
\definecolor{LLightBlue}{rgb}{0.95,0.95,1}
\definecolor{cyan}{cmyk}{1,0,0,0.7}
\definecolor{yellow}{cmyk}{0,0,1,0.5}
\definecolor{vsarga}{cmyk}{0,0,1,0}
\definecolor{lgreen}{rgb}{0.1,0.6,0.2}
\definecolor{green}{rgb}{0,0.7,0}
\definecolor{piros}{rgb}{1,0,0}
\definecolor{spiros}{rgb}{1,0.1,0}
\definecolor{ppiros}{rgb}{1,0.3,0}
\definecolor{lila}{rgb}{.7,0.1,.7}

\definecolor{tetel}{rgb}{0,0,0.5}

\newcommand{\piros}[1]{\textcolor{piros}{#1}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\green}[1]{\textcolor{DarkGreen}{#1}}
\newcommand{\cyan}[1]{\textcolor{cyan}{#1}}
\newcommand{\lila}[1]{\textcolor{lila}{#1}}
\newcommand{\yellow}[1]{\textcolor{yellow}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\kw}[1]{\color{red}\bfseries #1}
\newcommand{\uu}{\r{u}}
\newcommand{\nyil}{~$\Longrightarrow$~}
\newcommand{\vnyil}{~$\Longleftarrow$~}
\newcommand{\ellent}{~~\red{\Huge $\lightning$}}
\newcommand{\pipa}{~~\green{\large $\surd$}}

\newcommand{\p}{\mathop{\mbox{perm}}\nolimits}
\setbeamercolor{megj}{fg=orange!80!black}
\setbeamercolor{zaro}{fg=purple}
\newcommand{\imp}{\ {\color{green!50!black} $\mathbf{\Rightarrow}$}\ }

%%szines tetel environmentek
\newcommand{\newthm}[3]{\newtheorem{tt#2}{#2}
\newenvironment{#1}{\setbeamercolor{block title}{bg=#3}\begin{tt#2}}{\end{tt#2}}}
\newcommand{\renewthm}[3]{\newtheorem{tt#2}{#2}
\renewenvironment{#1}{\setbeamercolor{block title}{bg=#3}\begin{tt#2}}{\end{tt#2}}}

\renewthm{definition}{Definition}{tetel!50!orange}
\renewthm{theorem}{Theorem}{tetel}
\newthm{question}{Question}{red!70!tetel}
\newthm{conj}{Conjecture}{red!50!tetel}
\newenvironment{proof2}{\setbeamercolor{block title}{bg=green!50!tetel}\begin{proof}}{\end{proof}}
\newthm{obs}{Observation}{violet!50!tetel}
\renewthm{corollary}{Corollary}{brown!50!tetel}
\renewthm{lemma}{Lemma}{violet!60!tetel}
\newthm{prop}{Proposition}{LightBlue!60!tetel}


% \newtheorem{thm}{Theorem}
% \newtheorem{prf}{Proof}
% \newtheorem{defin}[thm]{Definition}
% \newtheorem{cons}[thm]{Corollary}
% \newtheorem{rmk}[thm]{Remark}
% \newtheorem{exmpl}[thm]{Example}
% \newtheorem{prop}[thm]{Claim}
\newcommand{\notdiv}{|\!\! ^{_\diagdown}}
\newcommand{\il}{\ell}


% \pgfdeclareimage[interpolate=true,width=9cm]{p4c5graf}{p4c5} 
% \pgfdeclareimage[interpolate=true,width=1.5cm]{c4graf}{c4} 
% \pgfdeclareimage[interpolate=true,width=6cm]{csillh}{csh} 
 \pgfdeclareimage[interpolate=true,width=7cm]{pl1}{fig1} 
\pgfdeclareimage[interpolate=true,width=6cm]{pl2}{fig2} 




\title{Extremal stable graphs}

\author[Gyula Y. Katona]{Illés Horváth\inst{1} \and \alert{\underline{Gyula Y. Katona}}\inst{2}}
\institute[Hungary] 
{\inst{1}
Department of Stochastics\\
Budapest University of Technology and Economics
\and \inst{2}
Department of Computer Science and Information Theory\\
Budapest University of Technology and Economics}
\date[CTW09]% (optional, should be abbreviation of conference name)
{3 June, 2009}


\subject{Graph Theory}

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

 \pgfdeclareimage[height=0.5cm]{university-logo}{bme-logo}
 \logo{\pgfuseimage{university-logo}}


% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command:

%\beamerdefaultoverlayspecification{<+->}

%-----------------------


\begin{document}

\begin{frame}
  \titlepage
\end{frame}



\section{Introduction}

%-----------------------
\begin{frame}

\frametitle{Introduction}



\begin{question}Let $\Pi$ be a graph property so that if $G_1\in \Pi$
  and $G_1$ is a subgraph of $G_2$, then $G_2\in \Pi$.
  \green{(i. e. being non-$\Pi$ is a hereditary graph property.)}\pause \\
  What is the minimum number of edges in a graph $G\in \Pi$ on $n$
  vertices if removing any $k$ edges (or vertices) from the graph
  still preserves $\Pi$?\pause
\end{question}

\lila{Examples:}
\begin{itemize}
\item What is the minimum number of edges in a $k$-connected
or $k$-edge connected graph? \pause
\item What is the miminum number of edges in hypo-hamiltonian graph?\pause
\item What is the mininum number of edges in graph that is still
  Hamiltonian after removing $k$ edges (or vertices)?
\end{itemize}
\end{frame}


\begin{frame}

\frametitle{Notations and definitions}

\green{We concentrate on the problem where $\Pi$ is the property that
  $G$ contains a given fixed subgraph $H$.} \pause\\
\lila{This clearly satisfies the assumption on $\Pi$.}\pause\\
\blue{We only consider simple, undirected graphs.}\pause

\begin{definition}[Stability] Let $H$ be a fixed graph. If the graph
  $G$ has the property that removing any $k$ edges of $G$, the
  resulting graph still contains \blue{(not necessarily spans)} a
  subgraph isomorphic with $H$, then we say that $G$ is
  \alert{$k$-stable} with regard to $H$. \pause
\end{definition}

\begin{definition}By \alert{$S_H(k)$} we denote the minimum number of
  edges in any $k$-stable graph.\pause
\end{definition}

\green{Note that there is no ``in a graph with $n$ vertices'' in the
  definition.}

\end{frame}

\begin{frame}

\frametitle{A trivial case: $H=P_2$}
\begin{center}
\includegraphics[width=2cm]{p2}
\end{center}

\begin{prop} $S_{P_2}(k)=k+1$\pause
\end{prop}

\green{Extremal graph:} Any graph with $k+1$ edges.\pause

\begin{lemma} For any graph $H$, we have
 $S_H(k)\geq k+|E(H)|$.\pause
\end{lemma}

\begin{proof2} Otherwise there aren't enough edges  to form $H$.
\end{proof2}


\end{frame}

\begin{frame}
\frametitle{An easy case: $H=P_3$}


\begin{center}
\includegraphics[width=3cm]{p3}
\end{center}

\begin{prop} $S_{P_3}(k)=k+2=k+|E(P_3)|$\pause
\end{prop}

\green{Extremal graph:} A star with $k+2$ edges.


\begin{center}
\includegraphics[width=4cm]{star}
\end{center}
\end{frame}

\begin{frame}
\frametitle{An other easy case: $H=2P_2$}

\begin{center}
\includegraphics[width=2cm]{2p2}
\end{center}

\begin{prop} $S_{2P_2}(k)=k+2=k+|E(2P_2)|$\pause
\end{prop}

\green{Extremal graph:}  $k+2$ independent edges.
\end{frame}


% -----------------------
\begin{frame}

\frametitle{Linear bounds}

\begin{prop} Let $H$ be fixed.\\
(a) $S(k)\geq k+|E(H)|$.\\
(b) $S(k)\leq (|V(H)|+1)k$ if $k$ is large enough.\pause
\end{prop}

\begin{proof2}
(a) is trivial,\pause\\ (b) is a consequence of Turán's theorem.\pause
\end{proof2}

\medskip
\lila{For a fixed $H$ graphs we are interested in the exact value of
$S(k)$ and also the extremal graphs.} 
%(e. g. the graphs which are
%$k$-stable and have the minimal number of edges among all $k$-stable
%graphs).

\end{frame}

%-----------------------

% \begin{frame}

% \frametitle{Motivation for $P_4$-stability}

% From now on, we turn to the case $H=P_4$, where $P_4$ is the path consisting of 3 edges on 4 vertices.

% \pause

% \ \\

% This question was first raised by Frankl and Katona in [1]. They defined $S(k)$ as the function corresponding to $H=P_4$, proved a result involving $S(k)$ for Hamiltonian chains in 3-regular hypergraphs, and stated a conjecture for the exact value of $S(k)$.

% \ \\

% For details, see [1].

% \end{frame}

%-----------------------

\section{Main result}

\begin{frame}

\frametitle{Main result: $H=P_4$}

%The main result is the exact value of $S(k)$ (for $H=P_4$):

\begin{theorem}$S(1)=4$, and for $k\geq 2$,
$$S(k)=k+\left\lceil\sqrt{2k+\frac{9}{4}}+\frac{3}{2} \right\rceil.$$
\end{theorem}

\pause

The above formula is equivalent with the following:


\begin{theorem}

$S(1)=4, S(2)=6$, and if $k\geq 3$,

$$S(k)=\left\{
\begin{array}{ll}
S(k-1)+2 &\textnormal{if $k=\binom{\il}{2}$ for some integer $\il$} \\
S(k-1)+1 &\textnormal{otherwise} \\
\end{array}\right.$$
\end{theorem}

\end{frame}


\section{Outline of proof}
%-----------------------

% \begin{frame}

% \frametitle{Ideas of the proof}

% For the lower bound:
% \begin{itemize}
% \item The problem rephrased as a covering problem
% \item Introduction of the parameter $s$
% \item Proof for small values of $s$
% \item Estimate on the dominance number of a graph for large values of $s$
% \end{itemize}

% \ \\

% For the upper bound, examples of stable graphs are needed.

% \end{frame}

%-----------------------

\begin{frame}

\frametitle{Covering with triangles and stars}

\begin{prop} If $G$ does not contain $P_4$ as a subgraph, then every
  component of $G$ is a triangle or a star.
\end{prop}

\begin{center}
\includegraphics[width=10cm]{tristar}
\end{center}

\end{frame}

\begin{frame}

\frametitle{Covering with triangles and stars}

\begin{prop} If $G$ is a graph with \lila{$e$} edges on
  \lila{$n$} vertices, then\\
  $G$ is $k$-stable \alert{$\iff$} the vertices of $G$ cannot be
  covered by \lila{$k+n-e$} stars and any number of triangles.\pause
\end{prop}



\begin{proof2} $G$ is not $k$-stable if there is a subgraph with $e-k$
  edges of $G$ such that it does not contain $P_4$.\pause \\
 That subgraph is a
  union of triangles and stars, and the number of stars is $n-(e-k)$.
  \pause \\
\lila{(In triangles, the number of edges is equal to the number of
  vertices, while in a star, the number of edges is 1 less, so we
  ``lose'' an edge for every star.)}
\end{proof2}

\end{frame}

%-----------------------
\begin{frame}

\frametitle{Examples for the lower bound}

 \lila{We need to show that any graph with $<S(k)$ edges is not $k$-stable} 
 \alert{$\iff$}  \green{the vertices  cannot be
  covered by \lila{$k+n-e$} stars and any number of triangles.}\pause

\medskip
\blue{$k=3, S(k)=8$}\pause

\begin{center}
   \multiinclude[<+-| visible@+->][graphics={width=9cm}]{lower-ex}
\end{center}


\end{frame}

\begin{frame}
\frametitle{Examples for the lower bound}

 \lila{We need to show that any graph with $<S(k)$ edges is not $k$-stable} 
 \alert{$\iff$}  \green{the vertices  cannot be
  covered by \lila{$k+n-e$} stars and any number of triangles.}

\medskip
\blue{$k=3, S(k)=8$}

\begin{center}
   \multiinclude[<+-| visible@+->][graphics={width=5cm}]{lower-ex2}
\end{center}


\end{frame}

\begin{frame}
\frametitle{Examples for the lower bound}

 \lila{We need to show that any graph with $<S(k)$ edges is not $k$-stable} 
 \alert{$\iff$}  \green{the vertices  cannot be
  covered by \lila{$k+n-e$} stars and any number of triangles.}

\medskip
\blue{$k=3, S(k)=8$}

\begin{center}
   \multiinclude[<+-| visible@+->][graphics={width=5cm}]{lower-ex4}
\end{center}


\end{frame}

\begin{frame}

\frametitle{Examples for the lower bound}

 \lila{We need to show that any graph with $<S(k)$ edges is not $k$-stable} 
 \alert{$\iff$}  \green{the vertices  cannot be
  covered by \lila{$k+n-e$} stars and any number of triangles.}

\medskip
\piros{$k=6, S(k)=12$}

\begin{center}
   \multiinclude[<+-| visible@+->][graphics={width=5cm}]{lower-ex3}
\end{center}


\end{frame}

\begin{frame}

\frametitle{Lower bound}

\begin{definition}
  Given a graph $G$ with $e\geq 5$ edges on $n$ vertices, let $\il$ be
  the largest integer such that $e\geq \binom{\il-1}{2}+1$ (that is,
  $\il$ is the smallest possible number of vertices that can fit $e$
  edges), and let $s=n-\il$.

$s\geq 0$ because of the definition of $\il$; $s$ measures how
'spread-out' $G$ is.\pause
\end{definition}


\begin{theorem}[Lower bound] If the graph $G$ has $e\geq 5$ edges,
  then $G$ can be covered by $s+1$ stars and any number of triangles.
\end{theorem}

\pause $S(k)\geq k+\left\lceil\sqrt{2k+\frac{9}{4}}+\frac{3}{2}
\right\rceil$ follows directly from the above.

\end{frame}

%-----------------------

\begin{frame}

\frametitle{Lower bound - cases}

\green{For different values of $s$, the methods
are different.}

\pause

\begin{lemma}[$s=0$ or $s=1$] The vertices can be covered by $s+1$ stars and \alert{at most 1 triangle}.\pause
\end{lemma}

\green{The proof is long but elementary.}

\pause

\begin{lemma}[$s\ge 2$] The vertices can be covered by $s+1$ stars.\pause
\end{lemma}

\alert{No triangles are needed.}

\pause

\medskip
\lila{If only stars are used, 
then the centers of the stars forms a ''dominating vertex set''.}

\end{frame}


\begin{frame}
\frametitle{Lower bound - cases}

The proof uses the following theorem:

\begin{theorem}[Vizing, 1965] If $G$ is a connected graph on
  \lila{$n$} vertices and \lila{$e$} edges, then the vertices can be
  dominated by a set of size
\[\beta(G)\le \left\lfloor \frac{1+2n-\sqrt{8e+1}}{2}\right\rfloor\]
if $e\le \frac{(n-2)(n-3)}{2}$.
\end{theorem}

\end{frame}
% -----------------------

\begin{frame}

\frametitle{Upper bound}

\begin{theorem}[Upper bound] $S(1)=4$, and for $k\geq 2$,
$S(k)\leq k+ \left\lceil\sqrt{2k+\frac{9}{4}}+\frac{3}{2} \right\rceil$.
\end{theorem}


\pause

Rephrased for coverings:

\begin{theorem} For every $k\geq 2$, there exists a graph $G$ with
  $e=k+\left\lceil\sqrt{2k+\frac{9}{4}}+\frac{3}{2} \right\rceil$
  edges that is $k$-stable, that is, it cannot be covered by $s=k+n-e$
  stars and any number of triangles.

\end{theorem}

\end{frame}

%-----------------------

\begin{frame}

\frametitle{Upper bound}

\begin{proof2} Let $\il$ be the unique integer for which 
$\binom{\il-2}{2}\leq k\leq\binom{\il-1}{2}-1$.

There are 2 types of constructions:\pause
\begin{enumerate}
\item If $3\notdiv \il$, then an almost complete graph, \pause
\item If $3|\il$, then a complete graph with pendant edges.
\end{enumerate}
\end{proof2}


\end{frame}

%-----------------------

\begin{frame}
\frametitle{Constructions}

\begin{center}
 
    \begin{tabular}{|c|c|c|}
      \hline
\blue{$k$} & \blue{$S(k)$} & extremal graph\\ \hline\hline
$1$ & $4$ & \includegraphics[heigth=1mm]{s1}\\ \hline
$1$ & $6$ & \includegraphics[heigth=1mm]{s2}\\ \hline
$1$ & $6$ & \includegraphics[heigth=1mm]{s2}\\ \hline
$1$ & $6$ & \includegraphics[heigth=1mm]{s2}\\ \hline

    \end{tabular}
 
\end{center}

\end{frame}

%-----------------------

% \begin{frame}
% \frametitle{Constructions}

% \begin{center}
%    \multiinclude[<+-| visible@+->][graphics={width=5cm}]{construct2}
% \end{center}

% \end{frame}

\section{Application}
%-----------------------

\begin{frame}

\frametitle{Application}

\begin{definition} A $v_1, v_2, \dots, v_n$ permutation of the
  vertices of an $r$-regular hypergraph is a Hamiltonian chain if any
  $r$ (cyclically) consecutive vertices form an edge.
\end{definition}

\begin{definition} A hypergraph is \emph{$k$-edge-hamiltonian} if it
  has the property that removing any $k$ edges, the resulting
  hypergraph still contains a Hamiltonian chain.
\end{definition}

\pause

\begin{theorem}[Frankl, Katona] For every 3-regular
  $k$-edge-hamiltonian hypergraph with $h$ edges on $n$ vertices,
  $$h\geq \frac{S(k)}{3}n.$$
\end{theorem}

\end{frame}

%-----------------------

\begin{frame}

\frametitle{Bibliography}

\begin{thebibliography}{9}

\bibitem{frankl}
{\scshape P. Frankl, G. Y. Katona},
\newblock Extremal $k$-edge-hamiltonian hypergraphs,
\newblock  {\itshape Discrete Mathematics } (2008) {\bfseries 308},
pp. 1415--1424

\bibitem{pww}
{\scshape M. Paoli, W. W. Wong, C. K. Wong},
\newblock Minimum $k$-Hamiltonian graphs. II.,
\newblock  {\itshape J. Graph Theory } (1986) {\bfseries 10},
no. 1, pp. 79--95
 
\bibitem{rauten}
{\scshape D. Rautenbach},
\newblock A linear Vizing-like relation between the size and the domination number of a graph,
\newblock  {\itshape J. Graph Theory } (1999) {\bfseries 31},
no. 4, pp. 297--302 

\bibitem{vizing}
{\scshape V. G. Vizing},
\newblock An estimate of the external stability number of a graph,
\newblock  {\itshape Dokl. Akad. Nauk SSSR } (1965) {\bfseries 52},
pp. 729--731

\end{thebibliography}

\end{frame}

\end{document}