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. 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 havent 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?

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

  • $\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 '12 at 17:33

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


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.