5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How do you define $\log(\kappa)$ when $\{\mu\in\kappa:2^\mu\ge\kappa\}$ is empty? $\endgroup$ – მამუკა ჯიბლაძე Mar 17 '17 at 9:37
  • $\begingroup$ Good point!! I corrected this to $\log(\kappa) = \min\{\mu\in\kappa\cup\{\kappa\}: 2^\mu \geq \kappa\}.$ $\endgroup$ – Dominic van der Zypen Mar 17 '17 at 9:56
  • $\begingroup$ You could also say $\mu\le\kappa$ instead of $\mu\in\kappa\cup\{\kappa\}$ $\endgroup$ – მამუკა ჯიბლაძე Mar 17 '17 at 10:00
  • 1
    $\begingroup$ Do you have an example when $\iota(G)\ne|V|$? $\endgroup$ – მამუკა ჯიბლაძე Mar 17 '17 at 10:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – Dominic van der Zypen Mar 17 '17 at 10:04
3
$\begingroup$

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

$\endgroup$

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.