Números extremais de ciclos

Dados os grafos \(G\) e \(H\), dizemos que \(G\) é $H$-livre se \(H\) não é um subgrafo de \(G\). O maior número de arestas em um grafo $H$-livre de \(n\) vértices, denotado por \(ex(n, H)\), é chamado de número extremal de \(H\). Mais formalmente, definimos

\begin{equation} ex(n, H) = \max \{e(G) \colon v(G) = n, G \textrm{ é } H\textrm{-livre}\} \end{equation}

Vamos denotar o ciclo de \(k\) vértices por \(C_k\).

O objetivo desse post é provar o seguinte teorema.

Teorema 1

Para todo \(k \geq 3\) e \(n \in \mathbb{N}\) suficientemente grande, temos que \[ex(n, C_k) \geq n^{1 + 1/k}\]

Tome \(p = 8n^{-1 + 1/k}\) e denote por \(X\) o número de cópias de \(C_k\) em \(G(n, p)\). Há no máximo \(n^k\) cópias de \(C_k\) em \(K_n\), e cada cópia é contida em \(G(n, p)\) com probabilidade \(p^k\). Pela linearidade da esperança, temos que

\[Ex{X} = \Ex{\sum_i X_i} = \sum_{i} \Ex{X_i} = \sum \Pr{X_i = 1} = \sum p^k = n^kp^k\]

\begin{align} fasd &= fasfd \frac{1}{2}\\ afasd &\leq fasdfa \end{align}
Theme is based on Cactus
Created with Emacs 27.2 (Org mode 9.4.4) on GNU/Linux
Last Updated: 2021-10-19 ter 19:51