Ensino Superior ⇒ Teoria dos Grafos Tópico resolvido

[danmat]

Olá pessoal,

Observe as definições a seguir:

Definição 1. Dado um conjunto [tex3][n] = \{1,2,3,...,n\}[/tex3] , cada combinação de [tex3]k[/tex3] elementos de [tex3][n][/tex3] é chamado de vértice e denotado por [tex3]v[/tex3].

Definição 2. Um conjunto [tex3]I[/tex3] de vértices é chamado indepedente se [tex3]\forall u,v \in I, u \cap v \neq \emptyset[/tex3].

Definição 3. Um conjunto independente [tex3]I[/tex3] é do [tex3]Tipo \ 1[/tex3], se todos os seus vértices possuem um mesmo elemento em comum.

Teorema 1. [Erdös-Ko-Rado] Se [tex3]I[/tex3] é um conjunto independente, então sua cardinalidade máxima é igual a [tex3]\binom{n-1}{k-1}[/tex3].

O que preciso provar é

Proposição 1. Se um conjunto indepedente [tex3]I[/tex3] tem cardinalidade máxima, então ele é do [tex3]Tipo \ 1[/tex3].

Estou trabalhando nesta questão há algum tempo, já tentei abordá-la utilizando matemática discreta, álgebra linear e álgebra, mas em todos os casos sem sucesso. No momento estou tentando utilizar alguns conceitos de topologia combinatória para resolvê-lo, entretanto meu conhecimento nesse campo ainda é muito pequeno e não consegui nenhuma evolução significativa.

Será que alguém consegue me dar uma ajuda?

Muito obrigado!

[Cássio]

Olá danmat.

Eu só estudei o básico sobre grafos, coisas como grafos conexos e etc e, nem me lembro. Mas apenas pelas definições que deu fiquei pensando no problema.

Eu não vi a demonstração do teorema 1, mas acredito que usa apenas argumentos combinatórios básicos. Eu pensei o seguinte:

Dado um conjunto [tex3][n]=\{1,2,3,...,n\}[/tex3], uma combinação de [tex3]k[/tex3] elementos é apenas um dos subconjuntos com [tex3]k[/tex3] elementos, onde não consideraremos que [tex3]\emptyset[/tex3] não está contido nesses subconjuntos. Então minha ideia pra provar o teorema 1, é notar que para máximizar a quantidade de combinações de um conjunto independente, essas combinações devem ter apenas um elemento em comum.

De fato, se tivermos apenas um elemento em comum entre todas as combinações (subconjuntos), temos apenas que escolher os outros [tex3]k-1[/tex3] elementos entre [tex3]n-1[/tex3] elementos, pois já usamos 1 elemento que será repetido. Sabemos que isso pode ser feito de [tex3]\dbinom{n-1} {k-1}.[/tex3]

----------------------------------------------------------------------------------------------------------------------------------------------------------------

Minha ideia para provar a sua proposição, é mostrar que se um conjunto não é do tipo 1, então a cardinalidade máxima dele é menor que [tex3]\dbinom{n-1} {k-1}.[/tex3] Mas antes eu gostaria de saber se na definição 3, o certo seria:

Definição 3. Um conjunto independente é do tipo 1, se todos os seus vértices possuem SOMENTE um elemento em comum.

Se for isso, veja o que pensei:

Suponha que um conjunto independente seja de um tipo maior que 1, ou seja, todos seus elementos tem mais de um elemento em comum. Digamos, de tipo [tex3]t>1.[/tex3]

Usando o mesmo raciocínio da prova do teorema 1, vamos contar quantas combinações, no máximo, existem. Vamos supor que os [tex3]t[/tex3] elementos em comum já estejam definidos. Para formar cada um dos subconjuntos (combinações-vértices) com [tex3]k[/tex3] elementos, temos apenas que escolher os outros [tex3]k-t[/tex3] elementos entre [tex3]n-t[/tex3] elementos. Isso, como sabemos, pode ser feito de [tex3]\dbinom{n-t}{k-t}[/tex3] maneiras.

