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:

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-~~20 14~~:55:05 UTC</tt>.

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

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

: The original revision id was <tt>359125703</tt>.

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

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

Line 21:

The [[http://en.wikipedia.org/wiki/Adjacency_matrix|adjacency matrix]] A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The [[http://en.wikipedia.org/wiki/Characteristic_polynomial|characteristic polynomial]] of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale.

These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/n, where n is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/n divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.

These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.

The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of n-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.

The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of V-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.

=The Laplace Spectrum=

Line 30:

We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.

The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.

The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to V, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.

=The Genus=

A graph is //~~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". 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.

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.

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 67:

The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Characteristic_polynomial" rel="nofollow">characteristic polynomial</a> of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale.

These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The spectrum of G is the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow">multiset</a> of roots, including multipicities, so that some roots may be repeated. From <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow">Newton's identities</a> we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace. Since tr(A^2)/n, where n is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/n divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.

These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The spectrum of G is the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow">multiset</a> of roots, including multipicities, so that some roots may be repeated. From <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow">Newton's identities</a> we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &quot;tr&quot; denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.

The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of n-1. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow">distance</a> between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow">diameter</a> of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.

The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of V-1. The <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow">distance</a> between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the <a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow">diameter</a> of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.

<h1 id="toc3"><a name="The Laplace Spectrum"></a>The Laplace Spectrum</h1>

Line 76:

We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.

The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.

The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to V, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.

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

A graph is 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 <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.

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.

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.

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.

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

@@ 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-20 14:55:05 UTC</tt>.<br>
+: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-22 01:11:49 UTC</tt>.<br>
-: The original revision id was <tt>358793441</tt>.<br>
+: The original revision id was <tt>359125703</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 21: / Line 21: @@
 The [[http://en.wikipedia.org/wiki/Adjacency_matrix|adjacency matrix]] A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The [[http://en.wikipedia.org/wiki/Characteristic_polynomial|characteristic polynomial]] of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale.
-These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/n, where n is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/n divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.
+These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The //spectrum// of G is the [[http://en.wikipedia.org/wiki/Multiset|multiset]] of roots, including multipicities, so that some roots may be repeated. From [[http://en.wikipedia.org/wiki/Newton's_identities|Newton's identities]] we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where "tr" denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.
-The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of n-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.
+The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of V-1. The [[http://en.wikipedia.org/wiki/Distance_(graph_theory)|distance]] between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the [[http://mathworld.wolfram.com/GraphDiameter.html|diameter]] of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.
 =The Laplace Spectrum=
@@ Line 30: / Line 30: @@
 We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.
-The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.
+The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to V, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.
 =The Genus=
-A graph is //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". 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.
+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.
 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 67: / Line 67: @@
 The &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow"&gt;adjacency matrix&lt;/a&gt; A of a graph is the square symmetric matrix with zeros on the diagonal, with 1 at the (i, j) place if the ith vertex is connected to the jth vertex, and 0 if it is not. The &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Characteristic_polynomial" rel="nofollow"&gt;characteristic polynomial&lt;/a&gt; of a graph is the characteristic polynomial det(xI - A) of its adjacency matrix, and is a property (graph invariant) of the graph alone, without consideration of how the vertices are numbered. The degree n-1 term is 0, the n-2 term is minus the number of edges of the graph and therefore dyads of the scale, and the n-3 term minus twice the number of triads (3-cliques) in the graph and therefore the scale. &lt;br /&gt;
 &lt;br /&gt;
-These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The &lt;em&gt;spectrum&lt;/em&gt; of G is the &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow"&gt;multiset&lt;/a&gt; of roots, including multipicities, so that some roots may be repeated. From &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow"&gt;Newton's identities&lt;/a&gt; we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &amp;quot;tr&amp;quot; denotes the trace. Since tr(A^2)/n, where n is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/n divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.&lt;br /&gt;
+These properties can be also expressed in terms of the roots of the characteristic polynomial, which are the eigenvalues of the matrix. These roots are real numbers, some of which may be multiple. The &lt;em&gt;spectrum&lt;/em&gt; of G is the &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Multiset" rel="nofollow"&gt;multiset&lt;/a&gt; of roots, including multipicities, so that some roots may be repeated. From &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Newton's_identities" rel="nofollow"&gt;Newton's identities&lt;/a&gt; we can also say that the sum of the squares of the spectrum is twice the number of edges of the graph, which means twice the number of dyads of the scale, and the sum of the cubes of the spectrum is six times the number of triads of the scale. In terms of the adjacency matrix A, the number of dyads is tr(A^2)/2 and the number of triads is tr(A^3)/6, where &amp;quot;tr&amp;quot; denotes the trace. Since tr(A^2)/V, where V is the degree (number of notes) is the variance of the spectrum, we can see we prefer the variance to be larger rather than smaller. Also, tr(A^3)/V divided by the 3/2 power of the variance is the skewness of the spectrum, from which we can conclude we want the skewness to skew positive.&lt;br /&gt;
 &lt;br /&gt;
-The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of n-1. The &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow"&gt;distance&lt;/a&gt; between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the &lt;a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow"&gt;diameter&lt;/a&gt; of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.&lt;br /&gt;
+The epitome of these properties is found in the complete graph, which in scale terms means every note is in consonant relation with every other--in other words, the scale is a dyadic chord. This has a spectrum with n-1 values of -1 and one of V-1. The &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow"&gt;distance&lt;/a&gt; between two vertices (notes) is the number of edges (consonant intervals) of the shortest path between then, and the &lt;a class="wiki_link_ext" href="http://mathworld.wolfram.com/GraphDiameter.html" rel="nofollow"&gt;diameter&lt;/a&gt; of a graph is the length of the greatest distance between two vertices. The diameter of a compete graph is 1, and in general a small diameter is another desirable quality. A graph with diameter d must have at least d+1 distinct values in the spectrum.&lt;br /&gt;
 &lt;br /&gt;
 &lt;!-- ws:start:WikiTextHeadingRule:6:&amp;lt;h1&amp;gt; --&gt;&lt;h1 id="toc3"&gt;&lt;a name="The Laplace Spectrum"&gt;&lt;/a&gt;&lt;!-- ws:end:WikiTextHeadingRule:6 --&gt;The Laplace Spectrum&lt;/h1&gt;
@@ Line 76: / Line 76: @@
 We can also relate the diameter d to the algebraic connectivity, since 4/(Vλ) ≤ d ≤ 2((Δ+λ)/4λ)ln(V-1), where Δ is the maximal degree of the vertices of G. Also, if ρ is the mean distance, meaning the average of all of the distances in G, then 2/((V-1)λ) + (V-2)/(2(V-1)) ≤ ρ ≤ (V/(V-1))((Δ+λ)/4λ)ln(V-1). Hence when λ is small, distances will be large.&lt;br /&gt;
 &lt;br /&gt;
-The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to n, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.&lt;br /&gt;
+The sum of the Laplace spectrum, which is tr(L), is twice the number of edges (dyads.) Just as with the ordinary spectrum, the Laplace spectrum has at least d+1 distinct values for a graph of diameter d. The largest value in the Laplace spectrum is less than or equal to V, the degree of the graph, meaning the size of the scale; and is equal iff the complementary graph is disconnected, where the complementary graph is the graph of non-consonant relations, that is, the graph which has an edge between two vertices iff G doesn't.&lt;br /&gt;
 &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;em&gt;planar&lt;/em&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;. 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.&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;
 &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;