BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Which permutations of a probability distribution on integers minimize variance? Let X be a random variable on a set of integers {x1,…,xN} such that P(Xi=xi)=pi, i∈{1,…,N}. Let (p(1),…,p(N)) be the sequence (p1,…,pN) ordered non-increasingly. Let X+ be the random variable defined by P(X+=0)=p(1), P(X+=1)=p(2), P(X+=−1)=p(3),…,P(X+=(−1)N⌊2N⌋)=p(N). In this short note we generalize and prove the inequality VarX+≤VarX.
Let X1,…,Xn be independent identically distributed random vectors in Rd. We consider upper bounds on maxxP(a1X1+⋯+anXn=x) under various restrictions on Xi and the weights ai. When P(Xi=±1)=21, this corresponds to the classical Littlewood-Offord problem. We prove that in general for identically distributed random vectors and even values of n the optimal choice for (ai) is ai=1 for i≤2n and ai=−1 for i>2n, regardless of the distribution of X1. Applying these results for Bernoulli random variables answers a recent question of Fox, Kwan and Sauermann. Finally, we provide sharp bounds for concentration probabilities of sums of random vectors under the condition supxP(Xi=x)≤α, where it turns out that the worst case scenario is provided by distributions on an arithmetic progression that are in some sense as close to the uniform distribution as possible. An important feature of this work is that unlike much of the literature on the subject we use neither methods of harmonic analysis nor those from extremal combinatorics.
For a random intersection graph with a power law degree sequence having a finite mean and an infinite variance we show that the global clustering coefficient admits a tunable asymptotic distribution.
For even n we prove that the genus of the complete tripartite graph Kn,n,1 is ⌈(n−1)(n−2)/4⌉. This is the least number of bridges needed to build a complete n-way road interchange where changing lanes is not allowed. Both the theoretical result, and the surprising link to modelling road intersections are new.
A commonly used characteristic of statistical dependence of adjacency relations in real networks, the clustering coefficient, evaluates chances that two neighbours of a given vertex are adjacent. An extension is obtained by considering conditional probabilities that two randomly chosen vertices are adjacent given that they have r common neighbours. We denote such probabilities cl(r) and call r-> cl(r) the clustering function. We compare clustering functions of several networks having non-negligible clustering coefficient. They show similar patterns and surprising regularity. We establish a first order asymptotic (as the number of vertices tends to infinity) of the clustering function of related random intersection graph models admitting nonvanishing clustering coefficient and asymptotic degree distribution having a finite second moment.
The classical Erdős-Pósa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k+1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that G-B has no cycles. We show that, amongst all such graphs on vertex set {1,..,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class; concerning uniqueness of the blocker, connectivity, chromatic number and clique number. A key step in the proof of the main theorem is to show that there must be a blocker as in the Erdős-Pósa theorem with the extra `redundancy' property that B-v is still a blocker for all but at most k vertices v in B.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.