3
$\begingroup$

For a natural number $N$ we can construct a graph $\underline{\text{SubsetGraph}}(N)$ with vertices for each subset of $\{1,2,\ldots,N\}$ and an edge between two vertices when the corresponding subsets are disjoint.

Is it true that given any simple undirected graph $G$ with N vertices, it is a induced subgraph of $\underline{\text{SubsetGraph}}(N)$. How can you prove or disprove it ?

$\endgroup$

1 Answer 1

2
$\begingroup$

Edit:

I was wrong and @RGB was right, it's not easy to fix. Actually, this fact is not true.

A counterexample is as follows:

$\hspace{50pt}$counterexample

Suppose there exists a mapping $S : V \to \mathcal{P}(V)$ such that $(u,v) \in E$ if and only if $S_u \cap S_v = \varnothing$. We know that $(1,2) \in E$, so $S_1 \cap S_2 = \varnothing$ and WLOG we can assume that $|S_1| \leq 2$. However, $S_3$, $S_4$, $S_5$ are pairwise disjoint, and hence for $S_1$ to have non-empty intersection with each of them, we need $|S_3| \geq 3$, contradiction.

I hope this helps $\ddot\smile$

$\endgroup$
3
  • 1
    $\begingroup$ I am getting sometimes two $S_v$ equal for different vertices. For example for the three vertex graph with edges $(ac),(bc)$. Don't we get $S_a=\{ab\}=S_b$? $\endgroup$
    – OR.
    Jul 30, 2013 at 11:14
  • 1
    $\begingroup$ I don't find it incredibly easy to fix. For example, every leaf of the graph is going to get the same $S$. If the number of leaves is large then how do you choose which elements to delete for which vertices? And not only for leaves, whenever a bunch of vertices do not have edges between them, this is going to happen. I have not idea how to fix it. $\endgroup$
    – OR.
    Jul 30, 2013 at 12:00
  • $\begingroup$ @RGB You are right, it's not easy to fix, it's not even true. You will find a counterexample and full explanation in the last edit. $\endgroup$
    – dtldarek
    Jul 30, 2013 at 17:03

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.