Veja nossa conclusão: se um conjunto independente for do tipo [tex3]t>1,[/tex3] sua cardinalidade máxima é [tex3]\dbinom{n-t}{k-t}[/tex3] e o que eu quero provar é que essa cardinalidade é menor que [tex3]\dbinom{n-1}{k-1}.[/tex3] Mas isso é o mesmo que provar que

[tex3]\dbinom{n-t}{k-t}<\dbinom{n-1}{k-1},\ \forall\ t>1.[/tex3]

Ao invés de trabalhar com esses sinais de subtração, vamos fazer [tex3]x=n-t,\ y=k-t[/tex3] e [tex3]m=t-1.[/tex3] Então temos que provar que [tex3]\dbinom{x}{y}<\dbinom{x+m}{y+m},\ \forall\ m>0.[/tex3]

Mas veja que:
[tex3]\dbinom{x+m}{y+m}=\dfrac{(x+m)!}{(x+m-y-m)!(y+m)!}=\dfrac{x!(x+1)(x+2)\cdots (x+m)}{(x-y)!y!(y+1)\cdots(y+m)}=\dbinom{x}{y}\dfrac{(x+1)\cdots(x+m)}{(y+1)\cdots(y+m)}[/tex3]. Pela própria definição do Binômio de Newton, temos que [tex3]x\ge y\Rightarrow (x+1)\cdots(x+m)\ge (y+1)\cdots(y+m)[/tex3] (vamos considerar aqui, [tex3]x>y[/tex3]. Vou explicar mais na frente o porque, o que nos leva a [tex3](x+1)\cdots(x+m)>(y+1)\cdots(y+m)[/tex3] )

[tex3]\Rightarrow \dfrac{(x+1)\cdots(x+m)}{(y+1)\cdots(y+m)}>1[/tex3]

e portanto, [tex3]\dbinom{x+m}{y+m}>\dbinom{x}{y}[/tex3]

ou seja, [tex3]\dbinom{n-1}{k-1}>\dbinom{n-t}{k-t},\ \forall\ t>1.[/tex3]

( Minha dúvida na definição, é o que acontece quando [tex3]k=1[/tex3] ou [tex3]k=n.[/tex3] Se [tex3]1<k<n,[/tex3] a desigualdade que enunciei é verdadeira, e talvez sirva pra provar a proposição. Só estou com dificuldades no entendimento do caso [tex3]k=1[/tex3] ou [tex3]k=n,[/tex3] porque aí a cardinalidade é 1... Se puder esclarecer esse ponto, talvez fique provado a proposição.)



Abraço. E desculpe se falei besteira aí acima rsrs.

[danmat]

Olá Cássio,

Primeiramente, muito obrigado por sua atenção. Eu concordo com sua argumentação, mas o que ela prova, na realidade é:

Seja [tex3]I[/tex3] um conjunto independente, tal que [tex3]|I| = p[/tex3] e [tex3]|\bigcap_{i = 1}^{p} v_i| = t[/tex3], com [tex3]v_i \in I, 1 \leq i \leq p[/tex3]. Se [tex3]t > 1[/tex3], então [tex3]p < \binom{n-1}{k-1}[/tex3].

Concorda? Sobre a definição 3

Definição 3. Um conjunto independente [tex3]I[/tex3] é do [tex3]Tipo \ 1[/tex3], se todos os seus vértices possuem SOMENTE um elemento em comum.

Ou ainda

Definição 3. Um conjunto independente [tex3]I[/tex3] é do [tex3]Tipo \ 1[/tex3], se [tex3]\bigcap_{i=1}^{p} v_i = \{a\}, v_i \in I[/tex3].

Ou seja, basta existirem [tex3]v_i, v_j, v_l \in I[/tex3],tais que [tex3]a \in v_i \cap v_j[/tex3] e [tex3]a \notin v_i \cap v_l[/tex3] para [tex3]I[/tex3] não ser [tex3]Tipo \ 1[/tex3].

