Few colored cuts or cycles in edge colored graphs
Finding induced acyclic subgraphs in random digraphs.
Finite-size scaling in percolation.
Giant vacant component left by a random walk in a random d-regular graph
We study the trajectory of a simple random walk on a d-regular graph with d ≥ 3 and locally tree-like structure as the number n of vertices grows. Examples of such graphs include random d-regular graphs and large girth expanders. For these graphs, we investigate percolative properties of the set of vertices not visited by the walk until time un, where u > 0 is a fixed positive parameter. We show that this so-called vacant set exhibits a phase transition in u in the following sense: there...
Ground state incongruence in 2D spin glasses revisited.
How frequently is a system of 2-linear Boolean equations solvable?
How the result of graph clustering methods depends on the construction of the graph
We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one first has to construct a graph on the data points and then apply a graph clustering algorithm to find a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) influences the outcome of the final clustering result. To this end we study the convergence of cluster quality measures...
Improved expansion of random Cayley graphs.
In-degree sequence in a general model of a random digraph
A general model of a random digraph D(n,P) is considered. Based on a precise estimate of the asymptotic behaviour of the distribution function of the binomial law, a problem of the distribution of extreme in-degrees of D(n,P) is discussed.
Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms
Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance of w(n)/(ln...
Inequality of two critical probabilities for percolation.
Infinite paths and cliques in random graphs
We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.
Intersections of randomly embedded sparse graphs are Poisson.
Isolated trees in a random graph
Large bounded degree trees in expanding graphs.
Large deviations in randomly coloured random graphs.
Large holes in quasi-random graphs.
Large trees in random graphs
Limit distributions and random trees derived from the birthday problem with unequal probabilities.
Limit theorems for the weights and the degrees in anN-interactions random graph model
A random graph evolution based on interactions of N vertices is studied. During the evolution both the preferential attachment rule and the uniform choice of vertices are allowed. The weight of an M-clique means the number of its interactions. The asymptotic behaviour of the weight of a fixed M-clique is studied. Asymptotic theorems for the weight and the degree of a fixed vertex are also presented. Moreover, the limits of the maximal weight and the maximal degree are described. The proofs are based...