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$
5
  • 1
    $\begingroup$ How do you define $\log(\kappa)$ when $\{\mu\in\kappa:2^\mu\ge\kappa\}$ is empty? $\endgroup$ Mar 17, 2017 at 9:37
  • $\begingroup$ Good point!! I corrected this to $\log(\kappa) = \min\{\mu\in\kappa\cup\{\kappa\}: 2^\mu \geq \kappa\}.$ $\endgroup$ Mar 17, 2017 at 9:56
  • $\begingroup$ You could also say $\mu\le\kappa$ instead of $\mu\in\kappa\cup\{\kappa\}$ $\endgroup$ Mar 17, 2017 at 10:00
  • 1
    $\begingroup$ Do you have an example when $\iota(G)\ne|V|$? $\endgroup$ Mar 17, 2017 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$ Mar 17, 2017 at 10:04

1 Answer 1

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.