[SOLVED] mathematical structure

Blake Winter

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no,location=no, scrollbars=yes,resizable=yes,status=no,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>This might be more applicable to a math forum, but there should be\nplenty of mathematical minded people here, so I\'ll ask anyway:\n\nIs there a branch of mathematics or anyone who has studied the\nfollowing: Take a set S of points (of arbitrary cardinality). Then,\ntake a set G whose elements are ordered subsets of S. These sets may\nbe continous if S is continous, but they need not be. Call the set G\nthe set of paths (and note that G need not contain all possible\nordered subsets of S).\n\nIn a certain limit where S is finite and no members of G are\ncontinous, it seems like one would get back something very like graph\ntheory, and with a few more restrictions on G one would actually have\ngraph theory. So it strikes me that perhaps this is a sort of a\ngeneralization of graph theory.\n\nIt also seems to me like one could study objects which can\'t be\ndescribed by other means: consider for example if S is R^2, but the\nset G consists (using the standard cartesian coordinates on R^2) only\nof parametrized paths such that if dx/dt!=0, then dy/dt=0, and if\ndy/dt!=0, then dx/dt=0. Such a system would be hard to describe in\nanothery way.\n\nSo, does anyone know if this has been studied previously? I think it\nmight possibly provide a framework in which one can naturally embed\nthe graphs mentioned in Smolin and Markopoulou\'s paper\n(www.arxiv.org/abs/gr-qc/0311059) into a continous manifold, without\nassuming that the continous manifold arises only as an approximation.\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>This might be more applicable to a math forum, but there should be
plenty of mathematical minded people here, so I'll ask anyway:

Is there a branch of mathematics or anyone who has studied the
following: Take a set S of points (of arbitrary cardinality). Then,
take a set G whose elements are ordered subsets of S. These sets may
be continous if S is continous, but they need not be. Call the set G
the set of paths (and note that G need not contain all possible
ordered subsets of S).

In a certain limit where S is finite and no members of G are
continous, it seems like one would get back something very like graph
theory, and with a few more restrictions on G one would actually have
graph theory. So it strikes me that perhaps this is a sort of a
generalization of graph theory.

It also seems to me like one could study objects which can't be
described by other means: consider for example if S is [itex]R^2,[/itex] but the
set G consists (using the standard cartesian coordinates [itex]on R^2)[/itex] only
of parametrized paths such that if [itex]dx/dt!=0,[/itex] then [itex]dy/dt=0,[/itex] and if
[itex]dy/dt!=0,[/itex] then [itex]dx/dt=0[/itex]. Such a system would be hard to describe in
anothery way.

