Recuento de la camarilla de los gráficos gratuitos?

Question

Estoy buscando una razonable, pero simple límites inferiores o asymptotics para $S_n(k)$, el número de marcado gráficos en $n$ vértices que contienen no $k+1$-clique. Bastante débil el límite inferior es el número de conectados gráficos en $k$ vértices veces el número de formas de elegir los $k$ vértices de $v$, pero incluso esto es un poco desordenado.

---

Kolaitis, Prömel, y Rothschild mostró en 1987, $S_n(k)$ es asintóticamente igual al número de marcado gráficos en $n$ vértices que se $k$-colourable (o $k$-partita). J. Balogh et al. recientemente mejorado, mostrando que casi todos los $k$libre de gráficos se $k-1$-partita al $k$ es un crecimiento lento de la función de $n$. (arXiv:1406.6961) Finalmente, Prömel en 1987 mostró que casi todos los etiquetados de los gráficos que contiene no $k$-camarilla son rígidos. Sin embargo, estos resultados no parecen producir una expresión explícita.

Answer 1

Nunca la mente: Mousset, Nenadov y Steger (arXiv:1312.1143v3) mostró que $S_n(k) = 2^{(1-1/k)n^2/2 + o(n^2/(k+1))}$, incluso cuando se $k$ es un crecimiento lento de la función de $n$. Esto se extiende un resultado de Erdős, Kleitman y los Rothschild, a partir de 1976 (preprint) fija $k$.