Questions tagged [random-graphs]

Question 1

In the book Computational Complexity: A Modern Approach you can find the following problem this is actually a multi-graph with loops. Their definition of expander and a hint are attached below My ...

Question 2

Given a locally finite, countably infinite connected graph, define its critical probability as $$p_c(G):=\inf\left\{p\in (0,1]: (V(G),E(G)_p) \substack{\text{ contains an infinite connected}\\ \text{...

Question 3

Problem. Let $t$ hard-core spheres of diameter $D$ be placed i.i.d. uniformly in the unit cube. Every pair is joined by a rigid cylinder of the same diameter $D$. Spheres and cylinders are mutually ...

Question 4

Given parameters $n$ and $p$ of an Erdos-Reyni random graph $G(n,p)$, one can estimate parameters such as the number of edges or triangles of the realized graph and show concentration results for ...

Question 5

In the proof of Theorem 4.1 of the book Random Graphs by B. Bollobas. Where it is written that Suppose the graph $A$ and $B$ are such that $B$ is an $H$-graph and it has exactly $t$ vertices not ...

Question 6

I am reading this paper and have a question about the factor graph of the posterior distribution in Figure 1. It looks like the authors never really define what that distribution is, and explain why ...

Question 7

I have the following problem: Given a Galton-Watson tree $T$ where the offspring distribution is $p_0 = p_2 = \frac{q-1}{2q}$ and $p_1 = \frac{1}{q}$ for some prime number $q \geq 3$. Consider depth-...

Question 8

I have read this statement from various articles: By considering random graphs in $\mathcal{G}(n,1/2)$, it can be seen that the discrepancy of a graph on $n$ vertices can be as small as $O(n^{3/2}).$ ...

Question 9

In the binomial Erdős–Rényi model of random graphs, we are interested in random graphs where there are $n$ nodes and where each of the $\binom{n}{2}$ possible edges is independently added to the graph ...

Question 10

Consider the complete graph $K_4$ with four vertices; all vertices are connected by an edge to all other vertices. Suppose now that we flip an unbiased coin for each edge. If heads comes up, we leave ...

Question 11

To determine the probability that vertices 1 and 2 lie in the same connected component in the random graph $G(4, p)$ https://math.stackexchange.com/a/1176529/745350 obtained an answer$$p + p^2 (1 - p) ...

Question 12

For the most part I understand the mathematical statement of Szemerédi's Regularity Lemma: it states that any large graph's vertices can be partitioned into k parts (groups) of equal or nearly equal ...

Question 13

Consider the following random process. Starting with n active nodes, at each step choose two active nodes uniformly randomly, making one inactive and creating an edge between the two nodes. After ...

Question 14

As part of proving that $C_1 ( G\left(n, \frac{c}{n}\right)) \leq (\rho(c) + \eta) n$ whp for $c > 0$ and fixed $\eta$ with $\rho(c)$ denoting the survival probability of the Galton–Watson ...

Question 15

Let $G$ be a graph on $n$ vertices. It is quite easy to write out a first-order sentence $\phi$ in the language of graphs such that any graph on $n$ vertices which satisfies $\phi$ is isomorphic to $G$...

Stack Exchange Network

Questions tagged [random-graphs]

The permutation model is an expander with high probability

Is the set of critical values for percolation dense in $(0,1)$?

Linking probability with 3D space filling complete graphs

Concentration of the number of triangles in a random graph with fixed number of edges

Proof explanation: theorem 4.1 from the book Random graphs Bollobas

The factor graph corresponding to the posterior distribution

Conditional expectation of number of visited nodes in a depth-first search on a Galton-Watson tree

The random graph $G(n,p)$ attains the minimum of graph discrepancy

Probability (or asymptotics) that $G_{n, p}$ is a forest?

What is the probability that the graph remains connected?

Probability for 2 vertices to lie in the same component of a random graph $G(4,p)$

Understanding the regularization lemma and what can be said about graphs representing the real word by applying this lemma?

Expected height of random tree formed by merging

Proof of Theorem 3 Handbook of Large Scale Random Networks - Bela Bollobas, Robert Kozma

Distinguishing between graphs with short first-order sentences

Hot Network Questions