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.

Filter by
Sorted by
Tagged with
-2
votes
0answers
10 views

Find the number of times the machine needs to use to find your current location for x% surety. ( shower thoughts question )

Guess, you are situated in a n*n grid in a random position. You have a machine that every time you use it. It selects a new position randomly and you can ask one of the 4 questions each time. The ...
0
votes
1answer
64 views

Number of graphs isomorphic with $K_{3,3}$

Find the number of non isomorphic directed graphs that after making all edges undirected are isomorphic with $K_{3,3}$. I need to use Burnside's Lemma - which says that number of orbits (non ...
1
vote
0answers
31 views

Heat kernel bounds on graph

I'm studying the heat kernel of the continuous time simple random walk $X_t$ on $\mathbb{Z}^d$. I know of the carne varopoulos bound for the heat kernel. But I'm lookong for a similiar bound for the ...
2
votes
1answer
69 views

Probability a given path occurs in a uniformly random simple graph

Let $(G_n)$ be a sequence of uniformly sampled simple graphs with $|G_n|=n$ and $\deg i = D_i$ where the $(D_i)_{i=1}^n$ are iid random variables with mean $\mu$. Let $\gamma$ be the path $(1,2, \...
0
votes
0answers
21 views

What are the odds that a path between two nodes passes through a specified subset of nodes?

Let G be a connected graph, and let S be a specified, randomly selected, subset of the nodes of the graph (say 5%). Let a and b be two randomly selected nodes from the graph. What is the ...
1
vote
1answer
36 views

Question about Posa rotation.

I’m reading a text that discusses Posa rotation, which is defined as follows. Given a graph $G$ and a vertex $x_{0} \in V(G)$ suppose that $P=x_{0} x_{1} \ldots x_{k}$ is a longest path in $G$ ...
4
votes
1answer
41 views

A question on exchangeable variables in Erdős-Rényi graphs

Let $H$ be a subgraph of the complete graph on $n$ vertices without isolated vertices, and let $\Gamma$ be the set of isomorphic copies of $H$. For any $\alpha\in \Gamma$, let $X_\alpha$ be the ...
1
vote
1answer
62 views

line keeping all arbitrary points on one side

Prove that out of $2n+3$ points on a plane we can construct a segment using two points A, B such that the rest of $2n+1$ points lie on the same side of segment AB. It is given that no three points are ...
0
votes
0answers
20 views

Threshold for the existence of a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{n,p}$.

Let $\frac{0.35\text{log}n}{n} \leq p \leq \frac{2\text{log}n}{n}$. Show that w.h.p there does not exist a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{...
1
vote
1answer
34 views

Largest component in an Erdos Renyi graph

I need to find a $p$ for an Erdos Renyi graph with $n$ nodes so that the largest component in the graph has a size of at least $0.25n$. With simulation we have come up with an answer that $p = c/n$ ...
0
votes
0answers
33 views

Probability of x edges in a G(n,p) model

(i) Define the two Erd ̋os–R ́enyi models, $G(n,m)$ and $G(n,p)$, of random graphs. (ii) For a fixed value of $n$, describe each of the two models as a probability distribution on the ...
2
votes
1answer
71 views

The largest component of G(n, p)

Below is an question related to largest /giant component : Let $p >> \frac{1}{n}$. Prove that, for every $ε > 0$, a.a.s. the largest component of $G(n, p)$ has a size of at least $(1 − ε)n$. ...
1
vote
1answer
73 views

Clarification regarding Branching Process

So the question I am trying to solve is given below: Find the extinction probability of the branching process generated by $ξ$ ∼ Bin$(2, p)$. So I saw various approach has been used to solve this ...
2
votes
0answers
33 views

Is there an algorithm for generating a periodic geometric graph from a set of degrees?

Apologies I am a layman with regards to graph theory and am curious about the problem here as it might relate to materials science (hence 2 or 3 dimensions). References and paper recommendations are ...
1
vote
2answers
40 views

Probabilities and expectations for paths of a certain length

If we are given a random graph G, where edges are made with probability $ \frac{1}{2}$. A) What's the probability that $2$ different vertices have a path of length 2 between them. B) What is the ...
1
vote
0answers
37 views

Estimations and equivalences of binomial coefficients

I'm trying to understand a proof of a lemma in Erdos and Renyi's 1959 paper entitled "On random graphs I." I'll write what they've written first and then describe the quantities and my ...
1
vote
1answer
34 views

Show that, for $p = \frac{c}{n}, c > 1$ a constant, with high probability $\Delta(G_{n,p}) = (1+o(1))\frac{\text{log}n}{\text{loglog}n}$.

I’m reading this proof and the argument is not entirely clear to me. The argument is as follows. For $\epsilon > 0$, let $d_+ = (1 + \epsilon)\frac{\text{log}n}{\text{loglog}n}$ and $d_- = (1 - \...
0
votes
1answer
49 views

Random Graph without K3,3 subgraph

Prove there is a constant $c > 0$ s.t. for every sufficiently large n, there exists a graph with n vertices and at least $cn^{3/2}$ edges, but no K3,3-subgraph. Hint: let p be a suitably chosen ...
0
votes
1answer
39 views

Vertex expander bounded away from zero

Show that for a family of ε-vertex expanders the expansion parameter $h(G_j )$ stays bounded away from 0. Conversely, let $G_1$, $G_2$, . . . be a sequence of k-regular graphs whose number of vertices ...
0
votes
1answer
43 views

Vertex expander bounded

Let $G_1$, $G_2$, . . . be a family of ε-vertex expanders on $n_1$, $n_2$, . . . vertices. Show that there is a constant c such that eventually the diameter of $G_j$ is bounded from above by c · log($...
1
vote
1answer
42 views

Relationship between the random graph models $G_{n,k}$ and $G_{n,p}$.

This is an excerpt from “Introduction to Random Graphs” by Frieze and Karoński We start with an empty graph on the set $[n]$, and insert $m$ edges in such a way that all possible ${n \choose 2} \...
2
votes
1answer
79 views

On the Evolution of Random Graph (Existence of Log-size Components)

Theorem: Let $ \mathbf c > 0, p \geq \frac{c}{n}.$ Prove that there exists $a>0$ such that with asymptotical probability 1, the size of the largest component of $G(n,p)$ is at least $a\ln n$. ...
0
votes
1answer
46 views

Another kind of random graphs?

Maybe this is just another method to generate random graphs of a known kind, but it's not obvious for me, and I'd like to ask if someone sees this at a glance. Start with an empty set of nodes. For $i ...
1
vote
0answers
29 views

Erdös-Renyi-like hypergraphs: threshold for connectedness

Consider an $N$-element set $X$ and a fixed number $k \ll N$. How many $k$-element subsets $X_i$ (hyperedges) of $X$ do I have to choose (at random) such that (i) $\bigcup_i X_i = X$ and (ii) the ...
2
votes
1answer
87 views

Limit in distribution for a random graph

I am stuck with this problem: If $R=2K_{3}\sqcup C_{4}$ and $p=\frac{c}{n}$ and if $Z$ is the number of copies of $R$ in $G(n,p)$. What is the limit in distribution of $Z$ as $n\rightarrow\infty$. Any ...
2
votes
0answers
128 views

Number of Isomorphic Trees

Given $p = cn^{−1−1/m}(1 + o(1)), m ∈ N, c > 0.$ Prove that the number of components in $G(n, p)$ isomorphic to a tree on $m + 1$ vertices converges to a $Pois$($\frac{c^m(m+1)^{m−1}} {(m+1)!}$)...
2
votes
1answer
55 views

Lemma regarding Balanced Graph

I am trying to prove a lemma which states that if Let $G= G_1 \sqcup . . . \sqcup G_k$ be a disjoint union of $k$ connected graphs. Prove that $G$ is balanced if and only if $ρ(G_1) = . . . = ρ(G_k)$ ...
2
votes
1answer
34 views

Relation between $k$ and $n$ in Alon and Spencer, 4th Edition, Section 10.3

On page 184, in section 10.3 of Alon and Spencer (The Probabilistic Method, 4th Edition), line -8, it is written: "Then $$n = \sqrt{2}^{k(1+o(1))}, ..."$$ At this point in the text, what is this ...
0
votes
2answers
54 views

Graph Theory - Binomial Random Graphs [closed]

Hi, could anyone provide any assistance on this? I have a feeling there's going to be a question like this on the exam and I really have no idea how to approach this concept. Any help on either part ...
1
vote
0answers
21 views

a natural way to measure the ``importance'' of the shortest path between pair of vertex

Suppose we are considering a graph G which is connected, unweighted, and undirected. Let P be the space of shortest path G, i.e., P contain the shortest path of all possible pair of vertex from G. I ...
2
votes
1answer
64 views

Connectivity of a graph in the Erdős–Rényi model

In the lecture series on random graphs that I'm watching teacher has made the following statements: if the probability of a branch between any two vertexes to be present in a graph is this function of ...
1
vote
0answers
48 views

Sharp threshold Probability

I have studied that.. If for $cp (n), c < 1,$ the graph almost surely does not have the property and for $cp (n), c > 1,$ the graph almost surely has the property, then $p (n)$ is a sharp ...
4
votes
1answer
113 views

Calculating the number of increasing properties of subsets of $\Gamma = \{1, 2, 3, 4\}$

Calculate the number of increasing properties of subsets of $\Gamma = \{1, 2, 3, 4\}$. I understand what an increasing property is, but I have no idea how to do this. Any hints would be great. Thanks....
0
votes
0answers
15 views

Will the conditional variance be larger in a sub-graph?

Please find the pictures of Graph 1 and Graph 2 here Graph 2 is constructed from Graph 1 by removing the edge $X_1\rightarrow X_2, Y\rightarrow X_2$. My question is whether there is always $$\...
0
votes
1answer
29 views

How to create a metric in a connected locally finite abstract graph?

First of all sorry for my English. I want to create a metric in a graph $(V, E)$ where $V$ is the countable set of vertices, $E$ the set of edges. The graph is non-directed, connected, locally finite. ...
6
votes
1answer
115 views

Measures of randomness of graphs

There are many practical measures of randomness for binary or number sequences. Some randomness tests yield a single number (like Kolmogorov complexity), others come as batteries of tests (like the ...
2
votes
2answers
88 views

Fano planes probability

I have to find the threshold probability for containing a Fano plane. Since its a 3-hypergraph with 7 vertices and 7 hyperedges I was following the same approach as in: https://math.stackexchange.com/...
5
votes
1answer
123 views

Threshold probability of the 3-uniform hypertriangle

I am stuck on a random hypergraph problem (I am encountering random hypergraphs for the very first time). Let $G_{3}(n, p)$ be a binomial 3-uniform hypergraph. Find a threshold probability for ...
1
vote
1answer
84 views

Monotone Properties of Random Graphs

I am learning about the monotone properties of random graphs. I came across this question which I am unable to prove. Let $s = s(N) ∈ \{0, 1, . . . , N\}$ where ${s(N) → ∞}$ and ${N − s(N) → ∞ }$ as ${...
2
votes
1answer
49 views

Expected size of largest connected component

I have a sample space of all the undirected graphs having n vertices and m edges. Then what is the expected value of the size of the largest connected component? My original problem is that using the ...
-1
votes
1answer
39 views

Biased graph generating processes

Given a random process (algorithm) that is supposed to generate with equal probability graphs from a given class $\Gamma$. Assume the process is not obviously biased, i.e. generating graphs unevenly (...
0
votes
0answers
28 views

Properties that are assumed to hold for almost all graphs in a given class

For some classes of random graphs (e.g. defined by a given set of independent properties) one can prove that some (dependent) properties hold for almost all of them. Examples: Almost all graphs are ...
1
vote
1answer
38 views

Random Markov Field, Mean-Field inference and potential functions… perplexities

I'd need help in understanding some concepts presented on a paper that I've started to read recently. The general setting is about seeing graph structures from a probabilistic persepctive, in ...
2
votes
0answers
171 views

Generating random graphs with given properties

One way to define random graphs is to fix a finite set of properties $P$. Picking with equal probability a graph with $|V|=n$ out of the set $\Gamma_n(P)$ of all $n$-(vertex-)graphs with properties $P$...
1
vote
1answer
38 views

Computing expected number of induced subgraphs of $G(n,\frac12)$ without graph removal lemma.

Define $G(n,\frac12)$ to be a graph on $n$ vertices where each edge has a $\frac12$ probability of being formed. We may compute the number of subgraphs of $G(n,\frac12)$ isomorphic to, say, $K_3$ as ...
6
votes
2answers
117 views

Graph puzzles: Constructing graphs from tiles

There is a vast literature on the reconstruction conjecture which says that two graphs with the same deck $D$ are isomorphic. The deck is the multi-set of vertex-deleted subgraphs of a graph (which ...
1
vote
1answer
43 views

The distribution of the uniform random tree

I have a question about how to interpreted the following: Proposition 2.3. The uniform random tree $\mathbb{T}_{n}$ has the same distribution as a tree generated as follows: Take a Galton-Watson ...
1
vote
0answers
55 views

Threshold for graph diameter two

I am currently studying Random Graph and Thresholds Probability. I stubbled on this question, although I tried solving it from my knowledge of previous examples in Random Graphs-Luczak, Rucinski text ...
0
votes
1answer
45 views

Expected number of vertices for a given random graph

So I have to find out the expected value of the number of vertices of degree 1. Let's the given graph if G(n,p). Then the $$\mathbb{P}(deg(v)=1) = {n \choose 1} (p)^{1}(1-p)^{n-1}$$ And $$\mathbb{E}X =...
2
votes
0answers
50 views

Why supersingular isogeny graphs are expander graphs?

I'm studying isogeny graphs and in particolar isogeny graphs of supersingular elliptic curves. In a supersingular isogeny graph $\mathcal{G}_\ell(p)$ nodes are supersingular elliptic curvers $E$ over $...

1
2 3 4 5
15