Eulerian and Hamiltonian scales

A traversable or Eulerian graph is a graph which has a circuit--a path
staring and ending at the same point--which traverses each edge
exactly once. A Hamiltonian graph is a graph with a circuit whice
visits each node exactly once. Given an octave-equivalent scale, we
can form the q-odd-limit graph of the scale by making the degrees of
the scale the nodes, and the consonances of the scale the edges. If
the resulting graph is Eulerian or Hamiltonian, we can say the scale
is Eulerian or Hamiltonian in the q-limit.

A graph is Eulerian if and only if each vertex is of even degree,
which means in scale terms each degree connects with an even number of
other degrees. An example of an Eulerian scale is the hexany, where
each degree connects with four others.

A Hamiltonian scale has a tone row where each succesive element of the
row is related via a consonance to the last, including the last to the
first again.

http://mathworld.wolfram.com/EulerianGraph.html

http://mathworld.wolfram.com/EulerianCircuit.html

http://en.wikipedia.org/wiki/Eulerian_graph

http://mathworld.wolfram.com/HamiltonianGraph.html

http://mathworld.wolfram.com/HamiltonianCircuit.html

http://en.wikipedia.org/wiki/Hamiltonian_graph

>A traversable or Eulerian graph is a graph which has a circuit--a
path
>staring and ending at the same point--which traverses each edge
>exactly once. A Hamiltonian graph is a graph with a circuit whice
>visits each node exactly once. Given an octave-equivalent scale, we
>can form the q-odd-limit graph of the scale by making the degrees of
>the scale the nodes, and the consonances of the scale the edges. If
>the resulting graph is Eulerian or Hamiltonian, we can say the scale
>is Eulerian or Hamiltonian in the q-limit.
>
>A graph is Eulerian if and only if each vertex is of even degree,
>which means in scale terms each degree connects with an even number
>of other degrees. An example of an Eulerian scale is the hexany,
>where each degree connects with four others.
>
>A Hamiltonian scale has a tone row where each succesive element of
>the row is related via a consonance to the last, including the last
>to the first again.

The former of these doesn't seem particularly relevant to music
theory.

-Carl

--- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:

> >A graph is Eulerian if and only if each vertex is of even degree,
> >which means in scale terms each degree connects with an even number
> >of other degrees. An example of an Eulerian scale is the hexany,
> >where each degree connects with four others.

> >A Hamiltonian scale has a tone row where each succesive element of
> >the row is related via a consonance to the last, including the last
> >to the first again.
>
> The former of these doesn't seem particularly relevant to music
> theory.

I agree Hamiltonian is more interesting. Aside from the tone-row
business, you might try reordering a Hamiltonian scale according to
the circuit. Alas, seeing if a graph is Hamiltonian is a hard problem,
whereas seeing if it is Eulerian is trivial.

>>>A Hamiltonian scale has a tone row where each succesive element
>>>of the row is related via a consonance to the last, including
>>>the last to the first again.
//
>I agree Hamiltonian is more interesting. Aside from the tone-row
>business, you might try reordering a Hamiltonian scale according
>to the circuit. Alas, seeing if a graph is Hamiltonian is a hard
>problem, whereas seeing if it is Eulerian is trivial.

I thought a speedup c/b taken from the fact that if a pair of notes
is consonant with respect to a third note, they are consonant with
one another. But it looks like you still have to test all the paths.
If a scale is a Hamiltonian you can often find out early, but this
isn't particularly comforting.

