Coloring the Powerset of $[n]$ Let $[n] = \{1,2, \dots, n\}$, and let $\mathcal{P}([n])$ denote its powerset. Given $\mathcal{P}([n])$, we will form a graph $G$ in the following manner: to each element $i \in \mathcal{P}([n])$, associate with it a vertex $v_i$, and add an edge between vertices $v_i, v_j$ if $i \not\subset j$, $j \not\subset i$, and $|i \cap j| \neq \varnothing$. Is there a known result that tells us what $\chi(G)$ is? I've looked around a little bit, but the closest thing I could find was this post. It is simple to see:
 $$ \dbinom{n}{\left\lceil\frac{n+1}{2}\right\rceil} \le \chi(G) $$ since for all elements $i,j \in \mathcal{P}([n])$ with $|i| = |j| = \left\lceil\frac{n+1}{2}\right\rceil$, $v_i$ and $v_j$ are adjacent. If an exact result on the coloring is too hard, is there a way to bound $\chi(G)$ from above? 
 A: Here is a partial answer. Let $G_n$ be the graph with vertex set $V_n=\mathcal P([n])$ and edge set $E_n=\{\{X,Y\}\in\binom{V_n}2:X\setminus Y\ne\emptyset,\ Y\setminus X\ne\emptyset,\ X\cap Y\ne\emptyset\}$.
Lemma 1. $\chi(G_n)\le\binom n{\lceil\frac n2\rceil}$.
Proof. It's well known that $\mathcal P([n])$ can be decomposed into $\binom n{\lceil\frac n2\rceil}$ chains; chains are independent sets in $G_n$.
Lemma 2. $\chi(G_n)\ge\omega(G_n)\ge\binom n{\lceil\frac{n+1}2\rceil}$.
Proof. The set of all $\lceil\frac{n+1}2\rceil$-element subsets of $[n]$ is a clique in $G_n$.
Lemma 3. If $n=2t\gt2$ then $\chi(G_n)\ge\frac12\binom n{t+1}+\frac12\binom nt=\frac12\binom n{\lceil\frac{n+1}2\rceil}+\frac12\binom n{\lceil\frac n2\rceil}$.
Proof. First, we need $\binom n{t+1}$ colors for the $(t+1)$-element sets, which must all be of different colors. Second, if $X$ is a $(t+1)$-element set, then (since $t\gt1$) at most one $t$-element set can have the same color as $X$. Therefore, we need additional colors for the remaining $\binom nt-\binom n{t+1}$ $t$-element sets. Since we can't have more than two (complementary) $t$-element sets of the same color, it follows that
$$\chi(G_n)\ge\binom n{t+1}+\frac{\binom nt-\binom n{t+1}}2=\frac12\binom n{t+1}+\frac12\binom nt.$$
Theorem. $\frac12\binom n{\lceil\frac{n+1}2\rceil}+\frac12\binom n{\lceil\frac  n2\rceil}\le\chi(G_n)\le\binom n{\lceil\frac n2\rceil}$ for $n\ne2$.
Proof. The upper bound is Lemma 1. The lower bound is Lemma 2 for odd $n$ and Lemma 3 for even $n$ except $n=0$ which can be checked separately.
Corollary. If $n$ is odd then $\chi(G_n)=\binom n{\lceil\frac n2\rceil}$.
Proof. $\lceil\frac{n+1}2\rceil=\lceil\frac n2\rceil$ if $n$ is odd.
Remark 1. $\chi(G_4)=5$.
Proof. $\chi(G_4)\ge5$ by Lemma 3. To show $\chi(G_4)\le5$ we only need to color the non-isolated vertices of $G_4$, i.e., the sets of size $2$ or $3$.
Color 1: $\{1,2,3\},\ \{1,3\}$
Color 2: $\{1,2,4\},\ \{2,4\}$
Color 3: $\{1,3,4\},\ \{1,4\}$
Color 4: $\{2,3,4\},\ \{2,3\}$
Color 5: $\{1,2\},\ \{3,4\}$
Remark 2. $18\le\chi(G_6)\le20$; what is the actual value?
