Showing math.PRShow all
3 papers · 1 filter
math.PR2019
Upper tail bounds for Stars
Matas Šileikis, Lutz Warnke
For r \ge 2, let X be the number of r-armed stars K_{1,r} in the binomial random graph G_{n,p}. We study the upper tail \Pr(X \ge (1+ε)\E X), and establish exponential bounds which…
math.PR2018
A counterexample to the DeMarco-Kahn Upper Tail Conjecture
Matas Šileikis, Lutz Warnke
Given a fixed graph H, what is the (exponentially small) probability that the number X_H of copies of H in the binomial random graph G_{n,p} is at least twice its mean? Studied int…
math.PR2016
Multivariate normal limit laws for the numbers of fringe subtrees in -ary search trees and preferential attachment trees
Cecilia Holmgren, Svante Janson, Matas Šileikis
We study fringe subtrees of random -ary search trees and of preferential attachment trees, by putting them in the context of generalised Pólya urns. In particular we show that…