%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 13 Jun 2017 05:17:14pm -03 by yoshi on korujinha.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
%----------------------------

%right pdf-output for special characters
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}

%\usepackage{lmodern}
\usepackage{amssymb}

\usepackage{xcolor}
\usepackage[backref]{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!60!black},
    citecolor={green!60!black},
    urlcolor={blue!60!black}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}
%\lfoot{}
\cfoot{}
%\rfoot{\today, \currenttime}
\fancyfoot[RO,LE]{\thepage}
\fancyfoot[LO,RE]{{\footnotesize\today, \currenttime}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%------------------ disjoint union with dot -------------------------------%
\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\dcup}{\charfusion[\mathbin]{\cup}{\cdot}}
\newcommand{\bigdcup}{\charfusion[\mathop]{\bigcup}{\cdot}}
%------------------ disjoint union with dot -------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{datetime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{lineno}
\newcommand*\patchAmsMathEnvironmentForLineno[1]{%
\expandafter\let\csname old#1\expandafter\endcsname\csname #1\endcsname
\expandafter\let\csname oldend#1\expandafter\endcsname\csname end#1\endcsname
\renewenvironment{#1}%
{\linenomath\csname old#1\endcsname}%
{\csname oldend#1\endcsname\endlinenomath}}% 
\newcommand*\patchBothAmsMathEnvironmentsForLineno[1]{%
\patchAmsMathEnvironmentForLineno{#1}%
\patchAmsMathEnvironmentForLineno{#1*}}%
\AtBeginDocument{%
\patchBothAmsMathEnvironmentsForLineno{equation}%
\patchBothAmsMathEnvironmentsForLineno{align}%
\patchBothAmsMathEnvironmentsForLineno{flalign}%
\patchBothAmsMathEnvironmentsForLineno{alignat}%
\patchBothAmsMathEnvironmentsForLineno{gather}%
\patchBothAmsMathEnvironmentsForLineno{multline}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage{refcheck}
%\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\tiny ind}}}}}

\def\inR{\mathrel{\in_{\text R}}} 
\def\inU{\mathrel{\in_{\text U}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cK{\mathcal K}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\tG{\widetilde G}
\def\tcG{\widetilde\cG}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}
\def\PG{\mathop{{\rm PG}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bfd{\textbf{d}}
\def\bff{\textbf{f}}
\def\bfp{\textbf{p}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\def\ldens{\underline\bfd}
\def\udens{\overline\bfd}
\def\lldens{\underline\bfdelta}
\def\uldens{\overline\bfdelta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}

\def\datedue#1{{\bf$\boldsymbol\{$\textsl{Data de entrega}: #1$\boldsymbol\}$}}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC6904 Combinatória Contemporânea I]%
{Tópicos em Combinatória Contemporânea I\\
  \bigskip\bigskip{\bf\textit{1{\tiny o.} Semestre de 2017}}\\
  \bigskip\bigskip Exercícios
}  

\shortdate
\yyyymmdddate
\def\today{\number\year/\number\month/\number\day}
\settimeformat{ampmtime}
\date{Versão de \today, \currenttime}
%\date{Versão de \today}

\maketitle

\linenumbers 
\onehalfspace
%\pagestyle{plain}
\pagestyle{fancy}

\noindent\textbf{Entrega.}
Entregue suas soluções no Paca.  Soluções entregues fora de prazo
valerão menos.

\medskip

\noindent\textbf{Política de colaboração e uso de fontes.}
Todo trabalho entregue por você deve ser seu.  Você não deve fornecer
suas soluções a seus colegas e você não deve procurar soluções de
terceiros (como colegas ou na Web).  Por outro lado, você é encorajado
a discutir com seus colegas o material visto em sala e os enunciados
dos exercícios.  Caso você acidentalmente encontre a solução de algum
exercício em algum lugar, você deve citar esta fonte em sua solução.
Caso você acidentalmente acabe colaborando com colegas na descoberta
de uma solução, você deve citar esta colaboração em sua solução.  Seu
desempenho nesta disciplina ficará prejudicado caso você viole essas
regras.

\medskip

\begin{enumerate}
  
\item Prove as seguintes estimativas.  
  \begin{enumerate}[label=\rmlabel]
  \item $1+x\leq\e^x$ para todo~$x\in\RR$.
  \item $1+x>\exp\big\{x-x^2/2\big\}$ para todo~$0<x\leq1$. 
  \item $1-x>\exp\big\{-x-x^2\big\}$ para todo~$0<x<x_0$,
    para algum~$x_0>0$.  De fato, podemos tomar, por exemplo,~$x_0=0{.}68$.  
  \item Prove que $1+x\geq\exp\{x/(1+x)\}$ para todo~$x>-1$.
  \end{enumerate}

  \noindent[\textit{Sugestão.} Lembre que~$1/(1-x)=1+x+x^2+\dots$ uniformemente
  se~$|x|\leq x_0$ e~$x_0<1$.  Integre ambos os lados para obter
  \begin{equation}
    \label{eq:1}
    -\log(1-x)=x+{1\over2}x^2+{1\over3}x^3+\dots\ ]  
  \end{equation}
    
\item\label{Q:binom_bds} Prove as seguintes estimativas para~$a\choose b$,
  onde~$a$ e~$b$ são inteiros não-negativos.
  \begin{enumerate}[label=\rmlabel]
  \item Se~$a\geq b$, então
    \begin{equation}
       \label{eq:binom_lwbd}
       {a\choose b}\geq\(a\over b\)^b.
    \end{equation}
     
  \item Ademais, 
    \begin{equation}
       \label{eq:binom_upbd1}
       {a\choose b}\leq{a^b\over b!}.
    \end{equation}

  \item\label{item:babai} Para todo~$b>0$, 
    \begin{equation}
       \label{eq:binom_upbd2}
       {a\choose b}\leq\(\e a\over b\)^b.
    \end{equation}
    \hint{Avalie~$(1+x)^a$ por cima e por baixo para~$x=b/a$.  Use,
    para tanto, $1+x\leq\e^x$ e o binômio de Newton:
    $(1+x)^a\geq{a\choose b}x^b$.}

  \item Prove a seguinte versão mais forte de~\ref{item:babai}:
  se~$b\leq a$, então
    \begin{equation}
       \label{eq:binom_upbd3}
       \sum_{0\leq j\leq b}{a\choose j}\leq\(\e a\over b\)^b.
    \end{equation}
  \end{enumerate}
  
\item A fórmula de Stirling diz que 
  \begin{equation}
    \label{eq:Stirling}
    n!=(1+o(1))\(n\over\e\)^n\sqrt{2\pi n},
  \end{equation}
  onde~$o(1)\to0$ conforme~$n\to\infty$.  
  \begin{enumerate}[label=\rmlabel]
  \item  Prove que, para todo~$\ell$ fixo, independente de~$n$, temos
    \begin{equation}
      \label{eq:middle_bin}
      {n\choose\lfloor n/2\rfloor+\ell}=(1+o(1))2^n\sqrt{2\over\pi n},
    \end{equation}
    onde~$o(1)\to0$ conforme~$n\to\infty$.
    
  \item Prove que se~$k=k(n)=n/2+c_n\sqrt n$, onde~$c_n\to c$
    ($n\to\infty$) e~$c$ é uma constante, então
    \begin{equation}
      \label{eq:middle_binom}
      {n\choose k}={n!\over k!(n-k)!}\sim{d\over\sqrt n}2^n,
    \end{equation}
    onde~$d=d(c)>0$ é uma constante que depende apenas de~$c$.

  \item Prove que, para todo~$0<\alpha<1$ fixo, temos 
    \begin{equation}
      \label{eq:entropy_binom}
      {n\choose\lfloor\alpha
      n\rfloor}=\(1\over\alpha^\alpha(1-\alpha)^{1-\alpha}\)^{(1+o(1))n}, 
    \end{equation}
    ou, equivalentemente,
    \begin{equation}
      \label{eq:entropy_binom.2}
      \lim_{n\to\infty}{1\over n}\log{n\choose\alpha n}=H(\alpha),
    \end{equation}
    onde~$H(\alpha)=\alpha\log(1/\alpha)+(1-\alpha)\log(1/(1-\alpha))$ é a
    assim chamada função entropia.
  \end{enumerate}
  
\item{}\label{ex:zst}Sejam $(A_1,B_1),\dots,(A_m,B_m)$ pares de
  conjuntos finitos com $A_{i} \cap B_{i} = \emptyset$ para todo~$i$ e
  com $A_{i} \cap B_{j} \neq \emptyset$ ou
  $A_{j} \cap B_{i} \neq \emptyset$ para todos os~$i$ e~$j$
  com~$i \neq j$.  Ademais, suponha que $|A_i| \leq a$ e
  $|B_{i}| \leq b$ para todo~$i$.  Prove que
  \begin{equation}
    m \leq \frac{(a+b)^{a+b}}{a^{a}b^{b}}.
  \end{equation}\hint{Prove que, para qualquer $0 < p < 1$, tem-se
    \begin{equation}
      \label{eq:zst}
      \sum_{i=1}^{m} p^{|A_i|}{(1-p)}^{|B_i|}\leq 1.
    \end{equation}
    Utilize essa cota para derivar o resultado.}
  \datedue{2/4/2017}

\item{}[Soma por partes] Sejam~$(a_n)_{n\geq1}$ e~$(b_n)_{n\geq1}$
  duas sequências.  Ponha~$A_n=\sum_{1\leq k\leq n}a_n$ ($n\geq0$).
  Prove que 
  \begin{equation}
    \label{eq:2}
    \sum_{1\leq n\leq N}a_nb_n=\sum_{1\leq n<N}A_n(b_n-b_{n+1})+A_Nb_N.
  \end{equation}

\item{}Seja~$A=\{a_1<a_2<\dots\}$ uma sequência de inteiros
  positivos.  Lembre que~$\ldens(A)$, $\udens(A)$, $\lldens(A)$
  e~$\uldens(A)$ denotam as densidades naturais e logarítmicas
  inferiores e superiores de~$A$.  Prove que
  \begin{equation}
    \label{eq:3}
    \ldens(A)\leq\lldens(A)\leq\uldens(A)\leq\udens(A). 
  \end{equation}
  \hint{Use soma por partes} \datedue{9/4/2017}

\item{}
  \begin{enumerate}[label=\rmlabel]
  \item Exiba uma sequência~$A=\{a_1<a_1<\dots\}$ de inteiros
    positivos que não tem densidade natural (isto é,
    $\ldens(A)\neq\udens(A)$). 
  \item Exiba uma sequência~$A=\{a_1<a_1<\dots\}$ de inteiros
    positivos que não tem densidade logarítmica (isto é,
    $\lldens(A)\neq\uldens(A)$). 
  \end{enumerate}
  \datedue{2/4/2017}

\item{}Seja~$\cA\subset{[4s]\choose2s}$ um sistema $2$-intersectante
  com~$|\cA|$ o maior possível.  Prove que
  \begin{equation}
    \label{eq:(4s,2s,2)-trivial}
    |\cA|=\({1\over2}-\epsilon(r)\){4s\choose2s}, 
  \end{equation}
  onde~$\lim_{r\to\infty}\epsilon(r)=0$.
  \datedue{9/4/2017}

\item{}Para inteiros~$t\leq n$, ponha
  \begin{equation}
    \label{eq:max_t_inter}
    g(n,t)=\max|\cA|
  \end{equation}
  onde o máximo é tomado sobre todos os~$\cA\subset\cP([n])=2^{[n]}$ que são
  \textit{$t$-intersectantes}, isto é, para todo~$A$ e~$A'\in\cA$,
  temos~$|A\cap A'|\geq t$.
  \begin{enumerate}[label=\rmlabel]
  \item Mostre que~$g(n,1)=2^{n-1}$.
  \item Mostre que, para todo inteiro~$t\geq2$,
    temos~$g(n,t)=(1+o(1))2^{n-1}$.  Isto é, prove que
    $\lim_{n\to\infty}g(n,t)2^{-n+1}=1$.
  \end{enumerate}
  \datedue{9/4/2017}

\item{}Sejam dados uma família $t$-intersectante~$\cA\subset\cP([n])$
  e inteiros~$1\leq i<j\leq n$.  Prove que~$s_{ij}(\cA)$ é
  $t$-intersectante.

\item{}O teorema de Katona sobre famílias $t$-intersectantes
  identifica as famílias que atingem o máximo.  Prove que de fato tais
  famílias são as únicas que atingem a cota do teorema.

\item\label{Q:bip_cover}Suponha que colorimos as arestas do grafo
  completo~$K^n$ com~$k$ cores e~$n>2^k$.  Mostre que há nessa
  coloração um circuito ímpar monocromático.

\item{}Suponha que colorimos as arestas do grafo completo~$K^n$ de
  forma que, para cada vértice~$x$, o número de cores distintas que
  `ocorrem em~$x$' é no máximo~$k$ (uma cor~$c$ \textit{ocorre em~$x$}
  se alguma aresta~$\{x,y\}$ tem cor~$c$).  Prove que se~$n>2^k$,
  então há nessa coloração um circuito ímpar monocromático.  Deduza o
  resultado no Ex.~\ref{Q:bip_cover}.  \hint{Aplique a
    desigualdade em~\eqref{eq:zst}.}  \datedue{16/4/2017}

\item{}Um grafo orientado~$\vec G$ é um grafo~$G$ munido de uma
  orientação de suas arestas.  Assim, dado~$G$, há~$2^{e(G)}$ grafos
  orientados~$\vec G$ associados a~$G$,
  onde~$e(G)=|E(G)|\leq{v(G)\choose2}$ e~$v(G)=|V(G)|$.  Dizemos
  que~$\vec G$ \textit{tem diâmetro}~$2$ se, para
  qualquer~$(x,y)\in V(G)\times V(G)$, há um caminho orientado de
  comprimento no máximo~$2$ de~$x$ para~$y$.  Prove que, para
  todo~$n\geq3$, existe um grafo orientado~$\vec G$ com~$n$ vértices
  e~$O(n\log n)$ arcos (um \textit{arco} é simplesmente uma aresta
  orientada).

\item{}Prove que todo grafo orientado~$\vec G$ com~$n$ vértices e
  diâmetro~$2$ tem pelo menos~$\Omega(n\log n)$ arcos.  Este resultado
  vale para grafos não-orientados?  \hint{Dado~$x\in V(\vec G)$,
    sejam~$N^+(x)=\{y\in V(\vec G)\:\vec{xy}\in E(\vec G)\}$ e
    $N^-(x)=\{y\in V(\vec G)\:\vec{yx}\in E(\vec G)\}$.  Aplique a
    desigualdade em~\eqref{eq:zst}; use a desigualdade de Jensen.}
  \datedue{16/4/2017}

\item{}Seja~$p$ um primo e suponha que~$\cA\subset{[4p]\choose2p}$
  seja tal que~$|A\cap B|\neq p$ para todo~$A$ e~$B\in\cA$ com~$A\neq
  B$.  Prove que
  \begin{equation}
    \label{eq:6}
    |\cA|\leq2\sum_{0\leq j<p}{4p\choose j}.
  \end{equation}
  \datedue{16/4/2017}

\item\label{Q:Borsuk} 
  \begin{enumerate}[label=\rmlabel]
  \item\label{item:Borsuk_i} Seja~$p$ um primo.  Construa um conjunto~$X$ de
    ${4p\choose2p}$ pontos em~$\RR^{4p-1}$ com a seguinte propriedade:
    \textsl{todo~$X'\subset X$ que não contém dois elementos ortogonais é tal
      que
      \begin{equation}
        \label{eq:4}
        |X'|\leq2\sum_{0\leq j<p}{4p\choose j}.
      \end{equation}}\sugestao{Considere vetores com
      coordenadas~$\pm1$ em~$\RR^{4p}$ com 
      o mesmo número de~$+1$s e~$-1$s.}
  \item\label{Q:Borsuk_ii}Use o conjunto~$X$ de~\ref{item:Borsuk_i}
    para construir um conjunto~$Y\subset\RR^d$ que desprova a
    conjectura de Borsuk (em dimensão suficientemente alta),
    onde~$d={4p-1\choose2}$.  \sugestao{Considere a aplicação
      \begin{equation}
        \label{eq:5}
        g\:(a_{ij})_{1\leq i,j\leq4p-1}\mapsto(a_{ij})_{1\leq i<j\leq4p-1},
      \end{equation}
      que leva matrizes $(4p-1)\times(4p-1)$ em matrizes triangulares
      superiores.}  
  \item\label{Q:Borsuk_iii} Seja~$f(d)$ o menor~$t$ tal que
    todo~$S\subset\RR^d$ com~$0<\diam S<\infty$ admite uma
    \textit{particão de Borsuk} em~$t$ partes, isto é, uma partição
    em~$t$ partes tal que cada parte tem diâmetro menor
    que~$\diam(S)$.  Use~\ref{Q:Borsuk_ii} para provar uma cota
    inferior exponencial para~$f(d)$ para todo~$d$ suficientemente
    grande da forma~$d={4p-1\choose2}$, onde~$p$ é um primo.
  \item Deduza a partir de~\ref{Q:Borsuk_iii} uma cota exponencial
    para~$f(d)$ para todo~$d$ suficientemente grande.  \hint{Use o
      teorema dos números primos.}
  \end{enumerate}
  \datedue{16/4/2017}

\item\label{Q:FW_Ramsey}Seja~$p$ um primo e~$n$ um inteiro
  com~$n>2p^2$. Seja~$V=V_{n,p}={[n]\choose p^2-1}$ e~$E=E_{n,p}$ o
  conjunto de arestas~$\{A,B\}$ ($A$, $B\in V$, $A\neq B$)
  com~$|A\cap B|\not\equiv-1\pmod p$.  Seja~$G=G_{n,p}$ o
  grafo~$(V,E)=(V_{n,p},E_{n,p})$.
  Pomos~$h(G)=\max\{\omega(G),\alpha(G)\}$.  Isto é, $h(G)$~é a
  cardinalidade máxima de um conjunto \textit{homogêneo} em~$G$
  (completo ou vazio).  Prove que
  \begin{equation}
    \label{eq:7}
    h(G_{n,p})\leq\sum_{0\leq j<p}{n\choose p-1}\leq2{n\choose p-1}.
  \end{equation}

\item Fixe~$\epsilon>0$.  Para todo~$t$ suficientemente grande, dê uma
  construção explícita de um grafo~$G=G_t$ com pelo menos
  \begin{equation}
    \label{eq:8}
    t^{(1-\epsilon)(\log t)/4\log\log t}
  \end{equation}
  vértices e com~$h(G)\leq t$.  \hint{Escolha~$n=p^3$ no resultado no 
    Ex.~\ref{Q:FW_Ramsey}; use to teorema dos números primos.}

\item\label{ex:20} Seja~$T$ uma árvore com raiz~$r$ e infinitos
  vértices.\footnote{Neste e exercício e nos Exs~\ref{ex:21}
    e~\ref{Ex:22} consideramos grafos infinitos.  Todos os nossos
    grafos são finitos, a menos de menção contrária explícita.}
  Suponha também que~$T$ seja \textit{localmente finito}, isto é, que
  todo vértice de~$T$ tenha grau finito.  Prove que~$T$ tem um caminho
  infinito da forma~$(r,x_1,x_2,\dots)$.

\item\label{ex:21} Seja~$G$ um grafo infinito.  Suponha que os números
  cromáticos dos subgrafos finitos de~$G$ sejam uniformemente
  limitados, isto é, que haja um inteiro~$q$ tal que~$\chi(H)\leq q$
  para todo subgrafo finito~$H$ de~$G$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\chi(G)\leq q$ supondo que~$V(G)$ é enumerável.
    \datedue{25/4/2017} 
  \item Prove que~$\chi(G)\leq q$.  \hint{Use o teorema de Tychonoff.
    Considere~$[q]$ como um espaço topológico discreto e
    considere~$X=\prod_{v\in V(G)}[q]$ com a topologia produto.} 
  \end{enumerate}

\def\og{\mathop{{\rm og}}\nolimits}
\def\vol{\mathop{{\rm vol}}\nolimits}
\item\label{Ex:22} Seja~$d\geq0$ um inteiro e~$\epsilon>0$ um número real.
  Seja~$B(d,\epsilon)$ o grafo infinito com conjunto de
  vértices~$S^d=\{x\in\RR^{d+1}\:\|x\|=1\}$ e conjunto de arestas
  \begin{equation}
    \label{eq:9}
    \big\{\{x,y\}\:x,\,y\in S^d\text{ e
    }\<x,y\>\leq-1+\epsilon\big\}. 
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\chi(B(d,\epsilon))\geq d+2$.
  \item A \textit{cintura ímpar}~$\og(G)$ de um grafo~$G$ é o
    comprimento de um circuito ímpar mais curto em~$G$, isto é,
    \begin{equation}
      \label{eq:10}
      \og(G)=\min\{|V(C)|\:C\text{ circuito de comprimento ímpar
        em }G\}.
    \end{equation}
    Prove que~$\og(B(d,\epsilon))\geq f(\epsilon)$ para alguma
    função~$f$ com~$\lim_{\epsilon\to0}f(\epsilon)=\infty$. 
  \item Podemos medir o `tamanho' de conjuntos~$U$ de vértices
    de~$B(d,\epsilon)$ usando a \textit{medida normalizada}~$\mu(U)$,
    pelo menos para conjuntos~$U$ mensuráveis.  Aqui,
    $\mu(U)=\vol(U)/\vol(S^d)$, onde~$\vol(X)=\vol_d(X)$ denota o
    volume $d$-dimensional de~$X$ ($X\subset S^d$ mensurável).
    Por exemplo, para~$x\in S^d$ e~$0\leq h\leq 2$, seja
    \begin{equation}
      \label{eq:15}
      C_h(x)=\{z\in S^d\:\<z,x\>\geq1-h\}
    \end{equation}
    o \textit{domo esférico} de~$S^d$ centrado em~$x$ e de
    altura~$h$.  Então
    \begin{equation}
      \label{eq:11}
      \mu(C_h(x))=c_d\int_0^{\arccos(1-h)}(\sin\theta)^{d-1}\,d\theta,
    \end{equation}
    onde~$c_d>0$ é uma constante apropriada para
    que~$\mu(C_2(x))=\mu(S^d)=1$ para qualquer~$x\in S^d$.  Podemos
    definir~$\alpha(B(d,\epsilon))=\sup\{\mu(U)\:U\text{ independente
      em }B(d,\epsilon)\}$.
    Prove que~$\alpha(B(d,\epsilon))\geq g(\epsilon)$ para alguma
    função~$g$ com~$\lim_{\epsilon\to0}g(\epsilon)=1/2$.
  \end{enumerate}

\item Sejam~$q$ e~$\ell$ inteiros arbitrários.  Prove que existe um
  grafo finito~$G$ tal que~$\chi(G)\geq q$ e~$\og(G)\geq\ell$.
  \datedue{25/4/2017} 

\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
\item Seja~$G=K(n,k)$ o grafo de Kneser com parâmetros~$n$ e~$k$
  com~$n>2k\geq2$.  Prove que
  \begin{equation}
    \label{eq:11b}
    \og(G)=1+2\llceil{k\over n-2k}\rrceil.
  \end{equation}
  Quanto é a cintura de~$G$?  (A cintura~$g(G)$ de~$G$ é
  $\min\{|V(C)|\:C\text{ circuito em }G\}$.) 

\item Sejam dados~$q$ e~$\ell$ inteiros e~$\epsilon>0$ um número real.
  Prove que existe um grafo~$G$ tal que~$\chi(G)\geq q$,
  $\og(G)\geq\ell$ e~$\alpha(H)\geq(1/2-\epsilon)|V(H)|$ para todo
  subgrafo~$H$ de~$G$.  Qual é o número cromático de um grafo~$G$
  tal que~$\alpha(H)\geq(1/2)|V(H)|$ para todo subgrafo~$H$ de~$G$?
  \datedue{2/5/2017}

\def\val{\mathop{{\rm val}}\nolimits}
\item Seja~$G$ um grafo.
  Seja~$\cI=\cI(G)=\{I\subset V(G)\:I\text{ conjunto independente
    em~$G$}\}$ a família dos conjuntos independentes de vértices
  em~$G$.  Uma \textit{coloração fracionária} de~$G$ é uma função
  não-negativa~$x\:\cI\to\RR$ tal que, para todo~$v\in V(G)$,
  \begin{equation}
    \label{eq:12}
    \sum\{x(I)\:v\in I\in\cI(G)\}\geq1.
  \end{equation}
  Seja~$\val(x)=\sum_{I\in\cI(G)}x(I)$.  O \textit{número cromático
    fracionário}~$\chi_f(G)$ de~$G$ é dado por
  \begin{equation}
    \label{eq:13}
    \chi_f(G)=\min\{\val(x)\:x\text{ coloração fracionária de }G\}. 
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que
    \begin{equation}
      \label{eq:14}
      {|V(G)|\over\alpha(G)}\leq\chi_f(G)\leq\chi(G).
    \end{equation}
  \item Seja~$G=K(n,k)$ o grafo de Kneser com parâmetros~$n$ e~$k$
    com~$n\geq2k\geq2$.  Prove que~$\chi_f(G)=n/k$.
  \end{enumerate}
  \datedue{30/4/2017}

\item Seja~$(\Omega,\PP)$ um espaço de probabilidade em que estão
  definidas~$k$ variáveis independentes $X_1,\dots,X_k$ não
  constantes, isto é, tais que, para todo~$i$ e~$c$,
  temos~$\PP(X_i=c)<1$.  Prove que~$|\Omega|\geq2^k$.
  \datedue{7/5/2017} 

\item Fixe~$n\geq k\geq2$.  Construa~$n$ variáveis aleatórias
  uniformes e $k$-a-$k$ independentes $X_1,\dots,X_n$ não-constantes
  definidas em um espaço de probabilidade~$(\Omega,\PP)$
  com~$|\Omega|\leq(2n)^k$.  \hint{Fixe um primo~$p\geq n$ e
    considere~$\FF_p=\ZZ/p\ZZ$.  Seja~$k=d+1$.
    Seja~$\gamma(t)=(1,\dots,t^d)$ e fixe~$n$ elementos distintos
    $t_1,\dots,t_n\in\FF_p$.  Seja~$X_i=\<\gamma(t_i),Y\>$
    ($1\leq i\leq n$) com~$Y=(Y_j)_{0\leq j\leq d}$ onde~$Y_j$ é
    uniforme e independentemente sorteado de~$\FF_p$.}
  \datedue{7/5/2017} 

\item Seja~$H$ um grafo.  Tome
  \begin{equation}
    \label{eq:16}
    q(H)=\sup\{\chi(G)\:G\text{ grafo sem cópias de~$H$ como subgrafo}\}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$q(H)=\infty$ se~$H$ não é uma floresta (isto é,
    se~$H$ contém circuitos).
  \item Prove que~$q(H)<\infty$ se~$H$ é uma floresta.  Encontre uma
    cota superior explícita para~$q(H)$ neste caso
  \end{enumerate}
  \datedue{14/5/2017}

\item Sejam~$k$ e~$\ell\geq3$ inteiros.  Prove que existe um grafo~$G$
  com~$\chi(G)\geq k$, $g(G)>\ell$ e
  \begin{equation}
    \label{eq:17}
    |V(G)|\leq\big(30(\log\ell)(\log(30k))\ell^2k\big)^\ell.
  \end{equation}
  \hint{Veja as notas de aula de~28/4/2017}  \datedue{14/5/2017}

\item Reescreva a prova de Turán do teorema de Hardy e Ramanujan sobre
  o número de divisores primos distintos de um inteiro sem usar o
  teorema dos números primos.  \hint{Lembre que, para um primo~$p$,
    consideramos~$X_p=\One_{\{p\mid m\}}$.  Se
    $X'=\sum_{p\leq\sqrt{n}}X_p$ e $X=\sum_{p\leq n}X_p$, temos
    $X'\leq X\leq X'+1$.}

\item Seja~$\Omega(m)$ o número de divisores primos de~$m$, contados
  com multiplicidade (de forma que~$\Omega(12)=3$ enquanto
  que~$\omega(12)=2$).  Seja~$\alpha=\alpha(n)$ qualquer função
  com~$\alpha\to\infty$ quando~$n\to\infty$.  Prove que
  \begin{equation}
    \label{eq:18}
    \lim_{n\to\infty}\PP_{m\inU[n]}\(|\Omega(m)-\log\log
    n|\geq\alpha\sqrt{\log\log n}\)=0.  
  \end{equation} \hint{Seja $X_{p^{k}}=\One_{\{p^k\mid m\}}$
    Note que $\Omega(m)=\sum_{p,k}X_{p^{k}}(m)$.  Prove que
    \begin{equation*}
      \sum_{k\geq2,\,p\text{ primo}}{1\over p^k}
      =\sum_p{1\over p(p-1)}<\infty,
    \end{equation*}
    de forma que $\EE_{m\inU}\big(\Omega(m)-\omega(m)\big)=O(1)$ e conclua
    que $\PP_{m\inU[n]}\big(\Omega(m)-\omega(m)\geq\beta(n)\big)=o(1)$ para
    qualquer~$\beta=\beta(n)\to\infty$.}  

\item Fixe~$n$ e suponha~$m\in[n]$.  Seja~$t_*(m)$ um valor real~$t$
  com a seguinte propriedade: 
  \begin{equation}
    \label{eq:19}
    \big|\{p\:p\text{ divisor primo de $m$ com }p\leq t \}\big|
    \geq{1\over2}\omega(m)
  \end{equation}
  e
  \begin{equation}
    \label{eq:20}
    \big|\{p\:p\text{ divisor primo de $m$ com }p\geq t \}\big|
    \geq{1\over2}\omega(m)
  \end{equation}
  Prove que para todo~$\epsilon>0$ existe~$n_0$ tal que vale a
  seguinte afirmação: para todo~$n\geq n_0$, temos que para pelo menos
  $(1-\epsilon)n$ valores de~$m\in[n]$, temos
  \begin{equation}
    \label{eq:21}
    \e^{(\log m)^{1/2-\epsilon}}\leq t_*(m)\leq\e^{(\log m)^{1/2+\epsilon}}.
  \end{equation}
  \hint{Seja~$\omega(m,t)$ o número de divisores primos distintos~$p$
    de~$m$ com~$p\leq t$.  Estude o comportamento típico
    de~$\omega(m,t)$ para~$m\in[n]$.}  \datedue{21/5/2017}

\item Prove que~$p=3^{-n/2}$ é uma função limiar para a propriedade
  de~$\cF=(2^{[n]})_p$ ser uma família de Sperner, isto é, ser tal que
  não há~$A$ e~$B\in\cF$ com~$A\subset B$ e~$A\neq B$.
  \observacao{Lembre que se~$U$ é um conjunto finito
    e~$0\leq p\leq 1$, denotamos por~$U_p$ um subconjunto aleatório
    binomial de~$U$, isto é, $\PP(U_p=T)=p^{|T|}(1-p)^{|U|-|T|}$.
    Como ``ser Sperner'' é uma propriedade decrescente, naturalmente
    queremos provar que se~$p\ll3^{-n/2}$,
    então~$\lim_n\PP(\cF\text{ Sperner})=1$ e se~$p\gg3^{-n/2}$, então
    esse limite é~$0$.}  \datedue{21/5/2017}

\item Tome~$p=3/n$ e considere~$G(n,p)$.  Seja~$X$ o número de
  circuitos hamiltonianos em~$G(n,p)$.  Mostre que~$\EE(X)\to\infty$
  conforme~$n\to\infty$.  Mostre também que~$G(n,p)$ não tem
  circuito hamiltoniano com probabilidade tendendo a~$1$
  conforme~$n\to\infty$.  Repita o mesmo para
  \begin{equation}
    \label{eq:22}
    p={1\over n}(\log n + \log\log n + \alpha),
  \end{equation}
  onde~$\alpha=\alpha(n)$ é uma função arbitrária tal
  que~$\alpha\to-\infty$ conforme~$n\to\infty$.  \datedue{21/5/2017}

\item Se~$A$, $B$ e~$C$ são três pontos em~$\RR^d$, com~$A\neq B$
  e~$A\neq C$, então os vetores~$B-A$ e~$C-A$ definem um
  ângulo~$\theta(A,B,C)$ no ponto~$A$.  Aqui
  consideramos~$\theta(A,B,C)\in[0,\pi]$.  Se~$S\subset\RR^d$
  e~$\theta>0$, dizemos que~$S$ é um \textit{$\theta$-conjunto} se,
  para quaisquer três elementos distintos~$A$, $B$ e~$C$ em~$S$,
  temos~$\theta(A,B,C)\leq\theta$.  Seja dado~$\theta$ e tome
  \begin{equation}
    \label{eq:23}
    f_{\leq\theta}(d)=\max\{|S|\:\text{$S\subset\RR^d$ é um
      $\theta$-conjunto}\}. 
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Determine~$f_{\leq\pi/3}(d)$.
  \item Prove que, para todo~$\epsilon>0$, existe~$\delta>0$ tal que
    \begin{equation}
      \label{eq:24}
      f_{\leq\pi/3+\epsilon}(d)\geq(1+\delta)^d.
    \end{equation}
  \end{enumerate}
  \datedue{28/5/2017}

\item\label{Q:AS} Sejam~$X_1,\dots,X_n$ variáveis aleatórias
  independentes com
  \begin{equation}
    \label{eq:25}
    \PP(X_i=-1)=\PP(X_i=1)={1\over2}
  \end{equation}
  para todo~$i$.  Seja~$S_n=\sum_{1\leq i\leq n}X_i$.  Prove que, para
  qualquer~$a>0$, temos
  \begin{equation}
    \label{eq:27}
    \PP(S_n>a)<\e^{-a^2/2n}.
  \end{equation}
  \hint{Veja, por exemplo, Alon e Spencer~(2000), Apêndice~A.}

\item\label{Q:r.mx} Seja~$A=(a_{ij})$ uma matriz.  Para~$I$ um
  conjunto de linhas de~$A$ e~$J$ um conjunto de colunas de~$A$,
  seja~$s_A(I,J)=\One_I^TA\One_J^{\phantom T}=\sum_{i\in I,\,j\in
    J}a_{ij}$.
  Vamos dizer que~$A$ é \textit{$\alpha$-limitada}
  se~$|s_A(I,J)|\leq\alpha\sqrt{|I||J|}$ para todo~$I$ e~$J$.  Seja~$A$
  uma matriz aleatória $n\times n$ com entradas~$+1$ e~$-1$
  independentes com
  \begin{equation}
    \label{eq:26}
    \PP(a_{ij}=-1)=\PP(a_{ij}=1)={1\over2}
  \end{equation}
  para todo~$i$ e~$j$.  Prove que, com probabilidade tendendo a~$1$
  conforme~$n\to\infty$, a matriz~$A$ é $c\sqrt n$-limitada para
  qualquer constante~$c>2\sqrt{\log 2}$.  \hint{Use o Ex.~\ref{Q:AS}.}
  \datedue{31/5/2017}
  
\item\label{Q:JHL} Dada uma matriz~$B$, vamos denotar aqui a $i$-ésima
  linha de~$B$ por~$B_i$.  Como no Ex.~\ref{Q:r.mx}, para~$I$ um
  conjunto de linhas e~$J$ um conjunto de colunas de~$B=(b_{ij})$,
  seja~$s_B(I,J)=\One_I^TB\One_J^{\phantom T}=\sum_{i\in I,\,j\in
    J}b_{ij}$.
  Seja~$B$ uma matriz $n\times n$ com entradas~$+1$ e~$-1$ cujas
  linhas são ortogonais: $\<B_i,B_{i'}\>=0$ para quaisquer~$i\neq i'$.
  Prove que~$|s_B(I,J)|\leq\sqrt{n|I||J|}$ para
  quaisquer~$I$ e~$J$.  \sugestao{Note que
    $s_B(I,J)=\big\<\sum_{i\in I}B_i,\One_J\big>$ e aplique
    Cauchy--Schwarz.  Para estimar $\|\sum_IB_i\|$, lembre que
    os~$B_i$ são ortogonais.}
  \datedue{4/6/2017}

\item\label{Q:40} Dê uma construção explícita para grafos
  $(\rho,o(1))$-uniformes para alguma constante~$0<\rho<1$.  Mais
  precisamente, dê uma construção explícita de grafos~$G=G^n$
  arbitrariamente grandes que sejam $(\rho,o(1))$-uniformes, isto é,
  que sejam $(\rho,f(n))$-uniformes para alguma função~$f(n)$
  com~$\lim_nf(n)=0$.  \sugestao{Antes de ler esta sugestão, tente
    encontrar uma tal construção explícita seriamente.  Não
    encontrando, continue a ler.  Fixe~$t$ e seja~$n=2^t$.  Considere
    o grafo~$G=G^n$ com conjunto de vértices~$\cP([t])=2^{[t]}$
    definido a seguir.  Se~$x$ e~$y\subset[t]$ são distintos, coloque
    a aresta~$\{x,y\}$ em~$G$ se~$|x\cap y|$ for ímpar.  Prove que~$G$
    é $(1/2,\sqrt n/2)$-bijumbled (para tanto, considere uma
    matriz~$B$ com entradas em~$\{-1,1\}$ adequada, indicando as
    adjacências em~$G$ (as linhas e colunas de~$G$ devem ser indexadas
    por~$V(G)$).  Defina~$B$ de forma que você possa aplicar o
    resultado no Ex.~\ref{Q:JHL}).}  \datedue{7/6/2017}

\item Resolva o Ex.~\ref{Q:40}, mas agora para alguma
  função~$\rho=\rho(n)=o(1)$.  \hint{Fixe um corpo finito~$\FF$.
    Considere $V=\FF^3\setminus\{0\}/\hbox{$\thicksim$}$,
    onde~$\thicksim$ é a relação de equivalência em
    $\FF^3\setminus\{0\}$ em que~$(x_0,x_1,x_2)$ é equivalente
    a~$(x_0',x_1',x_2')$ se e só se
    existe~$\lambda\in\FF\setminus\{0\}$ tal
    que~$(x_0',x_1',x_2')=\lambda(x_0,x_1,x_2)$.  Denote a classe
    de~$(x_0,x_1,x_2)$ por $[x_0,x_1,x_2]$.  Defina o grafo~$G$
    sobre~$V$ declarando dois elementos distintos~$[x_0,x_1,x_2]$
    e~$[x_0',x_1',x_2']$ adjacentes se e só se
    $x_0x_0'+x_1x_1'+x_2x_2'=0$.  Defina uma matriz adequada como na
    sugestão do Ex.~\ref{Q:40} e aplique uma generalização do
    resultado no Ex.~\ref{Q:JHL}, válida para matrizes com linhas
    ortogonais em que as entradas não precisar ser de~$\{-1,1\}$).}
  \datedue{11/6/2017}

\def\uF{{\text F}}
\item Prove a seguinte versão do lema de regularidade de Szemerédi:
  \textsl{Para quaisquer~$\epsilon>0$, $k_0$ e~$r\geq1$,
    existem~$n_0=n_0(\epsilon,k_0,r)$ e~$K=K(\epsilon,k_0,r)$ para os
    quais vale o seguinte.  Sejam~$G_1,\dots,G_r$ grafos quaisquer
    sobre um mesmo conjunto de vértices~$V$ com~$|V|=n\geq n_0$.
    Então existe uma partição de~$V$ com partes~$C_0,\dots,C_k$ que é
    $\epsilon$-balanceada e ainda tal que, para pelo menos
    $(1-\epsilon){k\choose2}$ pares~$(C_i,C_j)$ com~$1\leq i<j\leq k$,
    vale que~$(C_i,C_j)$ é simultaneamente $\epsilon$-regular em
    relação a cada um dos~$r$ grafos~$G_\sigma$
    $(1\leq\sigma\leq r)$.}  (Note que, assim, a partição é
  $\epsilon$-regular em relação a todos os~$G_\sigma$.)  \hint{Use o
    fato que o lema de regularidade pode ser provado exigindo-se que a
    partição resultante seja um refinamento de uma partição dada (isto
    é, de forma que toda classe não excepcional da partição resultante
    esteja contida em alguma parte da partição dada).
    Alternativamente, lembre que na prova que vimos do lema de
    regularidade, usamos a quantidade~$\|A_P\|_\uF^2$ para mostrar que
    um certo processo de refinamento sucessivo termina com uma
    partição regular do grafo dado (a quantidade~$\|A_P\|_\uF^2$ é
    também conhecida como o \textit{índice} da partição~$P$).  Sendo
    dados~$r$ grafos~$G_1,\dots,G_r$, use a quantidade
    $\|A_1\|_\uF^2+\dots+\|A_r\|_\uF^2$, onde~$A_\sigma$ é a matriz de
    adjacência de~$G_\sigma$.}

\item Sejam dados grafos~$G$ e~$H_1,\dots,H_r$.
  Escrevemos~$G\indarrow(H_1,\dots,H_r)$ se vale o seguinte: para
  qualquer coloração das arestas de~$G$ com cores~$1,\dots,r$, para
  algum~$1\leq i\leq r$, um subgrafo induzido~$H$ de~$G$ isomorfo
  a~$H_i$ tem todas suas arestas coloridas com a
  cor~$i$.\footnote{Isto é, existe~$U\subset V(G)$ tal que o
    subgrafo~$H=G[U]=(U,{U\choose2}\cap E(G))$ induzido por~$U$ em~$G$
    é isomorfo a~$H_i$ e todas as arestas em~${U\choose2}\cap E(G)$
    estão coloridas com a cor~$i$.}  Prove que, para quaisquer~$r$
  grafos~$H_1,\dots,H_r$, existe um grafo~$G$ tal
  que~$G\indarrow(H_1,\dots,H_r)$.  \sugestao{Tome para~$G$ o grafo
    aleatório~$G(n,1/2)$.  Use o lema de regularidade de Szemerédi, o
    teorema de Turán, o teorema de Ramsey, e use um lema da imersão
    adequado.}  \datedue{22/6/2017}

\end{enumerate}  

\endgroup
\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% eval: (flyspell-mode t)
%%% TeX-master: t
%%% End:
