Continuous graph

Continuous graph

A continuous graph is a graph whose set of vertices is a continuous space X. Edges are then defined by a function from the cartesian product X2 to the set {0, 1}. This could represent 1 for an edge between two vertices, and 0 for no edge, or it could represent a complete graph with a 2-color edge coloring. In this context, the set {0,1} is often denoted by 2, so we have f(X2)→2. For multi-colorings of edges we would have f(X2)→n.[1][2][3] Continuous graphs have applications to peer-to-peer systems.[4]

A graph limit or graphon is the limit of a sequence of graphs. Such a limit is a symmetric measurable function in two variables[5], that can often be written f(S2)→[0,1] which is the same as a complete continuous graph where the edges have values in the interval [0,1].

For any sets X and Y, the two-variable function f(X2)→Y is a complete graph with edges labelled with elements of Y. For multi-variable functions we have f(Xn)→Y for the complete hypergraph with edges labelled with elements of Y.[6]

Given a discrete-time dynamical system, the trajectories, or orbits (state space) of all the points form a (possibly disconnected) directed graph which is a continuous graph if the system is defined on a continuous space. The trajectories of a continuous-time dynamical system would form a collection of curved paths (phase space) rather than a collection of piece-wise linear paths and so is not a graph in the traditional sense.

See also

References

  1. ^ CONTINUOUS GRAPHS AND C*-ALGEBRAS, VALENTIN DEACONU, Operator theoretical methods: 17th International Conference on Operator Theory, Timișoara (Romania), July 23-26, 1998, ISBN 978-973-99097-2-3.
  2. ^ CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS, STEFAN GESCHKE, MARTIN GOLDSTERN, AND MENACHEM KOJMAN, Journal of Mathematical Logic, 2004.
  3. ^ INFINITE RAMSEY THEORY, STEFAN GESCHKE.
  4. ^ Novel architectures for P2P applications: the continuous-discrete approach, M Naor, U Wieder - ACM Transactions on Algorithms (TALG), 2007.
  5. ^ Graph Limits and Parameter Testing, Christian Borgs, Jennifer Chayes, László Lovász, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 2006
  6. ^ Testability and repair of hereditary hypergraph properties, T Austin, T Tao - Random Structures and Algorithms, 2010