# Distribution of Induced Subgraphs of Extremal Ramsey Graphs

Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to \{r, b\}$ be an edge 2-coloring such that there is no monochromatic $k$ clique.

Define $\tau(i)$ to be the proportion of $K_k \subset G$ such that exactly $i$ of the edges are colored $r$.

Questions: Are there any (nontrivial) properties known about $\tau$? Most interestingly, does $\tau \to$ normal distribution as $k \to \infty$?

• I don't know anything about this problem, but how could $\tau$ converge to the normal distribution as $k\to\infty$? $\tau(i)$ is only defined for positive integers, the normal distribution is defined on all reals. Did you mean Poisson distribution? – Stefan Geschke Apr 12 '13 at 9:45
• Since a random coloring yields a decent construction for constructing Ramsey graphs (at least up to roughly at least $R(k,k)/4$ vertices),one might expect the distribution of colors to be "random" even for larger extremal examples. If this is the case, $\tau$ follows a binomial distribution; which for large enough $k$ (appropriately normalized) would limit towards a normal distribution in probability. – fkenter Apr 12 '13 at 10:15

One such result of Prömel and Rödl shows that Ramsey graphs on $n$ vertices contain all graphs up to $c\log n$ size as induced subgraphs, for an appropriate constant $c$.
H. J. Prömel and V. Rödl, Non-Ramsey graphs are $c\log n$-universal. J. Combin. Theory Ser. A 88 (1999), 379–384.