Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most interested in the following question.

If in a two-coloring of $KG(n,k)$ any subKneser graph $KG(3k,k)$ has a red edge, and any triangle has a blue edge, then how large can $n$ be?

Here by subKneser graph $KG(3k,k)$ I mean a subgraph induced by $3k$ of the $n$ elements. So if the vertices of $KG(n,k)$ are $\binom Sk$ where $|S|=n$, then the vertices of $KG(3k,k)$ should be $\binom {S'}k$ where $S'\subset S$ such that $|S'|=3k$.

The question is related to the three disjoint equivoluminous subsets problem, which is related to the polymath10 project.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.