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}$?


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\}.$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.