Random Structures & Algorithms

We prove that there is a constant c > 0, such that whenever p ≥ n^-c, with probability tending to 1 when n goes to infinity, every maximum triangle-free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and ...

Let Δ > 1 be a fixed positive integer. For <span>\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} \end{document} **image**</span> ...

This study is dedicated to precise distributional analyses of the height of non-plane unlabelled binary trees (“Otter trees”), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size n is proved to admit a ...

Fix a sequence c = (c₁,…,c_n) of non-negative integers with sum n − 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let <span>\documentclass{...

We prove conditional negative association for random variables x_j = 1**math-image** (j∈[n]:= {1…n}) , where σ(1)…σ(m) are i.i.d. from [n]. (The σ(i) 's are thought of as the locations of balls dropped independently into urns 1…n according to some common ...

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work,...