9
$\begingroup$

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.

$\endgroup$

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.