Continuous and discontinuous phase transitions in hypergraph processes

Details Continuous and discontinuous phase transitions in hypergraph processes Continuous and discontinuous phase transitions in hypergraph processes

2003-12-24

arxiv.org/abs/math/0312451v2

Mathematics

Probability

25 pages, 2 figures. Revised version. To appear in Random Structures & Algorithms

Scientific paper

Let V denote a set of N vertices. To construct a "hypergraph process", create a new hyperedge at each event time of a Poisson process; the cardinality K of this hyperedge is random, with arbitrary probability generating function r(x), except that we assume P(K=1) +P(K=2) > 0. Given K=k, the k vertices appearing in the new hyperedge are selected uniformly at random from V. Hyperedges of cardinality 1 are called patches, and serve as a way of selecting root vertices. Identifiable vertices are those which are reachable from these root vertices, in a strong sense which generalizes the notion of graph component. Hyperedges are also called identifiable if all of their vertices are identifiable. We use "fluid limit" scaling: hyperedges arrive at rate N, and we study structures of size O(1) and O(N). After division by N, numbers of identifiable vertices and reducible hyperedges exhibit phase transitions, which may be continuous or discontinuous depending on the shape of the structure function -log(1 - x)/r'(x), for x in (0,1). Both the case P(K=1) > 0 and the case P(K=1) = 0 < P(K=2) are considered; for the latter, a single extraneous patch is added to mark the root vertex.

Affiliated with

Also associated with

No associations

Rating

Continuous and discontinuous phase transitions in hypergraph processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Continuous and discontinuous phase transitions in hypergraph processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Continuous and discontinuous phase transitions in hypergraph processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-625120