Re: mathematical structure

tessel_at_tum.bot
Date: 11/08/04 

Date: Mon, 8 Nov 2004 23:09:42 +0000 (UTC)

On Sat, 6 Nov 2004, Blake Winter wrote:

> One can, if one wishes, talk about a graph by taking a set S, whose
> elements are called nodes, and then taking a set E consisting of pairs
> of nodes, whose elements are called edges.

I didn't understand your question, but I get the impression you are
curious and open to learning cool stuff involving graphs, so below I will
try to point you at some fascinating connections (challenging, but
accessible to well-prepared undergraduates) between graphs and other neat
things you may have heard of, or may even know well.

Do you know about the categorical description of a digraph (possibly with
multiple edges from one node to another)? Consider a model category with
objects E, V and two nontrivial arrows head, tail. Then cofunctors

        E <== V
      F | | F
        v v
              FE ==> FV

define finite digraphs, and every finite digraph can be obtained this way!
For, we can interpret FE as the set of edges, FV as the set of vertices,
and the morphism Fhead assigns to each e in FE the vertex which e enters,
and Ftail assigns to each e in FE the vertex which e leaves.

For background on functors between categories, try

author = {John C. Baez and James Dolan},
title ={From Finite Sets to {F}eynman Diagrams},
note = {math.QA/0004133},
booktitle = {Mathematics Unlimited: 2000 and Beyond},
editor = {Bj\"orn Engquist and Wilfried Schmid},
publisher = {Springer-Verlag},
year = 2000}

author = {F. William Lawvere and Stephen H. Schanuel},
title = {Conceptual mathematics : a first introduction to categories},
publisher = {Cambridge University Press},
year = 1997}

author = {Colin McLarty},
title = {Elementary Categories, Elementary Toposes},
publisher = {Oxford Science Publications},
year = 1995}

>From these resources you can find out why cofunctors are preferrable here
to functors, etc. You can also look for various past posts here by Baez &
co.

A readable monograph on the categorification of generating functions (see
Baez & Dolan above for the general idea) is:

author = {F. Bergeron and G. Labelle and P. Leroux},
title = {Combinatorial species and tree-like structures},
publisher = {Cambridge University Press},
year = 1998}

See also

author = {Peter J. Cameron},
title = {Some counting problems related to permutation groups},
journal = {Discrete Mathematics},
volume = 225,
year = 2000,
pages = {75--92},
note = {http://www.maths.qmul.ac.uk/~pjc/papers.html}}

Compare

author = {Herbert S. Wilf},
title = {Generating functionology},
publisher = {Academic Press},
edition = {second},
year = 1994}

We've discussed species extensively in the past.

> An ordered graph has the set E consisting of pairs of ordered nodes. One
> would get back graph theory if, instead of considering pairs of nodes,
> one considered all the possible paths through the graph (if I'm
> recalling my graph theory terminology correctly here). From listing all
> the possible paths through the graph, one could reconstruct the set E.

I think you -are- misremembering something. But you might be thinking of
some problem involving reconstructing possible sizes of FV (the vertex
set) from partial information concerning the paths, e.g. a "generating
function" giving the number of paths of length n for each positive integer
n, or a list of -closed- paths, etc. The latter is analogous to listing
the prime factors of an integer! A useful buzzword here is "zeta
function".

See:

author = {J. C. Lagarias},
title = {Number Theory and Dynamical Systems},
booktitle = {The Unreasonable Effectiveness of Number Theory},
editor = {Burr, Stefan A.},
series = {Proceedings of Symposia in Applied Mathematics},
volume = 46,
publisher = {American Mathematical Society},
address = {Providence, Rhode Island},
year = 1991}

author = {Olle Haggstrom},
title = {Finite {M}arkov chains and algorithmic applications},
series = {London Mathematical Society student texts},
volume = 52,
publisher = {Cambridge University Press},
year = 2002}

author = {M. Pollicott and M. Yuri},
title = {Ergodic Theory and Dynamical Systems},
publisher = {London Mathematical Society},
series = {Student Texts},
number = 40,
year = 1998}

author = {Swinnerton-Dyer, H. P. F},
title = {A brief guide to algebraic number theory},
publisher = {Cambridge University Press},
series = {London Mathematical Society student texts}
volume = 50,
year = 2001}

the first half of the UG textbook

author = {Douglas Lind and Brian Marcus},
title = {Introduction to Symbolic Dynamics and Coding},
publisher = {Cambridge University Press},
year = 1995}

and

author = {Pollicott, Mark},
title = {Closed geodesics and zeta functions},
booktitle = {Ergodic theory, symbolic dynamics, and hyperbolic spaces},
editor = {Tim Bedford and Michael Keane and Caroline Series},
publisher = {Oxford University Press},
year = 1991,
pages = {153--174}}

