Concentration Properties of Extremal Parameters in Random Discrete Structures

Authors :: Michael Drmota
Institut für Diskrete Mathematik und Geometrie [Wien]
Vienna University of Technology (TU Wien)
Chassaing, Philippe and others
Source :: Discrete Mathematics and Theoretical Computer Science, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.1-30
Publication Year :: 2006
Publisher :: episciences.org, 2006.
Abstract: The purpose of this survey is to present recent results concerning concentration properties of extremal parameters of random discrete structures. A main emphasis is placed on the height and maximum degree of several kinds of random trees. We also provide exponential tail estimates for the height distribution of scale-free trees.

Subjects :: Discrete mathematics
General Computer Science
Distribution (number theory)
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
random discrete structures
Theoretical Computer Science
Exponential function
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
concentration inequalities
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Discrete Mathematics and Combinatorics
[INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]
[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
random trees
Mathematics

Language :: English
ISSN :: 14627264 and 13658050
Database :: OpenAIRE
Journal :: Discrete Mathematics and Theoretical Computer Science, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.1-30
Accession number :: edsair.doi.dedup.....cb964cda2edce69d76778bb8c9f6da46

Tools