Subsequências monotônicas

Toda sequência de $n^2$ números distintos possui uma subsequência monotônica com $n$ elementos.

Onde monotônica quer dizer crescente ou decrescente. Em outras palavras, dada uma sequência $a_1, a_2, a_3,\ldots a_{n^2}$, buscamos um conjunto de $I\subseteq [n^2]$ de $n$ índices tal que a subsequência $\langle a_i\rangle_{i\in I}$ é crescente ou decrescente.

Note que $n<3$ não é muito interessante.

Vamos ver o que acontece quando temos uma sequência com 9 elementos. Há 362880 possíveis ordenações, então uma análise caso a caso não parece óbvia.

O que você acha? Como resolveria o problema?

Decomposição em grafos bipartidos completos aresta-disjuntos

Decomposição de um grafo

Uma decomposição de um grafo \(G\) em grafos aresta-disjuntos consiste em encontrar subgrafos \(H_1,H_2,\ldots,H_k\) de \(G\) tais que cada aresta de \(G\) pertence a exatamente um deles. Em símbolos, temos

• \(\bigcup_{i=1}^k E(H_i)=E(G)\); e
• \(E(H_i)\cap E(H_j)=\emptyset\), para \(i\neq j\).

Decomposição em grafos bipartidos completos

Seja \(\tau(G)\) o número mínimo de subgrafos de \(G\) que são bipartidos completos, aresta-disjuntos, e que formam uma decomposição de \(G\).

A pergunta do dia é motivada pelo resumo (abstract) do artigo de Alon: mostre que\(|E(G)|\leq \tau(G)\leq |V(G)| - \alpha(G)\), onde \(\alpha(G)\) é o maior tamanho de um conjunto de vértices \(S\) tal que nenhuma aresta de \(G\) conecta vértices de \(S\).

Exercício de probabilidade

O problema

Sejam \(a,b\in]0,1[\) dois números reais entre zero e um. Queremos construir uma moeda que dê cara com probabilidade \(p\) proporcional a \(a\) e coroa com probabilidade proporcional a \(b\). Quanto vale \(p\)?

Solução

Queremos \(p=ac_1\) e \(1-p=bc_2\), onde \(c_1\) e \(c_2\) são constantes positivas que usamos para definir a “proporção”. Dividindo as expressões, obtemos \[\frac{p}{1-p} = \frac{ac_1}{bc_2}\implies p =\frac{ac_1}{ac_1+bc_2}.\]

Grafos sem \(C_4\)

Quantas arestas pode ter um grafo sem que ele contenha um circuito com quatro vértices (\(C_4\))?

Spoiler alert! Vale a pena pensar neste problema antes de ler a discussão abaixo.

Um \(C_4\) é o grafo conexo com 4 vértices, cada um com dois vizinhos. Num grafo sem \(C_4\), cada par de vértices tem no máximo um vizinho comum. Considere o grafo formado por \(k\) cópias de \(K_2\) (grafo completo com dois vértices), em que acrescentamos um vértice novo \(v\) e arestas ligando cada um dos demais vértices a \(v\). Esse grafo é tal que qualquer par de vértices possui um vizinho em comum, e possui \(3k\) arestas.

Outro comentário: num grafo em que cada par de vértices possui um vizinho comum, qualquer nova aresta gera um \(C_4\). (e, se há ao menos 5 vértices, um \(C_5\) também).

Pergunta: o número de arestas de um grafo \(G\) com \(n\) vértices e tal que todo par de vértices possui exatamente um vizinho em comum é único para cada \(n\) fixo?

Para pensar: seja \(G\) um grafo livre de \(C_4\) que possui vértices \(u\) e \(v\) sem vizinhança comum — isto é, \(N(u)\cap N(v)=\varnothing\). É possível que ele seja máximo (no número de arestas)? Em outras palavras, estamos certos de que não existe grafo com mais arestas do que \(G\) e que seja livre de \(C_4\)?

Tamanho importa

Valores Assintóticos

Que número é maior: \(\binom{n}{3}\) ou \(n^2\)?

Nem sempre conseguimos valores exatos em uma contagem. E nem sempre expressões exatas são tão informativas assim.

Responda rápido: existem mais subconjuntos de 3 elementos ou pares ordenados em um conjunto?

Uma estimativa útil (para \(n\) suficientemente grande…): \[\left(\frac{n}{k}\right)^k\leq \binom{n}{k}\leq\left(\frac{en}{k}\right)^k.\]

Pergunta: escolhemos uniformemente ao acaso um grafo (rotulado) com 30 vértices, e contamos o número de circuitos com 5 vértices. Quantos ciclos esperamos encontrar?

Eventos e variáveis aleatórias (espaços finitos)

Vamos definir alguns conceitos…

Seja \(S\) um conjunto finito. Uma medida de probabilidade sobre \(S\) é uma função \(\mu\colon 2^S\to[0,1]\) que satisfaz as seguintes condições

• para todo subconjunto \(A\subseteq S\), temos \(0\leq\mu(A)\leq 1\);
• se \(A\) e \(B\) são subconjuntos disjuntos de \(S\), então \(\mu(A \cup B) = \mu(A) +\mu(B)\);
• \(\mu(S)=1\).

Vamos chamar \(S\) de espaço amostral, ou espaço de probabilidade (deixando \(\mu\) subentendido). Um evento é qualquer subconjunto de \(S\). Assim, se nosso espaço consiste dos possíveis números obtidos ao lançar um dado comum, exemplos de eventos são "tirar 6" ou "tirar um número ímpar".

Note que \(\mu\) nada mais é do que uma atribuição de pesos aos subconjuntos de \(S\), normalizados no intervalo \([0,1]\). Uma maneira de interpretar \(\mu\) é como a "representatividade" dos eventos. Quanto maior o valor de \(\mu(A)\), mais "típicos" são os elementos de \(A\).

Variáveis aleatórias

A probabilidade de um evento está longe de ser a única coisa estudada em probabilidade. Por exemplo, podemos nos perguntar qual o "comportamento típico" de alguma característica dos pontos do espaço de probabilidade. Para isso, é interessante introduzir valores para os diferentes pontos de \(S\).

Uma variável aleatória é uma função \(X\colon S\to\mathbb{R}\) que leva subconjuntos de \(S\) em números reais. Note que usando variáveis aleatórias, temos um meio de formular diversas questões interessantes. Qual o valor mais comum da variável aleatória? Qual a probabilidade de \(X\) encontrar-se em um dado intervalo? Que valores são improváveis? E assim por diante.

Notação — conjuntos

Notação é coisa que "vareia". Não encontrei modo simples de acrescentar uma página estática no blog, para falar de notação, sem com isso perder o MathJax que nos dá essas belas equações. Então simplesmente recortei o texto que ia por lá e estou jogando aqui (leia-se: espere revisões e mais revisões deste post).

Conjuntos

Acredito que boa parte da notação que usamos aqui seja largamente adotada. Em geral letras maiúsculas \(A,B,C,\ldots\) denotam conjuntos, \(|A|\) para denotar a cardinalidade de \(A\). Usamos \(2^A\) para o conjunto das partes de \(A\) (isto é, a família de todos os subconjuntos de \(A\)), e \(\binom{A}{k}\) para a família de subconjuntos de \(A\) com exatamente \(k\) elementos \(\binom{A}{k}=\{ a\subset A\colon |a|=k\}\). Para um número natural \(n\), escrevemos \([n]=\{1,2,\ldots,n\}\).