Disjunction number of a graph

Question

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

Answer 1

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.

Answer 2

Try this. For the complementary graph, form it as a union of cliques. For infinite graphs on $\kappa$ vertices, there will be at most this many cliques.

Now assign to each vertex the list of cliques to which it belongs. If two vertices do not have a clique in common, they do not have an edge in the complement, and so must have an edge in G. So the inequality holds for graphs that are not finite.

I suspect it holds for many finite graphs as well. However, if the complement is like a dense bipartite graph, this construction does not work. It does given an upper bound on the disjunction number of something on the order of n^2/4.

Gerhard "Maybe Call It Clique Decomposition" Paseman, 2019.05.12.

Answer 3

The mathematical questions have been answered by Fedor Petrov and Gerhard Paseman. My purpose is to offer a partial answer to the historical/bibliographical question suggested in parentheses at the the end; namely, that the same notion, or something closely related to it (being vague because I'm too lazy to read the paper in detail), can be found in:

K. Čulík, Applications of graph theory to mathematical logic and linguistics, in: Theory of Graphs and its Applications, Proceedings of the Symposium held in Smolenice in June 1963; Publishing House of the Czechoslovak Academy of Sciences, Prague; Academic Press, New York and London; pp. 13–20.

Čulík defines the number of completeness of a graph $G$, denoted by $\omega(G)$, as the smallest cardinal number of a collection of complete subgraphs covering all the edges and vertices of $G$. As a slight modification, let me define $\varepsilon(G)$ as the smallest number of complete subgraphs covering all the edges of $G$. (I'm sorry if $\varepsilon$ is a bad choice of notation; I don't know if there is any Greek letter that does not already have a reserved meaning in graph theory.) If $\overline G$ denotes the complement of $G$, it is easy to see that $$\delta(G)=\varepsilon(\overline G).$$ The answers to the mathematical questions for infinite and finite graphs follow from the fact that $\varepsilon(G)\le|E(G)|$ in all cases, while $\varepsilon(G)=|E(G)|$ if $G$ is triangle-free. Thus, if $G$ is an infinite graph, then $\delta(G)=\varepsilon(\overline G)\le|E(\overline G)|\le|V(G)|$; if $G$ is a finite graph with $n$ vertices and $\overline G$ is bipartite with $\left\lfloor\frac{n^2}4\right\rfloor$ edges, then $\delta(G)=\varepsilon(\overline G)=|E(\overline G)|=\left\lfloor\frac{n^2}4\right\rfloor$.

The papers citing Čulík's paper may also be relevant, but I don't have time to look into them.