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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ How do you define $\log(\kappa)$ when $\{\mu\in\kappa:2^\mu\ge\kappa\}$ is empty? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented 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$
    – Dominic van der Zypen
    Commented Mar 17, 2017 at 9:56
  • $\begingroup$ You could also say $\mu\le\kappa$ instead of $\mu\in\kappa\cup\{\kappa\}$ $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Mar 17, 2017 at 10:00
  • 1
    $\begingroup$ Do you have an example when $\iota(G)\ne|V|$? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented 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$
    – Dominic van der Zypen
    Commented Mar 17, 2017 at 10:04

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .