http://openproblemgarden.org/op/shuffle_exchange_conjecture_graph_theoretic_form Comments for "Shuffle-Exchange Conjecture (graph-theoretic form)" en http://openproblemgarden.org/op/shuffle_exchange_conjecture_graph_theoretic_form <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/bene_vaclav_e">Beneš</a>; <a href="/category/folklore">Folklore</a>; <a href="/category/stone_harold_s">Stone</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Given integers <img class="teximage" src="/files/tex/a9949ee242cd42c24fff3da79661ec0f1ab5ab61.png" alt="$ k,n \ge 2 $" />, the <em>2-stage Shuffle-Exchange graph/network</em>, denoted <img class="teximage" src="/files/tex/03b896cc1ef5041c0c2a8bb1f28cb4ff01bbf2da.png" alt="$ \text{SE}(k,n) $" />, is the simple <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-regular bipartite graph with the ordered pair <img class="teximage" src="/files/tex/c96daced3d733b2b2f60d9c83f2c7e8f58369a2d.png" alt="$ (U,V) $" /> of linearly labeled parts <img class="teximage" src="/files/tex/8ab1db54001afc939c8c13b34266f88deaed6397.png" alt="$ U:=\{u_0,\dots,u_{t-1}\} $" /> and <img class="teximage" src="/files/tex/e60dfbea68ad50dabdd6219bbc20b65aefdb1bba.png" alt="$ V:=\{v_0,\dots,v_{t-1}\} $" />, where <img class="teximage" src="/files/tex/84f251c7218595855078ff39370db5bb03f4cfcc.png" alt="$ t:=k^{n-1} $" />, such that vertices <img class="teximage" src="/files/tex/d128d93e703ab643a5cb38f17e099cc84273e43f.png" alt="$ u_i $" /> and <img class="teximage" src="/files/tex/968028cb10337a37069f12583ee9071a4caff6c1.png" alt="$ v_j $" /> are adjacent if and only if <img class="teximage" src="/files/tex/1b38b14bb429cd4bcd8def829cbe48df863ee80a.png" alt="$ (j - ki) \text{ mod } t &lt; k $" /> (see Fig.1).</p> <p>Given integers <img class="teximage" src="/files/tex/b0d6e9ac8d094e67429f1869126f2cf25468891b.png" alt="$ k,n,r \ge 2 $" />, the <em><img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-stage Shuffle-Exchange graph/network</em>, denoted <img class="teximage" src="/files/tex/cc3f1c4b12aff41fe5fb8fc83fdca203a6ff79dc.png" alt="$ (\text{SE}(k,n))^{r-1} $" />, is the proper (i.e., respecting all the orders) concatenation of <img class="teximage" src="/files/tex/99503535ea75487203d7218ee05f18de44eb9da8.png" alt="$ r-1 $" /> identical copies of <img class="teximage" src="/files/tex/03b896cc1ef5041c0c2a8bb1f28cb4ff01bbf2da.png" alt="$ \text{SE}(k,n) $" /> (see Fig.1). </p> <p>Let <img class="teximage" src="/files/tex/89439aec31f70c82907b7174d89cdee92f6deba0.png" alt="$ r(k,n) $" /> be the smallest integer <img class="teximage" src="/files/tex/611b97d4d3d71f3e2d1d6bba7f92e0e243334893.png" alt="$ r\ge 2 $" /> such that the graph <img class="teximage" src="/files/tex/cc3f1c4b12aff41fe5fb8fc83fdca203a6ff79dc.png" alt="$ (\text{SE}(k,n))^{r-1} $" /> is rearrangeable.</p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Find <img class="teximage" src="/files/tex/89439aec31f70c82907b7174d89cdee92f6deba0.png" alt="$ r(k,n) $" />. </div> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/2b890eb205a3c491b93472737bc3c1b09b1fa787.png" alt="$ r(k,n)=2n-1 $" />. </div> </tr></td> </table> </td> </tr> </table> Beneš, Václav E. Folklore Stone, Harold S. Graph Theory http://openproblemgarden.org/op/shuffle_exchange_conjecture_graph_theoretic_form#comment Fri, 30 Oct 2009 12:03:33 +0100 Vadim Lioubimov 37089 at http://openproblemgarden.org