Correto? Agora a proposição

Proposição 1. Se um conjunto indepedente [tex3]I[/tex3] tem cardinalidade máxima, então ele é do [tex3]Tipo \ 1[/tex3].

Um contra-exemplo (ou uma hipótese para prova-la por redução ao absurdo) seria

[tex3]I[/tex3] tem cardinalidade máxima e ele não é do [tex3]Tipo \ 1[/tex3], ou seja, existem [tex3]v_i, v_j, v_l \in I[/tex3],tais que [tex3]a \in v_i \cap v_j[/tex3] e [tex3]a \notin v_i \cap v_l[/tex3].

Sem perda de generalidade, suponhamos [tex3]k = 3, n \geq 7[/tex3], dessa forma se [tex3]v_1 = \{a_1,a_2,a_3\}, v_2 = \{a_1,a_2,a_4\}, v_3 = \{a_2,a_3,a_4\}, a_i \in [n][/tex3], logo [tex3]v_1 \cap v_2 = \{a_1,a_2\}, v_1 \cap v_3 = \{a_2,a_3\}[/tex3], então existe [tex3]\{a\} \in v_1 \cap v_2[/tex3] e [tex3]\{a\} \notin v_1 \cap v_3[/tex3], portanto não consigo construir um conjunto independente que contenha os elementos [tex3]v_1, v_2, v_3[/tex3] com cardinalidade máxima.

Para [tex3]n \geq 5, k = 2[/tex3], é fácil provar a validade da proposição, pois sem perda de generalidade

[tex3]\{a_1,a_2\}, \{a_1,a_3\}, \{a_2,a_3\} \in I, a_i \in [n] \Rightarrow v \in I \Leftrightarrow \{a_1\} \in v[/tex3] e [tex3]\{a_2\} \in v[/tex3] ou [tex3]\{a_1\} \in v[/tex3] e [tex3]\{a_3\} \in v[/tex3] ou [tex3]\{a_2\} \in v[/tex3] e [tex3]\{a_3\} \in v[/tex3], mas estes são exatamente os vértices que pertencem ao conjunto [tex3]I[/tex3], portanto não é possível acrescentar nenhum outro vértice em [tex3]I[/tex3], disso decorre que só é possível construir um conjunto independente de cardinalidade máxima quando [tex3]n \geq 5,k = 2[/tex3] se [tex3]I[/tex3] for do [tex3]Tipo \ 1[/tex3].

Consegui ser claro? E a propósito estou interessado somente em valores [tex3]1 < k < \frac{n}{2}[/tex3]. O que acha disto?

[Cássio]

Olá danmat.

[tex3]\ldots|I|=p\ldots[/tex3] esse [tex3]p[/tex3] não é a cardinalidade do conjunto [tex3]I[/tex3]? E o que impede, evetualmente, que ele seja o maior [tex3]p[/tex3] possível, ou seja, a cardinalidade máxima?


Vou explicar como abordei o problema. Vou esquecer que é teoria dos grafos e abordar como um problema comum de combinatória:

1. Dado um conjunto de inteiros [tex3][n]=\{1,2,...,n\}[/tex3] e um [tex3]k\in\mathbb{N},[/tex3] um vértice é uma das combinações de [tex3]k[/tex3] elementos tomados de [tex3][n].[/tex3]

2. Um conjunto independente é uma conjunto formado por elementos que são combinações de [tex3]k[/tex3] elementos tomados de [tex3][n].[/tex3] ( Não necessariamente todas as combinações?)

3. Um conjunto independente é do tipo 1, quando todas essas combinações possuem um, e somente um elemento em comum.

Teorema: Todo conjunto independente tem no máximo [tex3]\dbinom{n-1}{k-1}[/tex3] elementos, ou seja, existem no máximo [tex3]\dbinom{n-1}{k-1}[/tex3] combinações, onde todas combinações possuem somente um elemento em comum.

