# Chromatic number of graph of subsets of a set

Suppose set $A$ with $2n$ elements. Construct simple graph $G$ with $\left(\begin{array}{c}2n\\ n\end{array}\right)$ vertices each one represents one of $n$_sized subsets of $A$ .Connect any two vertices of $G$ with an edge if and only if their corresponding subsets of $A$ , have one element in common or none(at most one element in common) .Prove that the chromatic number of $G$ is $6$ . In other word we can always color each vertex of $G$ such that no two adjacent vertex have the same color and also we can not do it with $5$ colors.

$n>3$

Its not difficult to show that we can do it with 6 colors , but how to prove that 5 colors are not enough and its not possible with 5 colors?

• What have you tried? We are dealing with the complement of a Kneser graph, and the chromatic number of Kneser graphs is well known since Lovasz. – Jack D'Aurizio Jul 18 '16 at 19:19
• Do you mean at least? It seems incorrect. Let $2n$ be large, like $60$. Surely we can find $10$ subsets of $\{1,\dots,60\}$ of size $30$ such that any two have an element in common. They can all for example contain the number $1$. – André Nicolas Jul 18 '16 at 19:21
• No , we connect any two vertices if and only if their corresponding subsets have one element in common or none . And notice that we can not find 10 subsets in $n=30$ such that any two are connected since any two of them must have at last one element in common and should differ a lot ! – Ypical Jul 18 '16 at 19:39
• sorry i mean at most – Ypical Jul 18 '16 at 19:50
• @Ypical: I guess "at last" could be interpreted as meaning "at most", but the phrase is not in common use in mathematical English. My example was for the interpretation "at least". – André Nicolas Jul 18 '16 at 20:26

Choose three distinct numbers $a,b,c\in\{1,\dots,2n\}.$

Color a vertex $X$ with
color $1$ if $X\cap\{a,b,c\}\supseteq\{a,b\},$
color $2$ if $X\cap\{a,b,c\}=\{a,c\},$
color $3$ if $X\cap\{a,b,c\}=\{b,c\},$
color $4$ if $X\cap\{a,b,c\}=\{a\},$
color $5$ if $X\cap\{a,b,c\}=\{b\},$
color $6$ if $X\cap\{a,b,c\}\subseteq\{c\}.$
This proper $6$-coloring shows that $\chi(G_n)\le6.$

• Thanks, but how to prove 5 colors is not sufficient :D – Ypical Jul 18 '16 at 20:19
• I don't know... – bof Jul 18 '16 at 20:31