Modèles d'urnes et phénomènes de seuils en combinatoire analytique.

Vincent Puyhaubert 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This thesis is about urn models and threshold phenomena, from the point of view of analytic combinatorics. It adresses three main questions: the phase transition in the k-sat problem, Polya-Eggenberger urn models, and the Ok Corral gunfight model. The k-sat phase transition corresponds to the fact that, considering random formulae, satisfiability is almost surely characterised by the density of the formula only. Our work intends to prove some parts of the satisfiability threshold conjecture, using mainly urn models and random allocations. The Polya-Eggenberger urn model subjects an urn containing balls of different colours to replacement rules. We determine the limit distribution of the composition of the triangular models, using Flajolet-Gabarro-Pekari's method. The Ok Corral gunfight is a special case of a general theory of conflict due to Lanchester. Using a link between this model and an urn of the Polya-Eggenberger type, we derive new expressions for the distribution of probabilities and reffine earlier results of Kingman.
Document type :
Theses
Complete list of metadatas

Cited literature [75 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00001348
Contributor : Ecole Polytechnique <>
Submitted on : Tuesday, July 27, 2010 - 2:24:28 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, October 28, 2010 - 11:31:41 AM

Identifiers

  • HAL Id : pastel-00001348, version 1

Collections

Citation

Vincent Puyhaubert. Modèles d'urnes et phénomènes de seuils en combinatoire analytique.. Combinatoire [math.CO]. Ecole Polytechnique X, 2005. Français. ⟨pastel-00001348⟩

Share

Metrics

Record views

543

Files downloads

1091