0
$\begingroup$

Consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph $H_3=H_1 \sqcup H_2 = (V, \mathscr{E}_1 \times \mathscr{E}_2)$ where "$\times$" is the cartesian join over edge sets. I am using the "$\sqcup$" join operator basically as defined in [1], a web page by B.Lynn about ZDDs (a variant of BDD, binary decision diagrams), but haven't seen that notation used in a paper so far. BDDs/ZDDs are an equivalent representation system for set families or hypergraphs. ZDDs generally more efficiently model "sparse" BDDs without all variable references.

This cartesian join appears not to have been studied much or be much related to hypergraph products (of which there is significant recent material & research) because hypergraph products are all defined over two different vertex sets $V_1$, $V_2$ and are built out of the cartesian join of the vertex sets (not the edge sets).

Knuth has enthusiastically investigated ZDDs [2],[3] & has dedicated a significant section of his Art of computer programming vol4.1 to the subject (30pp and 70 exercises):

Such operations form a "family algebra," and there are interesting algorithms to implement the operations of family algebra as operations on ZDDs. Family algebra is a relatively new topic that is just beginning to be understood.

This cartesian join operation in ZDDs appears to have been 1st implemented by Minato, an originator of ZDD operations. See p10 of [4] where it is called the "cartesian product set P*Q" and was apparently 1st introduced in [6] p7.

What are some other references on or applications of this hypergraph cartesian join operation?

I am particularly interested in its similarities to products and factoring incl. decomposition algorithms etc.


[1] Families of sets/multiple families by B.Lynn on ZDDs

[2] Katayanagi prize, ZDD Structures and Families of Sets, Donald E. Knuth

[3] Fun with ZDDs talk by Knuth

[4] ZDD and its applications to intelligent processing slides by Minato

[5] Recent and future work on decision diagrams and discrete structure manipulation by Minato

[6] Zero suppressed BDDs and their applications by Minato

$\endgroup$
1
  • $\begingroup$ ie $\mathscr{E}_1 \times \mathscr{E}_2 = \{ e_1 \cup e_2: e_1 \in \mathscr{E}_1, e_2 \in \mathscr{E}_2 \} $ $\endgroup$
    – vzn
    Oct 10, 2012 at 17:33

2 Answers 2

3
$\begingroup$

You may want look at the so called "fractional Cartesian products" studied extensively by Blei in connection with some extremal problems in Harmonic Analysis. You may have to translate some of his formalism to fit your needs that are stated in graph-theoretic language...

$\endgroup$
1
2
$\begingroup$

The problem of poly-time inversion of this kind of product was solved in 2014. See, for example,
Pavel Emelyanov and Denis Ponomaryov "The Complexity of AND-decomposition of Boolean Functions" (English), Discrete Applied Mathematics. 280 (2020), pp. 113–132, DOI:10.1016/j.dam.2019.07.005, MR4096175, Zbl 1481.94166.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.