# Disjunction number of a graph

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

• Isn't the complete graph on $\kappa$ elements an induced subgraph? The inequality seems to hold for all graphs on three vertices. Gerhard "Can't See It Not Holding" Paseman, 2019.05.12. – Gerhard Paseman May 12 at 14:37
• Yes, the complete graph on $\kappa$ elements is an induced subgraph on ${\cal P}(\kappa)$, but what about all the other graphs on $\kappa$ vertices? (I inserted a link leading to the definition of induced subgraphs in the question.) – Dominic van der Zypen May 12 at 15:02
• I am puzzling through a construction which should give the inequality for any infiinite graph G which is a finite union of maximal cliques. At each step, you incorporate a new maximal clique by adding a bunch of new elements to take care of the complementary graph. Gerhard "Complement, That Is The Ticket" Paseman, 2019.05.12. – Gerhard Paseman May 12 at 15:14
• This is now findstat.org/StatisticsDatabase/St001391. It would be great if you could check a few values! – Martin Rubey May 14 at 10:52
• Thanks @MartinRubey for including this in findstat.org! The code looks fine to me, very concise and clear, and the small examples I checked look good! – Dominic van der Zypen May 14 at 13:26

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.

• Thanks Fedor - I was convinced there would be some constant $c\geq 1$ such that $\delta(G) \leq c\cdot |V(G)|$ for all finite graphs, and your example proved me wrong! Very nice example! – Dominic van der Zypen May 13 at 7:46

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.

• I see Fedor had a similar idea and posted it while I was writing this. Fortunately I had something additional to contribute. Gerhard "Must Learn To Type Faster" Paseman, 2019.05.12. – Gerhard Paseman May 12 at 15:28
Č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$$.