Let $S\neq \emptyset$ be a set. We make its powerset ${\cal P}(S)$ into a simple, undirected graph by saying that $A, B\in{\cal P}(S)$ form an edge if and only if $A\cap B=\emptyset$. 


The *disjunction number* of a graph $G=(V,E)$ is the smallest cardinal $\kappa$ such that $G$ is isomorphic to an [induced subgraph](https://en.wikipedia.org/wiki/Induced_subgraph) of ${\cal P}(\kappa)$, and we denote the disjunction number of $G$ by $\delta(G)$.


Is $\delta(G) \leq |V|$ for any (finite or infinite) graph $G=(V,E)$? (As an aside remark, it would also be interesting to know whether what I call "disjunction number" has a proper name.)



Disjunction number of a graph
For finite graphs there exists a graph $G$ on $n$ vertices with $\delta(G)\geqslant \lfloor n^2/4\rfloor$. Namely, let $G$ be the disjoint union of two cliques $C\_1,C\_2$ on $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$ vertices resp. The vertices of $C\_1$ should correspond to disjoint sets $X\_1,\ldots,X\_a$, the vertices of $C\_2$ to disjoint sets $Y\_1,\ldots,Y\_b$. Any two sets $X\_i,Y\_j$ should have a common element $p\_{ab}$, and they are all distinct since $X\_i$'s are disjoint aswell as $Y\_j$'s. Therefore the ground set $S$ must contain at least $ab=\lfloor n^2/4\rfloor$ elements.


If I remember well, the edge set of any graph $G$ on $n$ vertices may be covered by a union of at most $f(n):=\lfloor n^2/4\rfloor$ cliques (cliques of size 2 and 3 should be enough), that implies $\delta(G)\leqslant \lfloor n^2/4\rfloor$. So this estimate for fixed $n$ is sharp.


The fact I am trying to remember should be provable by induction with removing a vertex with the minimal degree.


Indeed, let $v$ be a vertex of $G$ of minimal degree $d$, $N(v)$ be the set of neighbours of $v$. If $N(v)$ contains at least $d(v)-f(n)+f(n-1)$ disjoint edges, then the edges incident to $v$ may be covered by $f(n)-f(n-1)=\lfloor n/2\rfloor$ triangles and segments, and we may induct. If not, we have $d=\lfloor n/2\rfloor+k$ for some $k>0$, and $N(v)$ contains at most $k-1$ disjoint edges. Choose a maximal collection $\Omega$ of
disjoint edges in $N(v)$. We have $k=d-\lfloor n/2\rfloor\leqslant n-1-\lfloor n/2\rfloor\leqslant \lfloor n/2\rfloor$, therefore the exist $w\in N(v)$ not covered by the edges from $\Omega$. This vertex $w$ may be joined with at most $2(k-1)$ vertices in $N(v)$, thus the degree of $w$ does not exceed $2(k-1)+n-d=n-2+k-\lfloor n/2\rfloor<\lfloor n/2\rfloor+k=d$, a contradiction.