> I hope this explanation is better than my last one.

Well, I didn't understand your question as posed in this post. I missed
the previous one, so I can't say if your exposition has improved :-/

But if you are interested in how things change when we pass from finite to
countable graphs, the theory of random graphs is one of the most
fascinating examples. One basic phenomenon which arises is easily
discussed: if you pick a finite graph at random, chances are that its
automorphism group are very small, in fact trivial. And if you pick
another finite graph at random, chances are the two graphs are not
isomorphic. But you replace "finite" by "countable", a.e. every countable
random graph turns out to be isomorphic to a specific countable graph (the
Erdos/Renyi/Turan graph), and this has a large automorphism group! The
proof of Erdos is ingenious but elementary.

For more information, see the chapters on random graphs in:

author = {Bollob\'as, B\'ela},
title = {Modern Graph Theory},
series = {Graduate texts in mathematics},
volume = 184,
publisher = {Springer-Verlag},
year = 1998}

author = {Peter J. Cameron},
title = {Permutation Groups},
publisher = {Cambridge University Press},
series = {London Mathematical Society student texts},
volume = 45,
year = 1998}

(these authors emphasize different aspects of a big topic, so both are
well worth reading).

There are nifty connections with first-order logic; see Cameron's book
above and also

author = {Joel Spencer},
title = {The Strange Logic of Random Graphs},
publisher = {Springer},
series = {Algorithms and combinatorics},
year = 22,
year = 2001}

For larger cardinalities, you might also be intrigued by the work of
Shelah; his papers are challenging (see the ArXiV) but you can try this
expository paper:

author = {Wilfrid Hodges},
title = {What is a Structure Theory?},
journal = {Bulletin of the London Mathematical Society},
volume = 19,
year = 1987,
pages = {209--237}}

Back to finite graphs (undirected edges): there are also nifty and useful
connections with commutative algebra, if you know what that is. For
background, see

author = {David A. Cox and John Little and Donal O'Shea},
title = {Ideals, Varieties, and Algorithms},
series = {Undergraduate texts in mathematics},
edition = {Second},
publisher = {Springer-Verlag},
year = 1992}

and then see the discussion of "Stanley-Reissner rings" in

author = {Hal Schenck},
title = {Computational Algebraic Geometry},
publisher = {Cambridge University Press},
year = 2003}

editor = {David Eisenbud},
title = {Computations in algebraic geometry with {M}acaulay 2},
publisher = {Springer},
year = 2002}

You might also be interested in this book, which involves some of the
stuff mentioned above, and is useful in current work toward analysis of
computer networks, etc.:

author = { Guiliana Davidoff and Peter Sarnak and Alain Valette},
title = {Elementary Number Theory, Group Theory,
and {R}amanujan graphs},
publisher = {Cambridge University Press},
series = {London Mathematical Society student texts},
volume = 55,
year = 2003}

OK, so there are close interrelationships between graphs, digraphs and

  * automorphism groups (permutation groups)
  * generating functions (combinatorics)
  * first order logic
  * homological algebra (commutative algebra)
  * Markov chains (dynamical systems)
  * number theory
  * networks
  * category theory

There is of course much much more, but I've said more than enough to get
interested readers started on a glorious journey. Enjoy!

"T. Essel" (hiding somewhere in cyberspace)

Relevant Pages

  • Re: the correct program
    ... Excel and pasting it into either Publisher or Word. ... There are ranges of data, bar graphs, sometimes pie graphs and it's ... These marketing people just want to make a professional looking report and it ... you might be well off creating a report in Excel. ...
    (microsoft.public.publisher)
  • Re: the correct program
    ... from Excel and pasting it into either Publisher or Word. ... There are ranges of data, bar graphs, sometimes pie graphs and it's ... The whole report is compiled currently in Publisher and finally sent to ...
    (microsoft.public.publisher)
  • Re: Publisher to PDF
    ... I have a publisher document which contains a number of ... When i convert it to PDF the labels on X axis of the graphs ... the UNDERSCORE nerd AT mvps DOT org ...
    (microsoft.public.publisher)
  • Re: Is it possible to create Graphs and Charts?
    ... Is Publisher capable of creating graphs and charts. ... Excel doesn't give us the professional quality we are trying to achieve. ... Graphs inserted into Publisher have to be created in Excel or another graphing program. ...
    (microsoft.public.publisher)
  • Re: Printing e-newsletter from Outlook
    ... MVP Microsoft [Publisher] ... you to Don Schmidt... ... I'm using a lot of graphs - and prints the text without formatting. ... it does print page one (the way it looks in publisher) then it won't print ...
    (microsoft.public.publisher)