# Questions tagged [random-graphs]

A random graph is a graph - a set of vertices and edges - that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

491 questions
20 views

### How to calculate the maximum height

I am studying radio galaxies and observing the behavior of fluxes at high frequencies and want to calculate the maximum height of the fluxes at where they best correspond(typically at higher ...
21 views

### Probability of random graph being connected - block model

Let $n\in \mathbb{N}$ be given. Let us assume that the set of vertices is $V=[n]=\mathcal{C}^+ \cup \mathcal{C}^- \cup \mathcal{D}$, where the sets $\mathcal{C}^+$ and $\mathcal{C}^-$ stand for the ...
13 views

26 views

### Generate a random bi-connected graph

I am trying to find an algorithm which will generate a random graph G, where G is a bi-connected graph too. An efficient algorithm is appreciated but I am looking for a brute force algorithm which ...
47 views

### How to show the small component is likely to be a tree in a random graph

I was just looking a book and the book said For a graph in supercritical regime (np > 1). For the small component (size s) not a part of giant component, it is a tree (which means the number of edges ...
9 views

41 views

### expected number of in- and out-going links in random PA graph

I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is: $t=1,$ one node $v_1$. At each time step $(t+1)$ either we create a new node ...
86 views

### Probability that a graph is bipartite

Given the empty graph on $n$ vertices, we add $m$ of the $\binom{n}{2}$ possible edges, uniformly at random. What is the probability that the resulting graph is bipartite (equivalently, contains no ...
42 views

### Largest size of a complete bipartite sub-graph in a random graph

Let $G\in G(n,\frac{1}{2})$ be a random graph. What is the maximum number of edges of a complete bipartite graph that can appear as a subgraph in $G$ almost surely? Let's give an estimate in the ...
20 views

### Sampling probabilities for half-sparsification algorithm

https://dl.acm.org/citation.cfm?id=2948062 In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for ...
75 views

### Perfect matching in random bipartite graph - with fixed probability

as a follow up from this question : Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model ...
58 views

### Probability of being in same connected component

I would like to answer the following basic question: Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the ...
54 views

### Random graph with $p \ll n^{-1+\epsilon}$ a.a.s has no subgraph with $k$ vertices with at least $k+1$ edges

Let $G=(n,p)$ with $p \ll n^{-1+\epsilon}$ for all $\epsilon >0$. Then for each $k\in \mathbb{N}$ there are a.a.s no $k$ vertices with at least $k+1$ edges. Proof: We want to show \Pr(\...
48 views

### Binary trees constructed from the bottom up

I'm dealing with a set of random binary trees which I can't find referenced anywhere in literature. Computer scientists seem to prefer "random search trees" which is a different ensemble than mine (...
23 views