7
$\begingroup$

Consider a graph with the vertices being all subsets of size $n$ of a set of size $2n$. Two vertices are connected if their overlap has size at most one. What is the chromatic number of this graph?

If we have two vertices connected when the overlap is empty, then this corresponds to the Kneser graph, for which we know the chromatic number for any $n,k$. In this special case $k=n/2$, the chromatic number of the Kneser graph is trivially two. In our case, we have the generalized Kneser graph $KG(2n,n,1)$. It seems that the chromatic number is always $6$ for any $n\geq 2$. Can we prove this, or does it follow from some known result?

As domotorp wrote in the comments, the graph is also called the discrete Borsuk graph. Is something known about its chromatic number?

$\endgroup$
2
  • $\begingroup$ It seems that this graph always has chromatic number 6. It's easy to see that 6 colors suffice since the vertex set can be written as a disjoint union of two parts each of which induces a Kneser graph with chromatic number 3. Following Lovasz' original proof, my claim would follow if we can also prove that the neighborhood simplicial complex of your graph is 3-connected. This seems to be true but I haven't been able to come up with a proof yet. However it suggests adding the algebraic topology tag. $\endgroup$ Commented Jul 14, 2017 at 0:43
  • $\begingroup$ This thing has been called the "discrete Borsuk graph" in this unpublished manuscript: dcg.epfl.ch/files/content/sites/dcg/files/users/… For results related to the continuous version, we of course have ams.org/mathscinet-getitem?mr=708798. $\endgroup$
    – domotorp
    Commented Jul 22, 2017 at 20:56

1 Answer 1

2
$\begingroup$

The graph you are interested in is the generalized Kneser graph $KG(2n,n,1)$. The generalized Kneser graph $KG(n,r,s)$ has the same vertex set as a Kneser graph $KG(n,r)$ but with two vertices joined by an edge if their intersection has no more than $s$ elements.

A web search for chromatic numbers of such graphs generates many hits including a paper of Frankl and one of Tort in which the chromatic number is computed when $s = 1$ under some restrictions on $n$.

$\endgroup$
3
  • $\begingroup$ Interesting, unfortunately I can't access the papers. Is there a result for the graph $KG(2n,n,1)$? $\endgroup$
    – pi66
    Commented Jul 11, 2017 at 9:33
  • 3
    $\begingroup$ No, these papers deal with pretty much the opposite regime, where $n$ is exponentially large in $r$. $\endgroup$ Commented Jul 11, 2017 at 23:31
  • $\begingroup$ pi66: I only had access to the abstracts of those papers when I referenced them. Thanks @Gjergji Zaimi for clarifying the actual content of the papers. $\endgroup$
    – Aaron Dall
    Commented Jul 12, 2017 at 10:58

Your Answer

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