Representability of “large” graphs by “small” intersection graphs

Question

If ${\cal C}$ is a collection of subsets of a set $X$, we associate to ${\cal C}$ a graph $G_{\cal C} = (V,E)$ where $V = {\cal C}$ and $$E = \big\{\{A,B\}: A\neq B\in {\cal C} \land A\cap B \neq \emptyset\big\}.$$

If $\kappa$ is a cardinal and ${\cal C}$ is a collection of subsets of $\kappa$, it is easy to see that $G_{\cal C}$ has at most $\kappa$ connected components. So, suppose that $G = (V,E)$ is a graph with $V = 2^\kappa$ and the number of connected components is at most $\kappa$. Is there a collection ${\cal C}$ of subsets of $\kappa$ such that $G \cong G_{\cal C}$?

Answer 1

Assuming that $\kappa$ is an infinite cardinal, I answer your question with a characterization.

For $\mathcal C\subseteq\mathcal P(\kappa),$ the intersection graph $G_\mathcal C=(V,E)$ has the following properties:
(1) $|V|\le2^\kappa;$
(2) there is a collection $\mathcal K$ of cliques, with $|\mathcal K|\le\kappa,$ covering all vertices and edges of the graph; that is, each vertex belongs to an element of $\mathcal K,$ and each pair of adjacent vertices is contained in an element of $\mathcal K.$

Conversely, I clain that any graph $G=(V,E)$ satisfying those two conditions is isomorphic to an intersection graph $G_\mathcal C$ with $\mathcal C\subseteq\mathcal P(\kappa).$

Let $G=(V,E)$ be a graph satisfying (1) and (2). We may assume that $V\subseteq\{X:0\in X\subseteq\kappa\}.$ Let $\mathcal K$ be a collection of cliques in $G,$ of cardinality at most $\kappa,$ covering all vertices and edges of $G.$ Since $|\kappa\times\mathcal K|=\kappa,$ it will suffice to show that $G\cong G_\mathcal C$ for some $\mathcal C\subseteq\kappa\times\mathcal K.$

For $v\in V$ define $A_v=\{(\alpha,K)\in\kappa\times\mathcal K:\alpha\in v\in K\}.$

$v\mapsto A_v\text{ is injective}:$
Suppose $u,v\in V$ and $\alpha\in u\setminus v.$ Choose $K\in\mathcal K$ with $u\in K;$ then $(\alpha,K)\in A_u\setminus A_v.$

$\{u,v\}\in E\implies A_u\cap A_v\ne\emptyset$:
Choose $K\in\mathcal K$ with $u,v\in\mathcal K;$ then $(0,K)\in A_u\cap A_v.$

For $u\ne v,\ A_u\cap A_v\ne\emptyset\implies\{u,v\}\in E:$
If $(\alpha,K)\in A_u\cap A_v),$ then $u$ and $v$ are both in the clique $K.$

Therefore $G\cong G_\mathcal C$ where $\mathcal C=\{A_v:v\in V\}.$

Answer 2

You probably want a stronger condition on $G$ than just the number of components:

Let $G$ be a star with $2^\kappa$ leaves. Then the leaves form an independent set of size $2^\kappa$, but there is no collection of subsets of $\kappa$ containing more than $\kappa$ disjoint sets.