I have eight lines of Scheme that can return all permutations of
ten things in less than 15 seconds on my new, whiz-bang computer.
But it my interpreter mysteriously quits after about 30 seconds of
working on eleven things. :( I don't remember noticing this
before....

It might be easier to create Hamiltonian scales.

-Carl

--- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:

> It might be easier to create Hamiltonian scales.

Aside from trying for that, another interesting thing to do is to
solve the travelling salesman problem for the given scale and some
metric. A Travelling Tenney Salesman is one idea, but something
invariant as to octaves is probably better. There are programs out
there which do travelling salesmen problems, so I will see if I can
get my hands on one. Anyone else, of course, is welcome to try also,
especially if they have a new, nifty computer to play with.

>> It might be easier to create Hamiltonian scales.
>
>Aside from trying for that, another interesting thing to do is to
>solve the travelling salesman problem for the given scale and some
>metric. A Travelling Tenney Salesman is one idea, but something
>invariant as to octaves is probably better. There are programs out
>there which do travelling salesmen problems, so I will see if I can
>get my hands on one. Anyone else, of course, is welcome to try
>also, especially if they have a new, nifty computer to play with.

I thought about travelling salesman, since it is obviously
related, but I couldn't think of a musical tie-in.

-Carl

--- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:

> I thought about travelling salesman, since it is obviously
> related, but I couldn't think of a musical tie-in.

I'm thinking that a salesman route might be an interesting thing to
use to order a scale.

However, thinking about the traveling salesman problem got me to
thinking about using simulated annealing to adaptively temper a piece.
Simulated annealing (a bizarre name which makes you think it is about
a computer simulation in materials science, which is not the case but
which is what I thought for years back in the 80s) is a global
optimization algorithm which has been applied now for decades with
great success in some situations and about which whole books have been
written. I've never used it, but it occurs to me that reducing the
global mistuning of a piece of music is what adaptive tuning attempts
to do, and simulated annealing is a classic method for global
optimization which I presume works, since people keep using it. There
are also other global optimization methods out there, and one of those
might be better, for all I know.

>However, thinking about the traveling salesman problem got me to
>thinking about using simulated annealing to adaptively temper a piece.
>Simulated annealing (a bizarre name which makes you think it is about
>a computer simulation in materials science, which is not the case but
>which is what I thought for years back in the 80s) is a global
>optimization algorithm which has been applied now for decades with
>great success in some situations and about which whole books have been
>written. I've never used it, but it occurs to me that reducing the
>global mistuning of a piece of music is what adaptive tuning attempts
>to do, and simulated annealing is a classic method for global
>optimization which I presume works, since people keep using it. There
>are also other global optimization methods out there, and one of those
>might be better, for all I know.

The term is a nod to materials science -- the ancient technique of
annealing metal.

Paul's entropy minimizer stuff is worth mentioning here, but he
was using it to find scales, not retune music files. What process
do you have in mind?

-Carl

> I'm thinking that a salesman route might be an
> interesting thing to use to order a scale.

How would this work? TSP is all about economy
of travel. Why punish a scale for having too
much consonance?

It seems to me Hahn diameter is a more natural
candidate. This is real graph diameter, as
opposed to what I think you've been donig lately,
which is minimax hahn distance from 1/1 to each note.

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <ekin@l...> wrote:

> Paul's entropy minimizer stuff is worth mentioning here, but he
> was using it to find scales, not retune music files. What process
> do you have in mind?

The idea is that you would have to come up with a number which
expressed the deviation from optimality over the whole piece both
horizontally and vertically, as a function of the tuning of each of
the notes in the piece, and then we would would want to optimize this
function. These kinds of high dimension optimizations are not easy,
but they can be done. Whether such a system could be made pratical I
don't know.

--- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:

> > I'm thinking that a salesman route might be an
> > interesting thing to use to order a scale.
>
> How would this work? TSP is all about economy
> of travel. Why punish a scale for having too
> much consonance?

I'm not trying to punish consonance, I'm trying to find a circuit
which maximizes it.

>> Paul's entropy minimizer stuff is worth mentioning here, but he
>> was using it to find scales, not retune music files. What process
>> do you have in mind?
>
>The idea is that you would have to come up with a number which
>expressed the deviation from optimality over the whole piece both
>horizontally and vertically, as a function of the tuning of each of
>the notes in the piece, and then we would would want to optimize this
>function. These kinds of high dimension optimizations are not easy,
>but they can be done. Whether such a system could be made pratical I
>don't know.

Have you checked out John deLaubenfels' stuff?

-Carl

hi Gene,

--- In tuning-math@yahoogroups.com, "Gene Ward Smith" <gwsmith@s...>
wrote:

> --- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:
>
> > > I'm thinking that a salesman route might be an
> > > interesting thing to use to order a scale.
> >
> > How would this work? TSP is all about economy
> > of travel. Why punish a scale for having too
> > much consonance?
>
> I'm not trying to punish consonance, I'm trying to find a circuit
> which maximizes it.

we went thru a really big discussion, several years ago,
before you joined the tuning lists, and decided that we
should use "accordance" as the measure of an interval's
independent relative roughness/smoothness, reserving
"sonance" for the relative roughness/smoothness of an
interval dependent on its compositional context.

thus, "consonance" here should be replaced with
"concordance" (whose opposite is "discordance").

the reason for the distinction is that a composer may
use a relatively concordant interval in a way which
makes it seem dissonant, and vice versa.

a simple example: a composer may use pythagorean tuning
in such a way that the discordant "ditone" (monzo [-6 4,>
= ratio 81/64) is perceived as a wide "major-3rd"
consonance.

in fact, 12edo is used like this all the time, where
the relatively discordant 2^(4/12) is very often intended
by the composer to be perceived as a consonant "major-3rd".

-monz

--- In tuning-math@yahoogroups.com, "Carl Lumma" <ekin@l...> wrote:

> Have you checked out John deLaubenfels' stuff?

I'd like to get the code, but no luck so far.

> we went thru a really big discussion, several years ago,
> before you joined the tuning lists, and decided that we
> should use "accordance" as the measure of an interval's
> independent relative roughness/smoothness, reserving
> "sonance" for the relative roughness/smoothness of an
> interval dependent on its compositional context.

We did?

-Carl