more graph theory terminology

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