5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 12 at 14:37
  • $\begingroup$ 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.) $\endgroup$ – Dominic van der Zypen May 12 at 15:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 12 at 15:14
  • $\begingroup$ This is now findstat.org/StatisticsDatabase/St001391. It would be great if you could check a few values! $\endgroup$ – Martin Rubey May 14 at 10:52
  • $\begingroup$ 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! $\endgroup$ – Dominic van der Zypen May 14 at 13:26
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Dominic van der Zypen May 13 at 7:46
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman May 12 at 15:28
  • $\begingroup$ Thanks for your additional answer! $\endgroup$ – Dominic van der Zypen May 13 at 7:32
2
$\begingroup$

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.

$\endgroup$

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.