So, does anyone know if this has been studied previously? I think it
might possibly provide a framework in which one can naturally embed
the graphs mentioned in Smolin and Markopoulou's paper
(www.arxiv.org/abs/http://www.arxiv.org/abs/gr-qc/0311059) into a continous manifold, without
assuming that the continous manifold arises only as an approximation.

Eugene Shubert

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no,location=no, scrollbars=yes,resizable=yes,status=no,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>"Blake Winter" <blake.winter@houghton.edu> wrote in message\nnews:87423d2a.0411031012.2b3df754@posting.google.com...\n> Is there a branch of mathematics or anyone who has studied the\n> following: Take a set S of points (of arbitrary cardinality). Then,\n> take a set G whose elements are ordered subsets of S.\n\nAny set can be "well-ordered" but what ordering do you have in mind?\n\n> These sets may be continous if S is continous, but they need not be.\n\nWhat do you mean? In topology one can decide if functions are\ncontinuous, not sets. If you\'re talking about connectedness, you still\nneed to define a topology. Which topology do you have in mind?\n\nEugene Shubert\nhttp://www.everythingimportant.org/relativity/special.pdf\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>"Blake Winter" <blake.winter@houghton.edu> wrote in message
news:87423d2a.0411031012.2b3df754@posting.google.com...
> Is there a branch of mathematics or anyone who has studied the
> following: Take a set S of points (of arbitrary cardinality). Then,
> take a set G whose elements are ordered subsets of S.

Any set can be "well-ordered" but what ordering do you have in mind?

> These sets may be continous if S is continous, but they need not be.

What do you mean? In topology one can decide if functions are
continuous, not sets. If you're talking about connectedness, you still
need to define a topology. Which topology do you have in mind?

Eugene Shubert
http://www.everythingimportant.org/r...ty/special.pdf

Igor Khavkine

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no,location=no, scrollbars=yes,resizable=yes,status=no,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>\n\n\nOn Thu, 04 Nov 2004 09:40:17 +0000, Blake Winter wrote:\n\n> This might be more applicable to a math forum, but there should be plenty\n> of mathematical minded people here, so I\'ll ask anyway:\n>\n> Is there a branch of mathematics or anyone who has studied the following:\n> Take a set S of points (of arbitrary cardinality). Then, take a set G\n> whose elements are ordered subsets of S. These sets may be continous if S\n> is continous, but they need not be. Call the set G the set of paths (and\n> note that G need not contain all possible ordered subsets of S).\n\nOrder (partial order) and continuity (topology) must be specified\nexternally for an arbitrary set S. What you are describing sounds very\nmuch like a "causal set", but you are being very vague and ambiguous about\nit.\n\n> In a certain limit where S is finite and no members of G are continous, it\n> seems like one would get back something very like graph theory, and with a\n> few more restrictions on G one would actually have graph theory. So it\n> strikes me that perhaps this is a sort of a generalization of graph\n> theory.\n\nIf S is finite, then there is no need to take a limit, it can be\nconstructed directly.\n\n> It also seems to me like one could study objects which can\'t be described\n> by other means: consider for example if S is R^2, but the set G consists\n> (using the standard cartesian coordinates on R^2) only of parametrized\n> paths such that if dx/dt!=0, then dy/dt=0, and if dy/dt!=0, then dx/dt=0.\n> Such a system would be hard to describe in anothery way.\n\nIn this case R^2 is neither finite nor ordered, so it doesn\'t really fit\nthe model you are trying to build. What you specified is a subset of the\nset of curves in R^2. What other way would you want to describe it?\n\n> So, does anyone know if this has been studied previously? I think it\n> might possibly provide a framework in which one can naturally embed the\n> graphs mentioned in Smolin and Markopoulou\'s paper\n> (www.arxiv.org/abs/gr-qc/0311059) into a continous manifold, without\n> assuming that the continous manifold arises only as an approximation.\n\nThe point of such discrete approximations is exactly to reproduce the\ngeometry of a smooth manifold in some limit. Unfortunately, many\ndiscrete models, including causal sets, do not approach any smooth\nmanifold in the desired limit.\n\nIgor\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>On Thu, 04 Nov 2004 09:40:17 [itex]+0000,[/itex] Blake Winter wrote:

> This might be more applicable to a math forum, but there should be plenty
> of mathematical minded people here, so I'll ask anyway:
>
> Is there a branch of mathematics or anyone who has studied the following:
> Take a set S of points (of arbitrary cardinality). Then, take a set G
> whose elements are ordered subsets of S. These sets may be continous if S
> is continous, but they need not be. Call the set G the set of paths (and
> note that G need not contain all possible ordered subsets of S).

Order (partial order) and continuity (topology) must be specified
externally for an arbitrary set S. What you are describing sounds very
much like a "causal set", but you are being very vague and ambiguous about
it.

> In a certain limit where S is finite and no members of G are continous, it
> seems like one would get back something very like graph theory, and with a
> few more restrictions on G one would actually have graph theory. So it
> strikes me that perhaps this is a sort of a generalization of graph
> theory.

If S is finite, then there is no need to take a limit, it can be
constructed directly.

> It also seems to me like one could study objects which can't be described
> by other means: consider for example if S is [itex]R^2,[/itex] but the set G consists
> (using the standard cartesian coordinates [itex]on R^2)[/itex] only of parametrized
> paths such that if [itex]dx/dt!=0,[/itex] then [itex]dy/dt=0,[/itex] and if [itex]dy/dt!=0,[/itex] then [itex]dx/dt=0[/itex].
> Such a system would be hard to describe in anothery way.

In this case [itex]R^2[/itex] is neither finite nor ordered, so it doesn't really fit
the model you are trying to build. What you specified is a subset of the
set of curves in [itex]R^2[/itex]. What other way would you want to describe it?

> So, does anyone know if this has been studied previously? I think it
> might possibly provide a framework in which one can naturally embed the
> graphs mentioned in Smolin and Markopoulou's paper
> (www.arxiv.org/abs/http://www.arxiv.org/abs/gr-qc/0311059) into a continous manifold, without
> assuming that the continous manifold arises only as an approximation.

The point of such discrete approximations is exactly to reproduce the
geometry of a smooth manifold in some limit. Unfortunately, many
discrete models, including causal sets, do not approach any smooth
manifold in the desired limit.

Igor

Blake Winter

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no,location=no, scrollbars=yes,resizable=yes,status=no,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>After seeing the first couple responses, I realize I didn\'t describe\nthis well at all. So let me try again.\n\nOne can, if one wishes, talk about a graph by taking a set S, whose\nelements are called nodes, and then taking a set E consisting of pairs\nof nodes, whose elements are called edges. An ordered graph has the\nset E consisting of pairs of ordered nodes.\nOne would get back graph theory if, instead of considering pairs of\nnodes, one considered all the possible paths through the graph (if I\'m\nrecalling my graph theory terminology correctly here). From listing\nall the possible paths through the graph, one could reconstruct the\nset E. However, if one only lists possible paths, some interesting\nthings are possible: for example, given nodes a, b, and c, one could\nhave a path (a,b,c) but no path (a,b), if one wished. This wouldn\'t\nbe a graph, of course, but something different.\n\nSo, what I was wondering if anyone has studied a mathematical\nstructure where, instead of a graph where the set S is usually taken\nto be finite, we allow S to be any set of any cardinality (even\naleph-0 or perhaps a higher aleph). The paths would then be subsets\nof S, some of which we might list (a,b,...,n), but others would only\nbe able to be expressed as parameterized functions. In any case, this\nstruck me as an interesting generalization of graph theory and I\nwondered if anyone had studied it previously.\nI hope this explanation is better than my last one. Thanks\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>After seeing the first couple responses, I realize I didn't describe
this well at all. So let me try again.

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. 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. However, if one only lists possible paths, some interesting
things are possible: for example, given nodes a, b, and c, one could
have a path (a,b,c) but no path (a,b), if one wished. This wouldn't
be a graph, of course, but something different.

So, what I was wondering if anyone has studied a mathematical
structure where, instead of a graph where the set S is usually taken
to be finite, we allow S to be any set of any cardinality (even
[itex]\aleph-0[/itex] or perhaps a higher [itex]\aleph)[/itex]. The paths would then be subsets
of S, some of which we might list (a,b,...,n), but others would only
be able to be expressed as parameterized functions. In any case, this
struck me as an interesting generalization of graph theory and I
wondered if anyone had studied it previously.
I hope this explanation is better than my last one. Thanks

tessel@tum.bot

<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no,location=no, scrollbars=yes,resizable=yes,status=no,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>On Sat, 6 Nov 2004, Blake Winter wrote:\n\n> One can, if one wishes, talk about a graph by taking a set S, whose\n> elements are called nodes, and then taking a set E consisting of pairs\n> of nodes, whose elements are called edges.\n\nI didn\'t understand your question, but I get the impression you are\ncurious and open to learning cool stuff involving graphs, so below I will\ntry to point you at some fascinating connections (challenging, but\naccessible to well-prepared undergraduates) between graphs and other neat\nthings you may have heard of, or may even know well.\n\nDo you know about the categorical description of a digraph (possibly with\nmultiple edges from one node to another)? Consider a model category with\nobjects E, V and two nontrivial arrows head, tail. Then cofunctors\n\nE <== V\nF | | F\nv v\nFE ==> FV\n\ndefine finite digraphs, and every finite digraph can be obtained this way!\nFor, we can interpret FE as the set of edges, FV as the set of vertices,\nand the morphism Fhead assigns to each e in FE the vertex which e enters,\nand Ftail assigns to each e in FE the vertex which e leaves.\n\nFor background on functors between categories, try\n\nauthor = {John C. Baez and James Dolan},\ntitle ={From Finite Sets to {F}eynman Diagrams},\nnote = {math.QA/0004133},\nbooktitle = {Mathematics Unlimited: 2000 and Beyond},\neditor = {Bj\\"orn Engquist and Wilfried Schmid},\npublisher = {Springer-Verlag},\nyear = 2000}\n\nauthor = {F. William Lawvere and Stephen H. Schanuel},\ntitle = {Conceptual mathematics : a first introduction to categories},\npublisher = {Cambridge University Press},\nyear = 1997}\n\nauthor = {Colin McLarty},\ntitle = {Elementary Categories, Elementary Toposes},\npublisher = {Oxford Science Publications},\nyear = 1995}\n\nFrom these resources you can find out why cofunctors are preferrable here\nto functors, etc. You can also look for various past posts here by Baez &\nco.\n\nA readable monograph on the categorification of generating functions (see\nBaez & Dolan above for the general idea) is:\n\nauthor = {F. Bergeron and G. Labelle and P. Leroux},\ntitle = {Combinatorial species and tree-like structures},\npublisher = {Cambridge University Press},\nyear = 1998}\n\nSee also\n\nauthor = {Peter J. Cameron},\ntitle = {Some counting problems related to permutation groups},\njournal = {Discrete Mathematics},\nvolume = 225,\nyear = 2000,\npages = {75--92},\nnote = {http://www.maths.qmul.ac.uk/~pjc/papers.html}}\n\nCompare\n\nauthor = {Herbert S. Wilf},\ntitle = {Generating functionology},\npublisher = {Academic Press},\nedition = {second},\nyear = 1994}\n\nWe\'ve discussed species extensively in the past.\n\n> An ordered graph has the set E consisting of pairs of ordered nodes. One\n> would get back graph theory if, instead of considering pairs of nodes,\n> one considered all the possible paths through the graph (if I\'m\n> recalling my graph theory terminology correctly here). From listing all\n> the possible paths through the graph, one could reconstruct the set E.\n\nI think you -are- misremembering something. But you might be thinking of\nsome problem involving reconstructing possible sizes of FV (the vertex\nset) from partial information concerning the paths, e.g. a "generating\nfunction" giving the number of paths of length n for each positive integer\nn, or a list of -closed- paths, etc. The latter is analogous to listing\nthe prime factors of an integer! A useful buzzword here is "zeta\nfunction".\n\nSee:\n\nauthor = {J. C. Lagarias},\ntitle = {Number Theory and Dynamical Systems},\nbooktitle = {The Unreasonable Effectiveness of Number Theory},\neditor = {Burr, Stefan A.},\nseries = {Proceedings of Symposia in Applied Mathematics},\nvolume = 46,\npublisher = {American Mathematical Society},\naddress = {Providence, Rhode Island},\nyear = 1991}\n\nauthor = {Olle Haggstrom},\ntitle = {Finite {M}arkov chains and algorithmic applications},\nseries = {London Mathematical Society student texts},\nvolume = 52,\npublisher = {Cambridge University Press},\nyear = 2002}\n\nauthor = {M. Pollicott and M. Yuri},\ntitle = {Ergodic Theory and Dynamical Systems},\npublisher = {London Mathematical Society},\nseries = {Student Texts},\nnumber = 40,\nyear = 1998}\n\nauthor = {Swinnerton-Dyer, H. P. F},\ntitle = {A brief guide to algebraic number theory},\npublisher = {Cambridge University Press},\nseries = {London Mathematical Society student texts}\nvolume = 50,\nyear = 2001}\n\nthe first half of the UG textbook\n\nauthor = {Douglas Lind and Brian Marcus},\ntitle = {Introduction to Symbolic Dynamics and Coding},\npublisher = {Cambridge University Press},\nyear = 1995}\n\nand\n\nauthor = {Pollicott, Mark},\ntitle = {Closed geodesics and zeta functions},\nbooktitle = {Ergodic theory, symbolic dynamics, and hyperbolic spaces},\neditor = {Tim Bedford and Michael Keane and Caroline Series},\npublisher = {Oxford University Press},\nyear = 1991,\npages = {153--174}}\n\n> I hope this explanation is better than my last one.\n\nWell, I didn\'t understand your question as posed in this post. I missed\nthe previous one, so I can\'t say if your exposition has improved :-/\n\nBut if you are interested in how things change when we pass from finite to\ncountable graphs, the theory of random graphs is one of the most\nfascinating examples. One basic phenomenon which arises is easily\ndiscussed: if you pick a finite graph at random, chances are that its\nautomorphism group are very small, in fact trivial. And if you pick\nanother finite graph at random, chances are the two graphs are not\nisomorphic. But you replace "finite" by "countable", a.e. every countable\nrandom graph turns out to be isomorphic to a specific countable graph (the\nErdos/Renyi/Turan graph), and this has a large automorphism group! The\nproof of Erdos is ingenious but elementary.\n\nFor more information, see the chapters on random graphs in:\n\nauthor = {Bollob\\\'as, B\\\'ela},\ntitle = {Modern Graph Theory},\nseries = {Graduate texts in mathematics},\nvolume = 184,\npublisher = {Springer-Verlag},\nyear = 1998}\n\nauthor = {Peter J. Cameron},\ntitle = {Permutation Groups},\npublisher = {Cambridge University Press},\nseries = {London Mathematical Society student texts},\nvolume = 45,\nyear = 1998}\n\n(these authors emphasize different aspects of a big topic, so both are\nwell worth reading).\n\nThere are nifty connections with first-order logic; see Cameron\'s book\nabove and also\n\nauthor = {Joel Spencer},\ntitle = {The Strange Logic of Random Graphs},\npublisher = {Springer},\nseries = {Algorithms and combinatorics},\nyear = 22,\nyear = 2001}\n\nFor larger cardinalities, you might also be intrigued by the work of\nShelah; his papers are challenging (see the ArXiV) but you can try this\nexpository paper:\n\nauthor = {Wilfrid Hodges},\ntitle = {What is a Structure Theory?},\njournal = {Bulletin of the London Mathematical Society},\nvolume = 19,\nyear = 1987,\npages = {209--237}}\n\nBack to finite graphs (undirected edges): there are also nifty and useful\nconnections with commutative algebra, if you know what that is. For\nbackground, see\n\nauthor = {David A. Cox and John Little and Donal O\'Shea},\ntitle = {Ideals, Varieties, and Algorithms},\nseries = {Undergraduate texts in mathematics},\nedition = {Second},\npublisher = {Springer-Verlag},\nyear = 1992}\n\nand then see the discussion of "Stanley-Reissner rings" in\n\nauthor = {Hal Schenck},\ntitle = {Computational Algebraic Geometry},\npublisher = {Cambridge University Press},\nyear = 2003}\n\neditor = {David Eisenbud},\ntitle = {Computations in algebraic geometry with {M}acaulay 2},\npublisher = {Springer},\nyear = 2002}\n\nYou might also be interested in this book, which involves some of the\nstuff mentioned above, and is useful in current work toward analysis of\ncomputer networks, etc.:\n\nauthor = { Guiliana Davidoff and Peter Sarnak and Alain Valette},\ntitle = {Elementary Number Theory, Group Theory,\nand {R}amanujan graphs},\npublisher = {Cambridge University Press},\nseries = {London Mathematical Society student texts},\nvolume = 55,\nyear = 2003}\n\nOK, so there are close interrelationships between graphs, digraphs and\n\n* automorphism groups (permutation groups)\n* generating functions (combinatorics)\n* first order logic\n* homological algebra (commutative algebra)\n* Markov chains (dynamical systems)\n* number theory\n* networks\n* category theory\n\nThere is of course much much more, but I\'ve said more than enough to get\ninterested readers started on a glorious journey. Enjoy!\n\n"T. Essel" (hiding somewhere in cyberspace)\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form">  View this Usenet post in original ASCII form </a></div><P></jabberwocky>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
[itex]F | | F[/itex]
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 [itex]={From[/itex] Finite Sets to {F}eynman Diagrams},
note = {math.[itex]QA/0004133},[/itex]
booktitle = {Mathematics Unlimited: 2000 and Beyond},
editor [itex]= {Bj\[/itex]"orn Engquist and Wilfried Schmid},
publisher = {Springer-Verlag},
year [itex]= 2000}[/itex]

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

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

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 [itex]= {F[/itex]. Bergeron and G. Labelle and P. Leroux},
title = {Combinatorial species and tree-like structures},
publisher = {Cambridge University Press},
year [itex]= 1998}[/itex]

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 [itex]= 1994}[/itex]

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 "[itex]\zeta[/itex]
function".

