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-~~19 18~~:02:16 UTC</tt>.<br>

: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:03:57 UTC</tt>.<br>

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

: The original revision id was <tt>358748103</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 14:

=Connectivity=

We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be //connected// if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ~~λ(G)~~ if it is possible to disconnect the graph by removing ~~λ(G)~~ edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ~~κ(G)~~ if it is possible to disconnect the graph by removing ~~κ(G)~~ vertices (notes of the scale) but no smaller number will do. The graph is //k-edge-connected// if ~~λ(G)~~ ≥ k, and //k-vertex-connected// if ~~κ(G)~~ ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.

We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be //connected// if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ε if it is possible to disconnect the graph by removing ε edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ν if it is possible to disconnect the graph by removing ν vertices (notes of the scale) but no smaller number will do. The graph is //k-edge-connected// if ε ≥ k, and //k-vertex-connected// if ν ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.

A [[http://en.wikipedia.org/wiki/Clique_(graph_theory)|clique]] in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a [[dyadic chord]]. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale. The various problems of this nature are called, collectively, the [[http://en.wikipedia.org/wiki/Clique_problem|clique problem]], and this unfortunately is computationally hard. However, for scales of the size most people would care to consider a brute-force approach suffices.

Line 26:

=The Laplace Spectrum=

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The vertex-connectivity ~~κ(G)~~ is ~~greater~~ than or equal to the algebraic connectivity.

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices.

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.

Line 43:

Line 45:

The edges leading from the four outer vertices wrap around to the opposite side, creating the torus embedding. On the other hand, a tetrad is of genus 0, since it can be drawn on a sphere as the verticies of a tetrahedron.

If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V>2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree of valency is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2

If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V>2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree of valency is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2</pre></div>

</pre></div>

<h4>Original HTML content:</h4>

<div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Graph-theoretic properties of scales</title></head><body><a href="#Graph of a scale">Graph of a scale</a> | <a href="#Connectivity">Connectivity</a> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a> | <a href="#The Genus">The Genus</a>

Line 54:

Line 55:

<br />

<h1 id="toc1"><a name="Connectivity"></a>Connectivity</h1>

We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be <em>connected</em> if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ~~λ(G)~~ if it is possible to disconnect the graph by removing ~~λ(G)~~ edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ~~κ(G)~~ if it is possible to disconnect the graph by removing ~~κ(G)~~ vertices (notes of the scale) but no smaller number will do. The graph is <em>k-edge-connected</em> if ~~λ(G)~~ ≥ k, and <em>k-vertex-connected</em> if ~~κ(G)~~ ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.<br />

We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be <em>connected</em> if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ε if it is possible to disconnect the graph by removing ε edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ν if it is possible to disconnect the graph by removing ν vertices (notes of the scale) but no smaller number will do. The graph is <em>k-edge-connected</em> if ε ≥ k, and <em>k-vertex-connected</em> if ν ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.<br />

<br />

A <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="nofollow">clique</a> in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a <a class="wiki_link" href="/dyadic%20chord">dyadic chord</a>. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale. The various problems of this nature are called, collectively, the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Clique_problem" rel="nofollow">clique problem</a>, and this unfortunately is computationally hard. However, for scales of the size most people would care to consider a brute-force approach suffices.<br />

Line 66:

Line 67:

<br />

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

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the <em>Laplace matrix</em> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em>Laplace spectrum</em>. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member of the Laplace spectrum, which is therefore positive iff G is connected, is called the <em>algebraic connectivity</em>. The vertex-connectivity ~~κ(G)~~ is ~~greater~~ than or equal to the algebraic connectivity.<br />

If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the <em>Laplace matrix</em> of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the <em>Laplace spectrum</em>. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the <em>algebraic connectivity</em>. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices. <br />

<br />

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.<br />

<br />

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.<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-19 18:02:16 UTC</tt>.<br>
+: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-20 11:03:57 UTC</tt>.<br>
-: The original revision id was <tt>358627615</tt>.<br>
+: The original revision id was <tt>358748103</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 14: / Line 14: @@
 =Connectivity=
-We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be //connected// if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity λ(G) if it is possible to disconnect the graph by removing λ(G) edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity κ(G) if it is possible to disconnect the graph by removing κ(G) vertices (notes of the scale) but no smaller number will do. The graph is //k-edge-connected// if λ(G) ≥ k, and //k-vertex-connected// if κ(G) ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.
+We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be //connected// if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ε if it is possible to disconnect the graph by removing ε edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ν if it is possible to disconnect the graph by removing ν vertices (notes of the scale) but no smaller number will do. The graph is //k-edge-connected// if ε ≥ k, and //k-vertex-connected// if ν ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.
 A [[http://en.wikipedia.org/wiki/Clique_(graph_theory)|clique]] in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a [[dyadic chord]]. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale. The various problems of this nature are called, collectively, the [[http://en.wikipedia.org/wiki/Clique_problem|clique problem]], and this unfortunately is computationally hard. However, for scales of the size most people would care to consider a brute-force approach suffices.
@@ Line 26: / Line 26: @@
 =The Laplace Spectrum=
-If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.
+If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the //Laplace matrix// of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the //Laplace spectrum//. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the //algebraic connectivity//. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices.
+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.
@@ Line 43: / Line 45: @@
 The edges leading from the four outer vertices wrap around to the opposite side, creating the torus embedding. On the other hand, a tetrad is of genus 0, since it can be drawn on a sphere as the verticies of a tetrahedron.
-If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V&gt;2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree of valency is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2
+If V is the number of notes (vertices) of the scale, and E the number of dyads (edges), then the maximum value for E is C(V, 2) = V(V - 1)/2. This suggests the definition for [[http://en.wikipedia.org/wiki/Dense_graph|graph density]], 2E/(V(V-1)). Since the maximum number of edges for a genus 0 graph with V&gt;2 is 3V - 6, the maximum density for a genus 0 graph is 6(V-2)/(V(V-1)) whih has series expansion 6/V - 6/V^2 - 6/V^3 ...; if the density is 6/V or greater the graph must be of a higher genus, hence, higher genus scales are to be expected in music. If each note is harmonically related to at least three other notes, an obviously desirable property which in graph-theoretic language means the minimum degree of valency is greater than two, then the genus g ≥ E/6 - V/2 + 1. On the other hand, for a connected graph we have g ≤ (E - V + 1)/2</pre></div>
-</pre></div>
 <h4>Original HTML content:</h4>
 <div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html">&lt;html&gt;&lt;head&gt;&lt;title&gt;Graph-theoretic properties of scales&lt;/title&gt;&lt;/head&gt;&lt;body&gt;&lt;!-- ws:start:WikiTextTocRule:10:&amp;lt;img id=&amp;quot;wikitext@@toc@@flat&amp;quot; class=&amp;quot;WikiMedia WikiMediaTocFlat&amp;quot; title=&amp;quot;Table of Contents&amp;quot; src=&amp;quot;/site/embedthumbnail/toc/flat?w=100&amp;amp;h=16&amp;quot;/&amp;gt; --&gt;&lt;!-- ws:end:WikiTextTocRule:10 --&gt;&lt;!-- ws:start:WikiTextTocRule:11: --&gt;&lt;a href="#Graph of a scale"&gt;Graph of a scale&lt;/a&gt;&lt;!-- ws:end:WikiTextTocRule:11 --&gt;&lt;!-- ws:start:WikiTextTocRule:12: --&gt; | &lt;a href="#Connectivity"&gt;Connectivity&lt;/a&gt;&lt;!-- ws:end:WikiTextTocRule:12 --&gt;&lt;!-- ws:start:WikiTextTocRule:13: --&gt; | &lt;a href="#The Characteristic Polynomial"&gt;The Characteristic Polynomial&lt;/a&gt;&lt;!-- ws:end:WikiTextTocRule:13 --&gt;&lt;!-- ws:start:WikiTextTocRule:14: --&gt; | &lt;a href="#The Laplace Spectrum"&gt;The Laplace Spectrum&lt;/a&gt;&lt;!-- ws:end:WikiTextTocRule:14 --&gt;&lt;!-- ws:start:WikiTextTocRule:15: --&gt; | &lt;a href="#The Genus"&gt;The Genus&lt;/a&gt;&lt;!-- ws:end:WikiTextTocRule:15 --&gt;&lt;!-- ws:start:WikiTextTocRule:16: --&gt;
@@ Line 54: / Line 55: @@
 &lt;br /&gt;
 &lt;!-- ws:start:WikiTextHeadingRule:2:&amp;lt;h1&amp;gt; --&gt;&lt;h1 id="toc1"&gt;&lt;a name="Connectivity"&gt;&lt;/a&gt;&lt;!-- ws:end:WikiTextHeadingRule:2 --&gt;Connectivity&lt;/h1&gt;
-We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be &lt;em&gt;connected&lt;/em&gt; if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity λ(G) if it is possible to disconnect the graph by removing λ(G) edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity κ(G) if it is possible to disconnect the graph by removing κ(G) vertices (notes of the scale) but no smaller number will do. The graph is &lt;em&gt;k-edge-connected&lt;/em&gt; if λ(G) ≥ k, and &lt;em&gt;k-vertex-connected&lt;/em&gt; if κ(G) ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.&lt;br /&gt;
+We can attribute various properties to a scale, given a choice of consonance set, by the presence of a graph-theoretic property in the graph of the scale. One key graph-theoretic property is connectivity. A graph is said to be &lt;em&gt;connected&lt;/em&gt; if for any two vertices a and b, there is a path of edges between a and b. A scale is therefore connected if you can go from any one note to any other note by means of consonant intervals only. The graph G has an edge-connectivity ε if it is possible to disconnect the graph by removing ε edges, but no smaller number of edges will do. Similarly, it has vertex-connectivity ν if it is possible to disconnect the graph by removing ν vertices (notes of the scale) but no smaller number will do. The graph is &lt;em&gt;k-edge-connected&lt;/em&gt; if ε ≥ k, and &lt;em&gt;k-vertex-connected&lt;/em&gt; if ν ≥ k; these definitions transfer immediately to scales, and a high degree of connectivity may often be desired in a scale.&lt;br /&gt;
 &lt;br /&gt;
 A &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="nofollow"&gt;clique&lt;/a&gt; in a graph is a subgraph such that there is an edge connecting every vertex; that is, the subgraph is a complete graph. In music terms, a clique is a &lt;a class="wiki_link" href="/dyadic%20chord"&gt;dyadic chord&lt;/a&gt;. Hence, counting cliques of various degrees (number of notes) is a relevant consideration when analyzing a scale. The various problems of this nature are called, collectively, the &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Clique_problem" rel="nofollow"&gt;clique problem&lt;/a&gt;, and this unfortunately is computationally hard. However, for scales of the size most people would care to consider a brute-force approach suffices.&lt;br /&gt;
@@ Line 66: / Line 67: @@
 &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;
-If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the &lt;em&gt;Laplace matrix&lt;/em&gt; of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the &lt;em&gt;Laplace spectrum&lt;/em&gt;. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member of the Laplace spectrum, which is therefore positive iff G is connected, is called the &lt;em&gt;algebraic connectivity&lt;/em&gt;. The vertex-connectivity κ(G) is greater than or equal to the algebraic connectivity.&lt;br /&gt;
+If D is the diagonal matrix [Dij], with Dii being the degree of the ith vertex--that is, the number of edges connecting to that vertex--then L = D - A is called the &lt;em&gt;Laplace matrix&lt;/em&gt; of the graph G, and its eigenvalues (roots of its characteristic polynomial) is the &lt;em&gt;Laplace spectrum&lt;/em&gt;. The matrix L is positive-semidefinite; the Laplace spectrum has at least one zero value, with the other values real and non-negative; the number of zero values in the Laplace spectrum is equal to the number of connected components of G, and so there is just one iff G is connected. The second smallest member λ of the Laplace spectrum, which is therefore positive iff G is connected, is called the &lt;em&gt;algebraic connectivity&lt;/em&gt;. The various kinds of connectivity are related by the inequality λ ≤ ν ≤ ε; that is the algebraic connectivity is less than or equal to the vertex connectivity, which is less than or equal to the edge connectivity. In the other direction, λ ≥ 2(1 - cos(π/V))ε, where V is the number of vertices. &lt;br /&gt;
+&lt;br /&gt;
+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;