------------------------------------------

A minha interpretação da proposição que você fez foi a seguinte: Se eu tenho [tex3]\dbinom{n-1}{k-1}[/tex3] combinações de [tex3]k[/tex3] elementos tomados de [tex3][n][/tex3], então todos as combinações só podem possuir 1, e somente 1 elemento em comum.
Daí pensei numa ideia comum: Se [tex3]a=b[/tex3] ou [tex3]a=c,[/tex3] E, [tex3]a[/tex3] não pode ser igual a [tex3]b,[/tex3] então ocorre somente [tex3]a=c.[/tex3] Em outras palavras, todo conjunto independente é do [tex3]tipo\ 1[/tex3] ou de algum tipo maior que 1. Se ele não for do tipo maior que 1, só pode ser do tipo 1.

Daí, a pergunta que fiz foi: Qual o número máximo de combinações de [tex3]k[/tex3] elementos tomados de [tex3][n][/tex3], onde todos as combinações possuem [tex3]t>1[/tex3] elementos em comum? Daí seguiu todas as contas que fiz.



Pode me dizer se as formas de abordar podem ser ditas "equivalentes"?

[danmat]

Olá Cássio,

Eu concordo plenamente com seus argumentos. Mas observe esta afirmação:

todo conjunto independente é do [tex3]Tipo\ 1[/tex3] ou de algum tipo maior que 1. Se ele não for do tipo maior que 1, só pode ser do tipo 1.

Esse "tipo maior do que 1", pelo o que entendi, seria

Um conjunto independente é do tipo 2, quando todas essas combinações possuem dois, e somente dois elementos em comum.
...
Um conjunto independente é do tipo t, quando todas essas combinações possuem t, e somente t elementos em comum.

Correto? Daí, novamente, eu concordo totalmente com a forma que você abordou o problema... Entretanto, sob esse olhar, o problema não está quando o conjunto é do [tex3]Tipo \ t, t > 1[/tex3], mas sim quando o conjunto é do [tex3]Tipo \ 0[/tex3] ou seja

[tex3]\bigcap_{i=1}^{p} v_i = \emptyset, v_i \in I, |I| = p[/tex3].

De outra forma, não consigo construir um conjunto do Tipo 0 com cardinalidade máxima.

Veja um exemplo, para [tex3]n = 7 , k = 3[/tex3]

[tex3]I = \{\{1,2,3\}, \{1,2,4\}, \{2,5,6\}, \{3,4,6\}\}[/tex3]

Esse conjunto [tex3]I[/tex3] é do Tipo 0, pois

[tex3]\bigcap_{i=1}^{4} v_i = \{1,2,3\} \cap \{1,2,4\} \cap \{2,5,6\} \cap \{3,4,6\} = \emptyset[/tex3]. Se a proposição é falsa, então eu consigo adicionar subconjuntos em [tex3]I[/tex3] até que sua cardinalidade se torne a máxima.

Concorda?

[Cássio]

Olá, novamente, danmat.

Você entendeu perfeitamente as minhas definições: é do Tipo 1 quando todos elementos possuem somente 1 elemento em comum

- Tipo 2 quando possuem exatamente 2 elementos em comum
...



-----------------------------------------

Bom, pensando sobre o caso Tipo 0, notei que o resultado talvez não bata com sua proposição. O que penso é o seguinte:

