1
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Stefan Geschke
    Apr 12, 2013 at 9:45
  • $\begingroup$ 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. $\endgroup$
    – fkenter
    Apr 12, 2013 at 10:15

1 Answer 1

Reset to default
3
$\begingroup$

This is an open problem. Vera Sós has asked at numerous conferences if Ramsey graphs (these are graphs on n vertices with the smallest possible homogeneous set size) are quasirandom, in that each ordered graph on k vertices appears with asymptotically the same frequency. A positive answer to Sós' question would give a positive answer to your question. Unfortunately, while there are numerous nice results and conjectures about the structure of Ramsey graphs, these problems are still open.

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.

Another short proof of this result is given in:

J. Fox and B. Sudakov, Induced Ramsey-type theorems. Adv. Math. 219 (2008), 1771–1800.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.