OPENNOTORIOUSgraph theoryRamsey theory
Give a constructive proof that $R(k)>C^k$ for some constant $C>1$. Equivalently, explicitly construct a graph on $n$ vertices with no clique or independent set of size $\geq c\log n$.
Notes: Erdos provided a probabilistic proof showing R(k) >> k * 2^{k/2}. Li recently improved the constructive bound to avoiding sets of size >= (log n)^C for some constant C > 0.
AI Status: NONE · 0 total attempts