Se considerarmos todas as combinações com [tex3]1<k<n[/tex3] elementos tomados de [tex3][n],[/tex3] a interseção entre todos eles é simplesmente vazia. É simples perceber isso: uma das combinações é [tex3]\{1,2,...,k\}[/tex3] e essa combinação não contém o elemento [tex3]n.[/tex3] Portanto, [tex3]n[/tex3] não pode ser a interseção entre todas as combinações.
Uma outra combinação é [tex3]\{2,3,...,k+1\}[/tex3], que não contém o elemento [tex3]1,[/tex3] portanto, o 1 não pode ser a interseção entre todas as combinações.
Analogamente, temos a combinação [tex3]\{1,2,4,...,k+1\}[/tex3] que não contém o elemento 3.
De modo geral, para qualquer [tex3]1\le x\le n[/tex3], o elemento [tex3]x[/tex3] não pode ser a interseção entre todos as combinações, pois sempre existe a combinação [tex3]\{1,2,...,x-1,x+1,...,k+1\},[/tex3] que não contém o elemento [tex3]x.[/tex3]

Mas sabemos que o número de combinações de [tex3]k[/tex3] elemento tomados de [tex3][n][/tex3] é [tex3]\dbinom{n}{k},[/tex3] que já vimos que [tex3]\dbinom{n}{k}>\dbinom{n-1}{k-1}.[/tex3]

Minha pergunta agora, é se a definição cobre os conjuntos do Tipo 0. Se a definição não seria apenas para os conjuntos de tipo maior que 0.
-----------------------------------------------------------------------------------------------------

A propósito, quando considerou um caso particular como [tex3]n=7,\ k=3,[/tex3] acho que ficou faltando combinações. Vou considerar um caso menor: [tex3]n=4,\ k=3.[/tex3]

[tex3]I=\{\{1,2,3\},\{1,2,4\}, \{1,3,4\}, \{2,3,4\}\},[/tex3] que é o máximo de combinações que podemos fazer e perceba que a interseção entre todas elas é vazia. A cardinalidade desse conjunto é [tex3]|I|=\dbinom{4}{3}=4,[/tex3] que bate com o raciocínio que falei acima.


Abraço.

[danmat]

Olá Cássio,

Agora sim nos entendemos! rsrs Primeiramente, quanto ao caso [tex3]n =7, k = 3[/tex3] eu construi um conjunto [tex3]I[/tex3] com algumas das combinações de 3 elementos tomadas de conjunto com 7 elementos, mas não foram todas as combinações que seriam um total de 35.... Enfim...

Deixa eu te contextualizar no que estou trabalhando: em 1955 foi conjecturado por Martin Kneser o seguinte

"Se particionarmos os k-subconjuntos de um conjunto de n elementos em n–2k+1 classes, uma das classes conterá k-subconjuntos disjuntos".

Essa conjectura foi provada em 1978 por Lásló Lovász, sendo que essa prova deu origem a um novo campo matemático chamado Topologia Combinatória. Uma característica interessante na prova de Lovász foi ele ter traduzido esse problema para Teoria dos Grafos, dando origem a uma família de grafos chamada Grafos de Kneser. A prova desta conjectura resolveu o problema de determinar o menor número de cores necessárias para fazermos uma coloração de vértices nessa família de grafos, como você já estudou grafos você deve se lembrar que os grandes problemas em grafos são determinar o número mínimo de cores para uma coloração de vértices ou arestas, determinar se o grafo é hamiltoniano, etc. Por muito tempo tentou-se estabelecer uma prova puramente combinatória dessa conjectura e em 2004 um tcheco chamado Jiri Matousek conseguiu este feito.

A questão é que a prova dele não é nada trivial, este foi o tema de um projeto de IC que participei nos últimos 2 anos. Estudando as propriedades dos grafos de Kneser percebi uma estratégia para fazer uma prova desta conjectura, puramente combinatória, bem mais simples do que a prova referida. Mas para isso, preciso antes resolver este probleminha que apareceu no caminho.

Pelo fato de a conjectura ter sido provada, garante que a Proposição 1 é verdadeira, pois caso contrário conseguiriamos contra-exemplos para a conjectura... Mas, eu não posso usar este resultado para prová-la, pois estaria usando o teorema que quero provar para prová-lo... Vou continuar nessa tarefa... Se você se interessar pesquise sobre esse assunto, pois você terá contato com boa matemática!