http://openproblemgarden.org/op/enumerating_the_number_of_binary_relations Comments for "Enumerating the number of binary relations" en http://openproblemgarden.org/op/enumerating_the_number_of_binary_relations <table cellspacing="10"> <tr> <td> Author(s): <a href="/kpz_equation_central_limit_theorem"></a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/combinatorics">Combinatorics</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Problem</p> <p>Consider the finite set <img class="teximage" src="/files/tex/5e73d98d00a2a88ad490e4ca6382ad3cc0177bc9.png" alt="$ [n]=\{1,\dots,n\} $" />. We define a binary relation <img class="teximage" src="/files/tex/201b5ff8bf9045c34a583adc2741b00adf1fd14c.png" alt="$ R $" /> over the set <img class="teximage" src="/files/tex/06d9f8dd53868a1233f15c435c46e03deb17a82a.png" alt="$ [n] $" /> and we write <img class="teximage" src="/files/tex/d1b45b1ae16dbe47122151309a6d70fb181bcabe.png" alt="$ a\sim b $" /> to indicate <img class="teximage" src="/files/tex/b1d91efbd5571a84788303f1137fb33fe82c43e2.png" alt="$ a $" /> is related to <img class="teximage" src="/files/tex/0ba883c80f0b5e29aca587fcf5c2808ea8dd9d72.png" alt="$ b,\quad a,b\in R $" />. We have the following properties of <img class="teximage" src="/files/tex/201b5ff8bf9045c34a583adc2741b00adf1fd14c.png" alt="$ R $" />:</p> <p>(i) <img class="teximage" src="/files/tex/890e2fb3c09c6d51b4f50d8d9fcdccde0c923f9b.png" alt="$ a\sim b \Rightarrow b\sim a $" /></p> <p>(ii)<img class="teximage" src="/files/tex/b1a28f0bc1282a0efa46d796fcd35f07713c0e0f.png" alt="$ a\sim b \quad and \quad b\sim c \Rightarrow a\sim c $" /></p> <p>A relation <img class="teximage" src="/files/tex/201b5ff8bf9045c34a583adc2741b00adf1fd14c.png" alt="$ R $" /> together with a set <img class="teximage" src="/files/tex/06d9f8dd53868a1233f15c435c46e03deb17a82a.png" alt="$ [n] $" /> is a set of unordered pairs denoted by <img class="teximage" src="/files/tex/6f426e00823dbeca041586e699a9aeccf52e0b4a.png" alt="$ ([n],R) $" />. Consider the example <img class="teximage" src="/files/tex/32b774d199829010006ffe06ee870f3a60e5ac5f.png" alt="$ ([n],R_1)=\{(1,2),(2,3),(4,12),(6,7)\} $" />. This is extendable to <img class="teximage" src="/files/tex/de417f419b99e482ab4b72e307426319335c964d.png" alt="$ ([n],R_2)=\{(1,2),(2,3),(1,3),(4,12),(6,7)\} $" />. In this case we call <img class="teximage" src="/files/tex/26de9e4dac29b9527fc26c6c6578fe500c525a8e.png" alt="$ R_1 $" /> to be equivalent to <img class="teximage" src="/files/tex/4851de2433a48ffc5546d6b2c5965921bfde2e87.png" alt="$ R_2 $" /> (over <img class="teximage" src="/files/tex/06d9f8dd53868a1233f15c435c46e03deb17a82a.png" alt="$ [n] $" />).(This defines a equivalence relation over the set of relations) Two relations are called distinct if they are not equivalent.</p> <p>Let <img class="teximage" src="/files/tex/266f9253994faeb0e092d3796a5f5db50c050fdf.png" alt="$ R_1,\dots,R_k $" /> be all the equivalent relations. A set <img class="teximage" src="/files/tex/0f265286df50c7093eb7a4675b0b51d5b5f9be9c.png" alt="$ ([n],R_i) \quad \forall 1\leq i\leq k $" /> is said to be a minimal relation iff there does not exist a relation <img class="teximage" src="/files/tex/a33f8d5268f0485be2a01fd1f51d7d89c8ad50c2.png" alt="$ R_j $" /> which is extendable to <img class="teximage" src="/files/tex/e4f5df8b4fc28463abb475a5f20b56d62c99929e.png" alt="$ R_i $" />.</p> <p>1.Do all minimum relations among <img class="teximage" src="/files/tex/266f9253994faeb0e092d3796a5f5db50c050fdf.png" alt="$ R_1,\dots,R_k $" /> have same cardinality ie., same number of pairs?</p> <p>2.Find the number of distinct relations</p> <p>(i) when points are numbered</p> <p>(ii) Upto isomorphism.</p> <p>ps: I am a newcomer to this garden and newcomer to research too. Admin please move to relevant section if problem is not appropriate for this section.</p> </tr></td> </table> </td> </tr> </table> Combinatorics http://openproblemgarden.org/op/enumerating_the_number_of_binary_relations#comment Sun, 16 Mar 2008 14:09:08 +0100 arbitrary 747 at http://openproblemgarden.org