Skip to main content
explained subKneser graph in more detail
Source Link
domotorp
  • 18.7k
  • 3
  • 57
  • 125

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$ vertices.

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.

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$ vertices.

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

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.

Source Link
domotorp
  • 18.7k
  • 3
  • 57
  • 125

Is there a Ramsey theory for Kneser graphs?

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$ vertices.

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