Computer Science – Discrete Mathematics
Scientific paper
2008-03-03
Computer Science
Discrete Mathematics
103 pages, french
Scientific paper
Hypergraphs are structures that can be decomposed or described; in other words they are recursively countable. Here, we get exact and asymptotic enumeration results on hypergraphs by means of exponential generating functions. The number of hypergraph component is bounded, as a generalisation of Wright inequalities for graphs: the proof is a combinatorial understanding of the structure by inclusion exclusion. Asymptotic results are obtained, thanks to generating functions proofs are at the end very easy to read, through complex analysis by saddle point method. By this way, we characterized: - the components with a given number of vertices and of hyperedges by the expected size of a random hypermatching in these structures. - the random hypergraphs (evolving hyperedge by hyperedge) according to the expected number of hyperedges when the first cycle appears in the evolving structure. This work is an open road to further works on random hypergraphs such as threshold phenomenon, tools used here seem to be sufficient at first sight.
No associations
LandOfFree
Random hypergraphs and algorithmics 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 Random hypergraphs and algorithmics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random hypergraphs and algorithmics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-225334