# Intersection number of infinite graphs

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 $G$ is a simple, undirected graph, we define its intersection number $\iota(G)$ to be the smallest cardinal $\kappa$ such that there is a collection ${\cal C}$ of subsets of $\kappa$ such that $G_{\cal C} \cong G$.

For any cardinal $\kappa>0$ we define $\log(\kappa) = \min\{\mu\in\kappa\cup\{\kappa\}: 2^\mu \geq \kappa\}.$

If $G=(V,E)$ is infinite, is it true that $\iota(G) \in \{\;\log(|V|), |V| \;\}$?

• How do you define $\log(\kappa)$ when $\{\mu\in\kappa:2^\mu\ge\kappa\}$ is empty? – მამუკა ჯიბლაძე Mar 17 '17 at 9:37
• Good point!! I corrected this to $\log(\kappa) = \min\{\mu\in\kappa\cup\{\kappa\}: 2^\mu \geq \kappa\}.$ – Dominic van der Zypen Mar 17 '17 at 9:56
• You could also say $\mu\le\kappa$ instead of $\mu\in\kappa\cup\{\kappa\}$ – მამუკა ჯიბლაძე Mar 17 '17 at 10:00
• Do you have an example when $\iota(G)\ne|V|$? – მამუკა ჯიბლაძე Mar 17 '17 at 10:01
• Yes, $G = K_{\frak c}$ where ${\frak c} = 2^{\aleph_0}$. We have $\iota(G) = \aleph_0$: Let ${\cal C} = \{A\subseteq \omega: 0 \in A\}$, so we have $G_{\cal C} \cong G$, therefore $\iota(G) \leq \aleph_0$, and it's not hard to see that we cannot have $\iota(G) < \aleph_0$, so $\iota(G) = \aleph_0$. – Dominic van der Zypen Mar 17 '17 at 10:04

I think the answer is no, at least not without some additional assumptions. Suppose that $|\omega| < |\omega_1| < \mathfrak c$ and let $G$ be the union of the complete graph on $\mathfrak c$ and an independent set of size $|\omega_1|$. As you mention in the comments, the clique can be represented as an intersection graph of subsets of $\omega$, so we can represent $G$ using a ground set of size $|\omega_1| < \mathfrak c$. But we certainly need a ground set of size at least $|\omega_1| > |\omega| = \log \mathfrak c$.