Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities

Front Matter....Pages i-xv
Front Matter....Pages 1-1
Common Intervals of Permutations....Pages 3-14
Overpartitions and Generating Functions for Generalized Frobenius Partitions....Pages 15-24
Enumerative Results on Integer Partitions Using the ECO Method....Pages 25-36
321-Avoiding Permutations and Chebyshev Polynomials....Pages 37-38
Iterated Logarithm Laws and the Cycle Lengths of a Random Permutation....Pages 39-47
Transcendence of Generating Functions of Walks on the Slit Plane....Pages 49-58
Some Curious Extensions of the Classical Beta Integral Evaluation....Pages 59-68
Divisor Functions and Pentagonal Numbers....Pages 69-70
Front Matter....Pages 71-71
On Combinatorial Hoeffding Decomposition and Asymptotic Normality of Subgraph Count Statistics....Pages 73-79
Avalanche Polynomials of Some Families of Graphs....Pages 81-94
Perfect Matchings in Random Graphs with Prescribed Minimal Degree....Pages 95-132
Estimating the Growth Constant of Labelled Planar Graphs....Pages 133-139
The Number of Spanning Trees in P4-Reducible Graphs....Pages 141-143
Front Matter....Pages 145-145
On the Stationary Search Cost for the Move-to-Root Rule with Random Weights....Pages 147-148
Average-Case Analysis for the Probabilistic Bin Packing Problem....Pages 149-159
Distribution of WHT Recurrences....Pages 161-162
Probabilistic Analysis for Randomized Game Tree Evaluation....Pages 163-174
Polynomial Time Perfect Sampling Algorithm for Two-Rowed Contingency Tables....Pages 175-186
An Efficient Generic Algorithm for the Generation of Unlabelled Cycles....Pages 187-197
Using Tries for Universal Data Compression....Pages 199-200
Front Matter....Pages 201-201
New Strahler Numbers for Rooted Plane Trees....Pages 203-215
An Average-Case Analysis of Basic Parameters of the Suffix Tree....Pages 217-227
Arms and Feet Nodes Level Polynomial in Binary Search Trees....Pages 229-240
Random Records and Cuttings in Complete Binary Trees....Pages 241-253
Multidimensional Interval Trees....Pages 255-256
Edit Distance between Unlabelled Ordered Trees....Pages 257-259
On Parameters in Monotonically Labelled Trees....Pages 261-263
Number of Vertices of a Given Outdegree in a Galton-Watson Forest....Pages 265-266
Destruction of Recursive Trees....Pages 267-280
Front Matter....Pages 281-281
Restrictions on the Position of the Maximum/Minimum in a Geometrically Distributed Sample....Pages 283-294
Dual Random Fragmentation and Coagulation and an Application to the Genealogy of Yule Processes....Pages 295-308
Semi-Markov Walks in Queueing and Risk Theory....Pages 309-310
Representation of Fixed Points of a Smoothing Transformation....Pages 311-324
Stochastic Fixed Points for the Maximum....Pages 325-338
The Number of Descents in Samples of Geometric Random Variables....Pages 339-350
Large Deviations for Cascades and Cascades of Large Deviations....Pages 351-362
Partitioning with Piecewise Constant Eigenvectors....Pages 363-374
Yaglom Type Limit Theorem for Branching Processes in Random Environment....Pages 375-385
Two-Dimensional Limit Theorem for a Critical Catalytic Branching Random Walk....Pages 387-395
Front Matter....Pages 397-397
A Combinatorial Approach to Jumping Particles II: General Boundary Conditions....Pages 399-413
Front Matter....Pages 397-397
Stochastic Deformations of Sample Paths of Random Walks and Exclusion Models....Pages 415-428
A Markov Chain Algorithm for Eulerian Orientations of Planar Triangular Graphs....Pages 429-439
Regenerative Composition Structures: Characterisation and Asymptotics of Block Counts....Pages 441-443
Random Walks on Groups With a Tree-Like Cayley Graph....Pages 445-460
Nested Regenerative Sets and Their Associated Fragmentation Process....Pages 461-470
Front Matter....Pages 471-471
Real Numbers with Bounded Digit Averages....Pages 473-490
Large Deviation Analysis of Space-Time Trellis Codes....Pages 491-493
A Zero-One Law for First-Order Logic on Random Images....Pages 495-505
Coarse and Sharp Transitions for Random Generalized Satisfyability Problems....Pages 507-516
Stochastic Chemical Kinetics with Energy Parameters....Pages 517-529
Large Deviations of Hellinger Distance on Partitions....Pages 531-537
Estimation of the Offspring Mean for a General Class of Size-Dependent Branching Processes. Application to Quantitative Polymerase Chain Reaction....Pages 539-540
Decidability of Simple Brick Codes....Pages 541-542
A Constrained Version of Sauer’s Lemma....Pages 543-551
Back Matter....Pages 553-556