Combinatoria
Lista Corta de ELMO (2012)
Lista Corta de ELMO 2012 Problema C6
6 Considere un grafo dirigido $G$ con $n$ vértices, donde se permiten $1$ - ciclos y $2$ - ciclos. Para cualquier conjunto $S$ de vértices, sea $N^{+}(S)$ la vecindad saliente de $S$ (es decir, el conjunto de sucesores de $S$ ) , y defina $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ para $k\ge2$ . Para $n$ fijo, sea $f(n)$ el número máximo posible de conjuntos distintos de vértices en $\{(N^{+})^k(X)\}_{k=1}^{\infty}$ , donde $X$ es algún subconjunto de $V(G)$ . Demuestre que existe $n>2012$ tal que $f(n)<1.0001^n$ . Linus Hamilton.
0
0
Kevin
Inicia sesión para agregar soluciones y pistas