Local extrema in random trees.
Logarithmic components of the vacant set for random walk on a discrete torus.
Logconcave random graphs.
Loose Hamilton cycles in random 3-uniform hypergraphs.
Loose Hamilton cycles in random uniform hypergraphs.
Lower bounds for the size of random maximal -free graphs.
Matrix and discrepancy view of generalized random and quasirandom graphs
We will discuss how graph based matrices are capable to find classification of the graph vertices with small within- and between-cluster discrepancies. The structural eigenvalues together with the corresponding spectral subspaces of the normalized modularity matrix are used to find a block-structure in the graph. The notions are extended to rectangular arrays of nonnegative entries and to directed graphs. We also investigate relations between spectral properties, multiway discrepancies, and degree...
Matrix-free proof of a regularity characterization.
Minimum connected dominating sets of random cubic graphs.
Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices.
Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold.
Near-minimal spanning trees : a scaling exponent in probability models
We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.
Neighbour-distinguishing edge colourings of random regular graphs.
Non-hyperbolicity in random regular graphs and their traffic characteristics
In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.
On a matching distance between rooted phylogenetic trees
The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values...
On a sphere of influence graph in a one-dimensional space
A sphere of influence graph generated by a finite population of generated points on the real line by a Poisson process is considered. We determine the expected number and variance of societies formed by population of n points in a one-dimensional space.
On concentration of self-bounding functions.
On entropies of occupancy distributions
On families of weakly dependent random variables
Let be a family of random independent k-element subsets of [n] = 1,2,...,n and let denote a family of ℓ-element subsets of [n] such that the event that S belongs to depends only on the edges of contained in S. Then, the edges of are ’weakly dependent’, say, the events that two given subsets S and T are in are independent for vast majority of pairs S and T. In the paper we present some results on the structure of weakly dependent families of subsets obtained in this way. We also list...
On -radius of random graphs.