Graph-theoretic properties of scales: Difference between revisions
Wikispaces>genewardsmith **Imported revision 358548817 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 358607273 - Original comment: ** |
||
| Line 1: | Line 1: | ||
<h2>IMPORTED REVISION FROM WIKISPACES</h2> | <h2>IMPORTED REVISION FROM WIKISPACES</h2> | ||
This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | 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 | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-08-19 15:24:18 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>358607273</tt>.<br> | ||
: The revision comment was: <tt></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> | The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | ||
| Line 16: | Line 16: | ||
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 λ(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. | ||
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. | 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. | ||
=The Characteristic Polynomial= | =The Characteristic Polynomial= | ||
| Line 33: | Line 33: | ||
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 //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.</pre></div> | 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. | ||
A 5-limit scale, meaning a scale composed of 5-limit 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.)</pre></div> | |||
<h4>Original HTML content:</h4> | <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><!-- ws:start:WikiTextTocRule:10:&lt;img id=&quot;wikitext@@toc@@flat&quot; class=&quot;WikiMedia WikiMediaTocFlat&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/flat?w=100&amp;h=16&quot;/&gt; --><!-- ws:end:WikiTextTocRule:10 --><!-- ws:start:WikiTextTocRule:11: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:11 --><!-- ws:start:WikiTextTocRule:12: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:12 --><!-- ws:start:WikiTextTocRule:13: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:13 --><!-- ws:start:WikiTextTocRule:14: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:14 --><!-- ws:start:WikiTextTocRule:15: --> | <a href="#The Genus">The Genus</a><!-- ws:end:WikiTextTocRule:15 --><!-- ws:start:WikiTextTocRule:16: --> | <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><!-- ws:start:WikiTextTocRule:10:&lt;img id=&quot;wikitext@@toc@@flat&quot; class=&quot;WikiMedia WikiMediaTocFlat&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/flat?w=100&amp;h=16&quot;/&gt; --><!-- ws:end:WikiTextTocRule:10 --><!-- ws:start:WikiTextTocRule:11: --><a href="#Graph of a scale">Graph of a scale</a><!-- ws:end:WikiTextTocRule:11 --><!-- ws:start:WikiTextTocRule:12: --> | <a href="#Connectivity">Connectivity</a><!-- ws:end:WikiTextTocRule:12 --><!-- ws:start:WikiTextTocRule:13: --> | <a href="#The Characteristic Polynomial">The Characteristic Polynomial</a><!-- ws:end:WikiTextTocRule:13 --><!-- ws:start:WikiTextTocRule:14: --> | <a href="#The Laplace Spectrum">The Laplace Spectrum</a><!-- ws:end:WikiTextTocRule:14 --><!-- ws:start:WikiTextTocRule:15: --> | <a href="#The Genus">The Genus</a><!-- ws:end:WikiTextTocRule:15 --><!-- ws:start:WikiTextTocRule:16: --> | ||
| Line 45: | Line 47: | ||
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 λ(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 /> | ||
<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.<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 /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:4:&lt;h1&gt; --><h1 id="toc2"><a name="The Characteristic Polynomial"></a><!-- ws:end:WikiTextHeadingRule:4 -->The Characteristic Polynomial</h1> | <!-- ws:start:WikiTextHeadingRule:4:&lt;h1&gt; --><h1 id="toc2"><a name="The Characteristic Polynomial"></a><!-- ws:end:WikiTextHeadingRule:4 -->The Characteristic Polynomial</h1> | ||
| Line 62: | Line 64: | ||
A graph is <em>planar</em> 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 <em>planar</em> 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 /> | ||
<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.</body></html></pre></div> | 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.<br /> | ||
<br /> | |||
A 5-limit scale, meaning a scale composed of 5-limit 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.)</body></html></pre></div> | |||