1

In algebra or, number theory, it is fun playing with distributivity of one operation over the other; it helps in simplifying the calculations; for instance, $5\times(106)=5\times 100+5\times 6=530.$ Or, $16\times 6+ 16\times 4=16\times(6+4)=16\times 10=160.$

We know that graph intersection $\cap$ distributes over graph union $\cup$. What is a fun or, an interesting fact about the distributivity of graph intersection $\cap$ over graph union $\cup$? I can't find any geometrical significance or important usage of distributivity of graph operations.

Note that the graphs are simple and undirected here.

gete
  • 1,352

1 Answers1

1

This is a very broad answer, but here are some things I can think of.

First of all, there are two common versions of 'graph union'. One is the general union of the vertex-sets and the edge-sets, and the other is the disjoint union where the operation remains the same but the graphs are seen to be disjoint (empty intersection).

Rough example uses

There are more interesting things you can do with disjoint union. For instance, any graph can be seen as the disjoint union of its connected components and that decomposition is unique among decompositions into the disjoint union of connected graphs. In this sense, anything that applies component-wise can be seen to distribute over the disjoint union. Many things can be done component-wise, in particular, the search for any connected subgraph such as paths, cycles, trees, cliques is such an example and graph intersection is one way to 'select' subgraphs from a graph. So if the connected components $G_1, \cdots, G_k$ of a graph $G$ have some special structure which makes intersection easier, than you can use that to compute $(G_1 \cap H) \cup (G_2 \cap H) \cdots (G_k \cap H)$ faster than $G \cap H$ vertex-wise and edge-wise. Direct computational advantages cannot seem to be generalizable to any class of graphs.

Problems

Unfortunately, a big hurdle against finding very many interesting things to do with graph union and intersection is that union is not invertible (there is such a thing as a $-5$ number, but there is no $-G$ graph) and graph intersection does not even have a unit (there is no '1 graph' $G$ such that $H \cap G = H$ for all graphs $H$ (at least not nice, finite graphs). To see why these cause problems, consider the case on integers where multiplication by 10 is easy. This multiplication is considered easy because the digits of 10 are 1, the multiplicative identity, so you don't change the digits and 0, multiplicative absorbing element, so the multiplication by 0 is 0 allowing you to say that $16 \times 10 = 16 0$ the same digits, but shifted.

Other operations

Since you appear to be searching for interesting uses of some properties of graph operations more broadly, I would like to direct you toward a generalization of these graph operations in category theory as products and sums. Here, union and intersection can be seen as categorical sums and products in the category where arrows are inclusion (in other words where functions can be seen as indicating the subgraph relation), but there are other distributive operations that might resemble those on numbers more, namely, the tensor product and the edge-disjoint union.

EDIT: Categorical products don't have to distribute over categorical sums Distributivity of categorical product and sum

Jad Issa
  • 26
  • 1
    By the ways, If we consider a specific class of graphs like a set of all subgraphs of a simple undirected graph $G$, then for any sub graphs $H$ of $ G$, we get $H\cap G=H$ or $G\cap H= H$, where $G$ is the identity. – gete Nov 20 '20 at 12:15