\documentclass[letterpaper, 10pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}

\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{1.5cm}
\addtolength{\hoffset}{-0.5cm}
% \addtolength{\textwidth}{2cm}

\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\theoremstyle{plain}
\newtheorem{proposicion}{Proposition}
\newtheorem{lema}{Lema}
\newtheorem{teorema}{Teorema}
\newtheorem{corolario}{Corolario}
\newtheorem{conjetura}{Conjetura}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}
\DeclareMathOperator{\exc}{e}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\cc}{cc}
\DeclareMathOperator{\Q}{Q}
\DeclareMathOperator{\domatic}{d}

\begin{document}
\header{Teoría de las Gráficas II}{Cuarta tarea}
Se entrega el viernes 26 de marzo. Todos los ejercicios bien justificados.
\vspace{0.5cm}

Dados dos enteros positivos $s$ y $t$, el \emph{número de Ramsey $r(s$, $t)$} es el menor entero positivo $n$ tal que para toda gráfica $G$ de orden $n$, ora $G$ contiene $K_s$ como subgráfica, ora $\overline{G}$ (el complemento de $G$) contiene $K_t$ como subgráfica: esto es, $G$ posee ora $s$ vértices mutuamente adyacentes o un conjunto independiente de $t$ vértices. Los números de Ramsey son así llamado por Frank Ramsey, quien estudio este concepto en el marco de la Teoría de los Conjuntos y esencialmente comprobó la existencia de dichos números.  Ya que $\overline{\overline{G}}=G$ para toda gráfica $G$, se sigue que el número de Ramsey $r(s$, $t)$ es simétrico en $s$ y $t$ y $r(s$, $t)=r(t$, $s)$.

Es fácil mostrar que $r(s$, $t)$ existe si al menos uno $s$ o $t$ no exceden dos y que
\begin{displaymath}
 r(1,t)=1 \qquad r(2,t)=t\text{.}
\end{displaymath}
El grado de dificultad de determinar los valores para otros números de Ramsey se incrementa tan rápidamente como $s$ y $t$ crecen y en general valores como los anteriores no son conocidos.

A veces es conveniente trabajar con los números de Ramsey desde el punto de vista de 'coloración de aristas'. Para toda gráfica $G$ de orden $n$, el conjunto de aristas de $G$ y $\overline{G}$ forman una partición de las aristas de $K_n$.  Así, $r(s$, $t)$ puede pensarse como el menor entero positivo $n$ tal que si toda arista de $K_n$ está arbitrariamente coloreada rojo o azul (donde, por supuesto, aristas adyacentes pueden recibir el mismo color) entonces existe ora una subgráfica completa de orden $s$, en la cual todas sus aristas son rojas, ora una subgráfica completa de orden $t$, en la cual todas sus aristas son azules.  En el primer caso, diremos que existe un $K_s$ rojo; en el segundo, un $K_t$ azul.  A la coloración se le llama una \emph{coloración rojo-azul} de $K_n$.  Por ejemplo, para $t \geq 2$, $r(2$, $t) > t-1$ ya que si todas las $\binom{t-1}{2}$ aristas de $K_{t-1}$ están coloreadas con azul entonces $K_{t-1}$ no contiene ni un $K_2$ rojo ni un $K_t$ azul.  Sin embargo, $r(2$, $t)\leq t$ ya que en una coloración rojo-azul arbitraria de $K_t$, ora todas las aristas son azules y tenemos un $K_t$ azul o al menos una arista es roja y tenemos al menos un $K_2$ rojo.  Por lo tanto, $r(2$, $t)=t$.

\begin{teorema}
\label{teo:1}
 El número de Ramsey $r(3$, $3)=6$.
\end{teorema}

\begin{teorema}
 Para cualesquiera dos enteros $s$ y $t$, el número de Ramsey $r(s$, $t)$ existe; más aún,
\begin{displaymath}
 r(s,t)\leq\binom{s+t-2}{s-1}\text{.}
\end{displaymath}
\end{teorema}

\begin{corolario}
 Para enteros $s\geq 2$ y $t \geq 2$,
\begin{displaymath}
 r(s,t)\leq r(s-1,t)+r(s,t-1)\text{.}
\end{displaymath}
Más aún, si $r(s-1$, $t)$ y $r(s$, $t-1)$ son ambos impares, entonces la desigualdad estrica se satisface.
\end{corolario}

\begin{teorema}
 Para todo entero $t\geq 3$,
\begin{displaymath}
 r(3,t)\leq\frac{t^2+3}{2}\text{.}
\end{displaymath}
\end{teorema}

\begin{enumerate}
\item Prueba el Teorema~\ref{teo:1}.
\item Muestra que si $G$ es una gráfica de orden $r(s$, $t)-1$ entonces
\begin{enumerate}
\item $K_{s-1}\subseteq G$ ó $K_t \subseteq \overline{G}$,
\item $K_s\subseteq G$ ó $K_{t-1} \subseteq \overline{G}$.
\end{enumerate}
\item Si $2\leq s' \leq s$ y $3\leq t' \leq t$ entonces prueba que $r(s'$, $t')\leq r(s$, $t)$. Más aún, prueba que la igualdad se tiene si y sólo si $s'=s$ y $t'=t$.
\item Muestra que $r(3$, $4)=9$.
\item La \emph{composición} de gráficas $G$ y $H$ es la gráfica $G[H]$ con conjunto de vértices $V(G)\times V(H)$, en la cual $(u$, $v)$ es adjacente a $(u'$, $v')$ si y sólo si $uu' \in E(G)$ o $u=u'$ y $vv' \in E(H)$.
\begin{enumerate}
\item Muestra que $\alpha(G[H])\leq\alpha(G)\alpha(H)$.
\item Usando lo anterior, muestra que:
\begin{displaymath}
 r(kl+1,kl+1)-1\geq(r(k+1,k+1)-1)\times(r(l+1,l+1)-1)\times{.}
\end{displaymath}
\item Deduce que $r(2^n+1$, $2^n+1)\geq 5^n+1$ para todo $n \geq 0$.
\end{enumerate}

\item Considera la gráfica obtenida a partir de $C_3$ y $C_5$, uniendo cada  vértice de $C_3$ con todos los vértices de $C_5$.  Muestra que dicha gráfica no posee $K_6$ pero que toda coloración rojo-azul arbitraria de sus aristas produce un triángulo monocromático.
\item Considera $G_1$, $G_2$, \ldots, $G_m$ gráficas.  El \emph{número generalizado de Ramsey} $r(G_1$, $G_2$, \ldots, $G_m)$ es el menor entero $n$ tal que toda $m$-coloración de aristas $(E_1$, $E_2$, \ldots, $E_m)$ de $K_n$ contiene, para algún $i$, una subgráfica isomorfa a $G_i$ de color $i$.  Muestra que si $G$ es una trayectoria de longitud tres y $h$ es un ciclo de longitud cuatro entonces $r(G$, $G)=5$, $r(G$, $H)=5$ y $r(H$, $H)=6$.
\end{enumerate}


\end{document}