Graph-theoretic properties of scales: Difference between revisions

Line 1:

<h2>IMPORTED REVISION FROM WIKISPACES</h2>

This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br>

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 01:13:30 UTC</tt>.<br>

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 01:17:53 UTC</tt>.<br>

: The original revision id was <tt>~~359125841~~</tt>.<br>

: The original revision id was <tt>359126205</tt>.<br>

: The revision comment was: <tt></tt><br>

The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br>

Line 33:

=The Genus=

A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes". If a surface has g holes, it is of [[http://en.wikipedia.org/wiki/Genus_(mathematics)|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph.

A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http://en.wikipedia.org/wiki/Genus_(mathematics)|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph.

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] ~~will~~ manage to finish computing after an acceptable amount of time.

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.

A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the [[http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif|hexagonal lattice]] of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)

Line 79:

<br />

<h1 id="toc4"><a name="The Genus"></a>The Genus</h1>

A graph is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow">planar</a> if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow">compact</a><a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow">orientable</a> <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow">surface</a> with &quot;donut holes&quot;. If a surface has g holes, it is of <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Genus_(mathematics)" rel="nofollow">genus</a> g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. <br />

A graph is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow">planar</a> if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow">compact</a><a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow">orientable</a> <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow">surface</a> with &quot;donut holes&quot;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Genus_(mathematics)" rel="nofollow">genus</a> g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. <br />

<br />

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow">NP-complete</a>. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> ~~will~~ manage to finish computing after an acceptable amount of time.<br />

Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow">NP-complete</a>. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of <a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow">SAGE</a> can manage to finish computing after an acceptable amount of time.<br />

<br />

A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the <a class="wiki_link_ext" href="http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif" rel="nofollow">hexagonal lattice</a> of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)<br />

@@ Line 1: / Line 1: @@
 <h2>IMPORTED REVISION FROM WIKISPACES</h2>
 This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br>
-: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 01:13:30 UTC</tt>.<br>
+: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 01:17:53 UTC</tt>.<br>
-: The original revision id was <tt>359125841</tt>.<br>
+: The original revision id was <tt>359126205</tt>.<br>
 : The revision comment was: <tt></tt><br>
 The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br>
@@ Line 33: / Line 33: @@
 =The Genus=
-A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes". If a surface has g holes, it is of [[http://en.wikipedia.org/wiki/Genus_(mathematics)|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph.
+A graph is [[http://en.wikipedia.org/wiki/Planar_graph|planar]] if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable [[http://en.wikipedia.org/wiki/Compact_space|compact]][[http://en.wikipedia.org/wiki/Orientability|orientable]] [[http://en.wikipedia.org/wiki/Surface|surface]] with "donut holes", which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of [[http://en.wikipedia.org/wiki/Genus_(mathematics)|genus]] g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph.
-Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] will manage to finish computing after an acceptable amount of time.
+Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is [[http://en.wikipedia.org/wiki/NP-complete|NP-complete]]. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of [[http://www.sagemath.org/|SAGE]] can manage to finish computing after an acceptable amount of time.
 A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the [[http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif|hexagonal lattice]] of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)
@@ Line 79: / Line 79: @@
 &lt;br /&gt;
 &lt;!-- ws:start:WikiTextHeadingRule:8:&amp;lt;h1&amp;gt; --&gt;&lt;h1 id="toc4"&gt;&lt;a name="The Genus"&gt;&lt;/a&gt;&lt;!-- ws:end:WikiTextHeadingRule:8 --&gt;The Genus&lt;/h1&gt;
-A graph is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow"&gt;planar&lt;/a&gt; if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow"&gt;compact&lt;/a&gt;&lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow"&gt;orientable&lt;/a&gt; &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow"&gt;surface&lt;/a&gt; with &amp;quot;donut holes&amp;quot;. If a surface has g holes, it is of &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Genus_(mathematics)" rel="nofollow"&gt;genus&lt;/a&gt; g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. &lt;br /&gt;
+A graph is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Planar_graph" rel="nofollow"&gt;planar&lt;/a&gt; if it can be drawn on a plane, or equivalently on a sphere, in such a way that no edges cross. Not all graphs can be drawn without edge crossings on a sphere, but they all can be drawn without crossings on a suitable &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Compact_space" rel="nofollow"&gt;compact&lt;/a&gt;&lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Orientability" rel="nofollow"&gt;orientable&lt;/a&gt; &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Surface" rel="nofollow"&gt;surface&lt;/a&gt; with &amp;quot;donut holes&amp;quot;, which we may view as a closed and bounded surface in 3 dimensional Euclidean space. If a surface has g holes, it is of &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Genus_(mathematics)" rel="nofollow"&gt;genus&lt;/a&gt; g, where the sphere (or plane) has genus 0. The minimum number of holes needed to draw the graph is the genus of the graph. &lt;br /&gt;
 &lt;br /&gt;
-Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow"&gt;NP-complete&lt;/a&gt;. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of &lt;a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow"&gt;SAGE&lt;/a&gt; will manage to finish computing after an acceptable amount of time.&lt;br /&gt;
+Drawing (embedding) the graph on a surface with no crossings would give a nice visual picture of the harmonic relations in a scale. Unfortunately, the problem of determining the genus and finding such an embedding is &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/NP-complete" rel="nofollow"&gt;NP-complete&lt;/a&gt;. However, finding bounds on the genus is a much easier problem. For small enough scales, the genus routine of &lt;a class="wiki_link_ext" href="http://www.sagemath.org/" rel="nofollow"&gt;SAGE&lt;/a&gt; can manage to finish computing after an acceptable amount of time.&lt;br /&gt;
 &lt;br /&gt;
 A 5-limit JI scale, meaning a scale composed of 5-limit JI intervals such that {6/5, 5/4, 4/3, 3/2, 8/5, 5/3} is the consonance set, is always planar. This because the &lt;a class="wiki_link_ext" href="http://xenharmonic.wikispaces.com/file/detail/hexagonal-lattice.gif" rel="nofollow"&gt;hexagonal lattice&lt;/a&gt; of 5-limit pitch classes is planar, and the graph of any scale will simply be a finite subgraph of that lattice, considered as a graph. On the other hand, a non-contorted 5-limit scale in any equal temperament will be of genus 1, since the two commas serve as boundaries for a parallelogram which defines a torus (we can visualize this as rolling it up and glueing ends together.)&lt;br /&gt;