Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:perfectgraphs [2023/06/22 16:25] – piva
+++ grafos:perfectgraphs [2023/06/22 17:07] (atual) – edição externa 127.0.0.1
@@ Linha 230: / Linha 230: @@
 Observe que se $K$ é o conjunto de vértices de qualquer $K^{\omega}$ em $G$, então
-$$K \cap A_i = \emptyset para exatamente um i \in \{0,\dots, \alpha \omega\}. \qquad (4)$$
+$$K \cap A_i = \emptyset, \qquad (4)$$
+para exatamente um $i \in \{0,\dots, \alpha \omega\}$. De fato, se $K \cap A_0 = \emptyset$ então $K \cap A_i \neq \emptyset$ para todo $i \neq 0$, por definição de $A_i$ e $(2)$. Similarmente se $K \cap A_0 \neq \emptyset$, então $|K \cap A_0| = 1$, então $K \cap A_i = \emptyset$ para exatamente um $i \neq 0$: aplique $(3)$ ao único vértice $u \in K \cap A_0$ e $(2)$ a todos os outros vértices $u \in A_0$.
-De fato, se K então K para todo K, por definição de K e 2. Similarmente se K , então K , então K para exatamente um K; aplique 3 ao único vértice K e 2 a todos os outros vértices K.
+Seja $J$ a matriz real $(\alpha \omega +1) \times (\alpha \omega +1)$ com zero entradas na diagonal principal e todas as outras entradas $1$. Seja $A = (a_{ij})$ a matriz real $(\alpha \omega +1) \times n$ cujas linhas são os vetores de incidência dos conjuntos $A_i$ com $V(G)$: onde $a_{ij} = 1$, se $v_j \in A_i$, e $a_{ij} = 0$ caso contrário. Da mesma forma, seja $B$ denotando a matriz real $n \times (\alpha \omega +1)$ cujas colunas são os vetores de incidência dos conjuntos $K_j$ com $V(G)$. Agora, enquanto $|A_i \cap K_i| = 0$ para todo $i$ pela escolha de $K_i$, temos $A_i \cap K_j \neq \emptyset$ e, portanto, $A_i \cap K_j = 1$ sempre que $i \neq j$, por $(4)$. Assim,
-Seja J a matriz K real com zero entradas na diagonal principal e todas as outras entradas 1. Seja K a matriz K real cujas linhas são os vetores de incidência dos conjuntos K com V: onde K, e K caso contrário. Da mesma forma, seja B denotando a matriz K real cujas colunas são os vetores de incidência dos conjuntos K com V. Agora, enquanto K para todo J pela escolha de K, temos K e, portanto, K sempre que K, por 4. Assim, B. Como J não é singular , isso implica que K tem classificação K. Em particular, K, que contradiz (*) para H.
+$$AB = J.$$
+Como $J$ não é singular, isso implica que $A$ tem classificação $\alpha \omega +1$. Em particular, $n \geq \alpha \omega +1$, que contradiz $(*)$ para $H := G$.
 </WRAP>
 ----
-Pelo teorema 5.2.5, não podemos forçar um subgrafo K , mesmo para K, tornando o número cromático de um grafo suficientemente grande. No entanto, isso pode ser possível para gráficos com certas propriedades especificadas, que podem, por sua vez, dar alguma importância a essas propriedades que, de outra forma, não teriam. Por exemplo, os grafos sem buraco ímpar ou antiburaco parecem uma classe estranha para estudar. Mas o fato de que, pelo teorema do grafo perfeito forte, grafos de número cromático K nesta classe possuem K subgrafos, torna-os interessantes: alto número cromático, para grafos desta classe, sempre terá uma razão local.
+Pelo [[grafos:teoerdos#teorema_erdos|teorema]], não podemos forçar um subgrafo $K^r$ , mesmo para $r = 3$, tornando o número cromático de um grafo suficientemente grande. No entanto, isso pode ser possível para grafos com certas propriedades especificadas, que podem, por sua vez, dar alguma importância a essas propriedades que, de outra forma, não teriam. Por exemplo, os grafos sem buraco ou antiburaco ímpar parecem uma classe ímpar para estudar. Mas o fato de que, pelo teorema do grafo perfeito forte, grafos de número cromático $k$ nesta classe possuem $K^k$ subgrafos, torna-os interessantes: alto número cromático, para grafos desta classe, sempre terá uma razão local.
-De forma um pouco mais geral, uma classe G de grafos é chamada limitada por X se existe uma função F tal que X para cada grafo G em G. Em tais grafos, então, podemos forçar um subgrafo K tornando X maior que F.
+De forma um pouco mais geral, uma classe $\mathcal{G}$ de grafos é chamada $\chi$-limitada se existe uma função $f: \mathbb{n} \to \mathbb{N}$ tal que $\chi (G) \leq f(r)$ para cada grafo $G \supsetneq K^r$ em $\mathcal{G}$. Em tais grafos, então, podemos forçar um subgrafo $K^r$ tornando $\chi$ maior que $f(r)$.
-Teorem 5.5.7
+<WRAP round box 100%>
+=== Teorema ===
-(i) O gráfico sem buracos ímpares é limitado por X com F.
+$(i)$ //O gráfico sem buracos ímpares é $\chi$-limitado com $f( r ) = 2^{2^{r+1}}$.//
-(ii) Para cada inteiro K, o grafo sem furos de comprimento K são limitados por X.
+$(ii)$ //Para cada inteiro $\ell$, o grafo sem buracos de comprimento $> \ell$ são $\chi$-limitados.//
+</WRAP>
 ----
-a questão óbvia que isso levanta é o que podemos dizer se ambas as condições forem combinadas: dado K, os gráficos sem buraco ímpar de comprimento K ainda são X limitados? esta é certamente uma velha conjectura de Gýarfás, que motivou o Teorema 5.5.7.
+A questão óbvia que isso levanta é o que podemos dizer se ambas as condições forem combinadas: dado $\ell$, os grafos sem buraco ímpar de comprimento $> \ell$ ainda são $\chi$-limitados? Esta é certamente uma velha conjectura de Gýarfás, que motivou o Teorema logo acima.