See:

author [itex]= {J[/itex]. 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 [itex]= 46,[/itex]
publisher = {American Mathematical Society},
address = {Providence, Rhode Island},
year [itex]= 1991}[/itex]

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

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

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

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 [itex]= 1995}[/itex]

and

author = {Pollicott, Mark},
title = {Closed geodesics and [itex]\zeta[/itex] 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 [itex]= {Bollob\'as, B\'ela},[/itex]
title = {Modern Graph Theory},
series = {Graduate texts in mathematics},
volume = 184,
publisher = {Springer-Verlag},
year [itex]= 1998}[/itex]

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

(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 [itex]= 22,[/itex]
year [itex]= 2001}[/itex]

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 [itex]= 19,[/itex]
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 [itex]= 1992}[/itex]

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

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

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

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 [itex]= 55,[/itex]
year [itex]= 2003}[/itex]

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)

Similar Threads for: [SOLVED] mathematical structure
Thread	Forum	Replies
[SOLVED] Secondary structure of protein.	Biology, Chemistry & Other Homework	2
[SOLVED] Resonance Structure #3	Biology, Chemistry & Other Homework	1
[SOLVED] Resonance Structure	Biology, Chemistry & Other Homework	2
QM: mathematical structure?	Math & Science Software	5
Mathematical structure of terrorism	Math & Science Software	6