MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 \} $ – vzn Oct 10 '12 at 17:33
up vote 2 down vote accepted

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

share|cite|improve this answer
ok eg Combinatorial Dimension in Fractional Cartesian Products ...? did not see it, can you elaborate? – vzn Oct 18 '12 at 18:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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