Muestre que existe$d'$ tal que para cada$d > d'$, cada$d$ - gráfico regular contiene un subgrafo de alcance con grado mínimo$\ge 10$ y circunferencia$\ge 10$.
¿Alguna idea de cómo abordar esta pregunta?
Respuesta
¿Demasiados anuncios?
Versión corta: elegir un subconjunto aleatorio de los bordes, cada borde de ser elegido con una probabilidad de $p = d^{-0.9}$. A continuación, aplicar el local lema.
Versión larga: hay ocho tipos de acontecimientos negativos.
- Tipo $1$: un vértice termina con menos de $10$ bordes.
- Tipo $k$$3 \le k \le 9$: un ciclo de longitud $k$ termina completamente elegido.
El promedio de grado de un vértice es $pd = d^{0.1}$, por lo que la probabilidad de que menos de la mitad de ese grado (que es $\ge 10$ $d$ suficientemente grande) es en la mayoría de las $\exp(-d^{0.1}/8)$ por un Chernoff-tipo de enlazado. En particular, este es más pequeño que cualquier función polinómica de $d$. Que tipo de $1$ eventos. Tipo $k$ eventos tienen probabilidad de $p^k = d^{-0.9k}$, que es sencillo.
El solapamiento entre estos, tenemos que contar el número de ciclos de longitud $j$ que contiene un determinado vértice. Esto es en la mayoría de las $d^{j-1}$: recogemos $j-1$ de los bordes del ciclo, se extiende desde un extremo en uno de $d$ formas, y el último borde debe ser el borde que cierra el ciclo, si ese borde que pasa a existir.
Como resultado, un tipo de $1$ evento está en condiciones de independencia mutua de todos, pero $d$ otro tipo de $1$ eventos, y todos, pero $d^{j-1}$ tipo $j$ eventos para cada una de las $j>2$. Un tipo de $k$ evento está en condiciones de independencia mutua de todos, pero en la mayoría de las $k$ tipo $1$ eventos, y todos, pero $k d^{j-1}$ tipo $j$ eventos para cada una de las $j>2$.
Así que establezca $x_1 = 1/d^2$ $x_k = 2 d^{-0.9k}$ por cada $k>2$. Comprobamos que para suficientemente grande $d$:
\begin{align} e^{-d^{0.1}/8} &\le \frac1{d^2} \cdot \left(1 - \frac1{d^2}\right)^d \cdot \prod_{j=3}^9 \left(1 - 2 d^{-0.9j}\right)^{d^{j-1}}, \\ d^{-0.9k} &\le 2 d^{-0.9k} \cdot \left(1 - \frac1{d^2}\right)^j \cdot \prod_{j=3}^9 \left(1 - 2d^{-0.9j}\right)^{k d^{j-1}}. \end{align}
Esto es sencillo por la de Bernoulli de la desigualdad: $(1-x)^r \ge 1-rx$$r\ge0$$x\le1$. En particular, $$\left(1 - 2 d^{-0.9j}\right)^{d^{j-1}} \ge 1 - 2d^{-0.9j} \cdot d^{j-1} = 1 - 2d^{0.1j-1} \ge 1 - 2d^{-0.1}$$ for $j\le 9$, which can be made arbitrarily close to $1$ by taking $d$ lo suficientemente grande.
