## [SOLVED] mathematical structure

<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">&nbsp;&nbsp;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 $R^2,$ but the
set G consists (using the standard cartesian coordinates $on R^2)$ only
of parametrized paths such that if $dx/dt!=0,$ then $dy/dt=0,$ and if
$dy/dt!=0,$ then $dx/dt=0$. 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.

 PhysOrg.com science news on PhysOrg.com >> Intel's Haswell to extend battery life, set for Taipei launch>> Galaxies fed by funnels of fuel>> The better to see you with: Scientists build record-setting metamaterial flat lens


"Blake Winter" 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



On Thu, 04 Nov 2004 09:40:17 $+0000,$ 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 $R^2,$ but the set G consists > (using the standard cartesian coordinates $on R^2)$ only of parametrized > paths such that if $dx/dt!=0,$ then $dy/dt=0,$ and if $dy/dt!=0,$ then $dx/dt=0$. > Such a system would be hard to describe in anothery way. In this case $R^2$ 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 $R^2$. 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

## [SOLVED] mathematical structure

<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">&nbsp;&nbsp;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
$\aleph-0$ or perhaps a higher $\aleph)$. 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



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)