hypergraph cartesian join operation (over same vertex set) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:26:20Z http://mathoverflow.net/feeds/question/108655 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108655/hypergraph-cartesian-join-operation-over-same-vertex-set hypergraph cartesian join operation (over same vertex set) vzn 2012-10-02T17:15:26Z 2012-10-06T18:52:34Z <p>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 <em>"sparse"</em> BDDs without all variable references.</p> <p>this cartesian join appears not to have been studied much or be much related to hypergraph products (of which there is significant recent material &amp; 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 <em>vertex sets</em> (<em>not</em> the edge sets).</p> <p>Knuth has enthusiastically investigated ZDDs [2],[3] &amp; has dedicated a significant section of his <em>Art of computer programming vol4.1</em> to the subject (30pp and 70 exercises):</p> <p><em>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.</em></p> <p>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.</p> <blockquote> <p>what are some other references on or applications of this hypergraph cartesian join operation?</p> </blockquote> <p>am particularly interested in its similarities to products and factoring incl decomposition algorithms etc. </p> <p><hr> [1] <a href="http://crypto.stanford.edu/pbc/notes/zdd/family.xhtml" rel="nofollow">Families of sets/multiple families</a> by B.Lynn on ZDDs</p> <p>[2] Katayanagi prize, <a href="http://www.cs.cmu.edu/~katayanagi/2009/knuth_abstract.html" rel="nofollow">ZDD Structures and Families of Sets, Donald E. Knuth</a></p> <p>[3] <a href="http://www.cs.ox.ac.uk/news/2-full.html" rel="nofollow">Fun with ZDDs talk by Knuth</a></p> <p>[4] <a href="http://www.jst.go.jp/sicp/ws2010_austria/presentation/presentation_22.pdf" rel="nofollow">ZDD and its applications to intelligent processing</a> slides by Minato</p> <p>[5] <a href="http://www-erato.ist.hokudai.ac.jp/docs/tcstr-minato.pdf" rel="nofollow">Recent and future work on decision diagrams and discrete structure manipulation</a> by Minato</p> <p>[6] <a href="http://eprints2008.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf" rel="nofollow">Zero suppressed BDDs and their applications</a> by Minato</p> http://mathoverflow.net/questions/108655/hypergraph-cartesian-join-operation-over-same-vertex-set/109019#109019 Answer by ron blei for hypergraph cartesian join operation (over same vertex set) ron blei 2012-10-06T18:52:34Z 2012-10-06T18:52:34Z <p>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...</p>