It seems that undirected graphs with diameter 1 are considered

"complete" graphs. It's easy to generate these at any card k.

They all have edge connectivity k-1. So the problem of finding

all k-card chords in the n-limit may be equivalent to finding

all the orientations of the complete order-k graph in the n-

limit lattice.

And this may be equivalent to finding all the 1-diameter order-k

subgraphs of the n-limit lattice (when the lattice is a directed

graph). Or maybe directedness isn't what we want to use to

differentiate the edges of the lattice. There's also a concept

called "weighting" -- weighted graphs are called "networks".

-Carl

BTW- On the topic of using edge connectivity to evaluate scales...

While it is impressive that connectivitiy is sufficient to select

the diatonic scale from all 7-tone meantones, the results may not

be so impressive when k is closer to card(n) (in the 5-limit,

card(n) is only 3, while k=7 for the diatonic scale). After all,

we're not claiming that things like harmonics 6-12 are our

favorite 11-limit scales (actually, I like this scale a lot, but

I seem to be alone in this opinion around here...). A more

important property of the diatonic scale may be that it has several

weakly-connected, complete subgraphs. As weakly connecteded as

they can be, and still be so numerous and in-tune, I could argue.

Of course this is nothing new; we've been using "chord coverage"

for years, and chords/notes is practically what this list is about.

But if we can put this stuff into graph-theory terms, we may be

able to use the many powerful existing tools out there to soup-up

our searches.

-Carl

--- In tuning-math@y..., "clumma" <carl@l...> wrote:

> But if we can put this stuff into graph-theory terms, we may be

> able to use the many powerful existing tools out there to soup-up

> our searches.

You might also reverse the process, and try to see what a graph theory concept means in scale terms. Things such as the chromatic number, domination number, genus and so forth strike me as interesting in that way.

>>But if we can put this stuff into graph-theory terms, we may be

>>able to use the many powerful existing tools out there to soup-up

>>our searches.

>

>You might also reverse the process, and try to see what a graph

>theory concept means in scale terms. Things such as the chromatic

>number, domination number, genus and so forth strike me as

>interesting in that way.

I bet! There seeems to be no shortage of terms in this field.

I didn't actually run across domination number or genus. I

did see chromatic number, but didn't stop to read the def. I'll

go back and get these -- thanks for the pointers.

So it seems a 1-diameter subgraph is also called a clique? Anyway,

the problem of finding n-limit chords seems related to something

called the Clique Problem. Naturally, the mathematicians are more

interested in wether problems can be done or not than (the usually

much easier problem of) actually finding the answer. . .

"Algorithms for the Maximum Clique Problem

A clique in a graph is a set of vertices which are pairwise

adjacent. The CLIQUE problem is to determine given a graph

G and an integer k, whether G has a k-clique. Although this

problem is NP-complete, several practical algorithms exist."

...'but we're not going to tell you what they are...'

-------

Other promising leads I haven't checked yet:

http://www1.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf

"Approximating Minimum-Size k-Connected Spanning Subgraphs via

Matching", Joseph Cheriyan, Ramakrishna Thurimella.

-Carl

--- In tuning-math@y..., "clumma" <carl@l...> wrote:

> So it seems a 1-diameter subgraph is also called a clique?

Unless the author defines clique to be maximal. The cliques of a graph give us consonant chords in the sense I've been using it on the masses of asses thread.

> A clique in a graph is a set of vertices which are pairwise

> adjacent. The CLIQUE problem is to determine given a graph

> G and an integer k, whether G has a k-clique. Although this

> problem is NP-complete, several practical algorithms exist."

Graph theory is unfortunately a great source of NP-complete problems.

We might look for a graph theory package which does this--Mathematica has a bigger one than Maple, so perhaps I should check that out.

>> A clique in a graph is a set of vertices which are pairwise

>> adjacent. The CLIQUE problem is to determine given a graph

>> G and an integer k, whether G has a k-clique. Although this

>> problem is NP-complete, several practical algorithms exist."

>

>Graph theory is unfortunately a great source of NP-complete

>problems. We might look for a graph theory package which

>does this--Mathematica has a bigger one than Maple, so perhaps

>I should check that out.

It's unclear wether the above author was talking about maximal

cliques, or not. Maximal cliques certainly seem harder than

what we're after.

I have Maple V, from wayback in 1995, which I've never used,

and I finally fired it up, and lo and behold, it doesn't seem

to run on Windows 2000.

It looks like Mathematica actually comes in some affordable

flavors. Those are probably the ones without the graph theory

package. :)

-Carl

--- In tuning-math@y..., "clumma" <carl@l...> wrote:

> I have Maple V, from wayback in 1995, which I've never used,

> and I finally fired it up, and lo and behold, it doesn't seem

> to run on Windows 2000.

Email Waterloo and see if they will upgrade you.

--- In tuning-math@y..., "genewardsmith" <genewardsmith@j...> wrote:

> --- In tuning-math@y..., "clumma" <carl@l...> wrote:

>

> > So it seems a 1-diameter subgraph is also called a clique?

>

> Unless the author defines clique to be maximal. The cliques of a

>graph give us consonant chords in the sense I've been using it on

>the masses of asses thread.

Look up "saturated" in Monz' dictionary -- perhaps this is relevant?

>>> So it seems a 1-diameter subgraph is also called a clique?

>>

>>Unless the author defines clique to be maximal. The cliques of a

>>graph give us consonant chords in the sense I've been using it on

>>the masses of asses thread.

>

>Look up "saturated" in Monz' dictionary -- perhaps this is

>relevant?

The maximal cliques of the n-limit lattice are the n-limit

saturated chords, I think. My problem is to find all the

order-k cliques in the lattice. [Hope I'm not making any

errors here -- I'm an utter neophyte with the graph theory.]

-Carl