En probabilistisk studie av grafer och träd

Tidsperiod: 2013-01-01 till 2016-12-31

Projektledare: Cecilia Holmgren

Finansiär: Vetenskapsrådet

Bidragstyp: Projektbidrag

Budget: 3 200 000 SEK

The overall purpose is to develop the study of graphs through the combined use of probabilistic methods (e.g. renewal theory, Galton-Watson processes, Brownian motion, contraction method and Stein´s method) and combinatorial arguments. The main focus is on random trees and threshold problems (examining phase transitions). Five main areas are studied: A)BOOTSTRAP PERCOLATION: 1) Find the minimal percolating set in the hypercube; 2) Study the speed of percolation; 3) Find the critical probability for trees. B) CUTTINGS IN TREES: 1) Study its extension into a general k-cutting model; 2) Study inversions in trees using my recently developed methods (renewal theory and Aldous Brownian continuum tree) for cuttings in trees; 3) Study problems related to a new cutting model introduced by Devroye. C) SPLIT TREES: 1) Determine the expected fringe (number of vertices at the maximal depth) of the binary search tree; 2) Find the distribution of the number of vertices in split trees; 3) Study the running time of data algorithms; 4) Determine phase transitions of CTM protocols for sending messages efficiently. D) GRAPH PEBBLING: Show Graham´s conjecture and develop random pebbling. E) CODES ON GRAPHS: Introduce probabilistic methods for studying phase transitions and threshold functions for the minimum cardinality of " identifying codes" in random trees.