Questions tagged [random-graphs]

The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.

Filter by
Sorted by
Tagged with
2 votes
1 answer
63 views

Connected components in random regular graphs

Suppose we take a random regular graph $G_{2n, r}$, where $n$ is large. Let us also assume that $r$ is fixed, (not dependent on $n$). Let's say that half of the vertices of the graph are colored black ...
SMS's user avatar
  • 1,223
1 vote
1 answer
83 views

Random graph uniformly sample from the special graphs

We know two basic random graph models:$G(n,p)$ and $G(n,m)$. $G(n,m)$ consists of all graphs with $n$ vertices and $m$ edges, in which the graphs have the same probability. We know that $G(n,p)$ and $...
zhukui bai's user avatar
2 votes
0 answers
53 views

Random walks on randomly evolving graphs

I am interested in analyzing a random walk on a growing tree with vertices labelled on a tree with following properties. The number of nodes at depth $k$ is a an exponential function of $k$. One can ...
user82261's user avatar
  • 121
1 vote
0 answers
109 views

Size of the maximum matching in random graph $G(n,p)$

a.a.s. Is there a lower bound of maximum matching size in random graph $G(n,p)$? For example: Theorem(Bollobas and Thomason). Let $y_n=2 n p-\log n-2 \log \log n$. Then $$ \mathbb{P}(\mathbb{G}(n, p) \...
zhukui bai's user avatar
0 votes
0 answers
25 views

Asymmetric strictly balanced graphs

I am interested in the existence of strictly balanced, asymmetric graph with given number of vertices and edges. A known result of Rucinski and Vince shows that for every $(v,e)$ with $1\leq v-1 \leq ...
35T41's user avatar
  • 123
5 votes
1 answer
192 views

Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$

Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$? ...
Nikita Gladkov's user avatar
1 vote
0 answers
39 views

Diameter of component graph of uniform spanning forests on the amenable transitive graph with super polynomial growth

According to the paper Benjamini, Kesten, Peres, and Schramm - Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12 (Annals, 2004), the diameter of the component graph of the ...
none Yuan's user avatar
1 vote
0 answers
48 views

What is the average degree of a node in a Barabasi-Albert network?

Consider a random network that is generated following the Barabasi-Albert model, i.e., the degree distribution of a node follows the distribution: $$ p(k)=\frac{4}{k(k+1)(k+2)}.$$ For network of size $...
Sam's user avatar
  • 187
3 votes
0 answers
51 views

Minimum induced subtree cover number of a graph

For an arbitrary simple finite graph $G$, without multiple edges between any two nodes and without any loop, the minimum induced subtree cover number, which is denoted by $stc(G)$, is defined to be ...
Shahrooz's user avatar
  • 4,688
2 votes
0 answers
132 views

Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]

Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$. Question: Is (the simple random walk on) $G$ transient almost surely?
none Yuan's user avatar
1 vote
1 answer
53 views

Probability of randomly finding a loop in a (directed) Bernoulli random graph

This problem is inspired by an activity at work, where each person was tasked with introducing another person in the onboarding class, sequentially. Problem Statement Given $N$ people. For each pair ...
Benjamin Wang's user avatar
0 votes
0 answers
92 views

An unnamed (perhaps?) graph theory problem

We create a graph weighted $G_0$ given a set of nodes and a function $f(v_x, v_y, G_i) $ that calculates the edge weight between the nodes within $G_0$ that's dependent on the global graph structure. ...
Maximilian Powers's user avatar
0 votes
1 answer
217 views

Vertex degree on random graphs

Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$, where $G_{n,p}$ is a graph with $n$ vertices and the ...
Nir Kfir's user avatar
1 vote
0 answers
81 views

Probability of (single) connecting paths in Erdos-Renyi graphs

In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of there ...
Scriddie's user avatar
  • 129
4 votes
1 answer
91 views

Quasi-random vs pseudo-random graphs

My question is somehow concerning terminology on extremal graph theory. Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
Johnny Cage's user avatar
  • 1,453
6 votes
1 answer
154 views

Expected doubling constant of a random Erdős–Rényi graph

Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
ABIM's user avatar
  • 4,881
0 votes
0 answers
38 views

Hyperbolic random geometric graphs with less clustering

The hyperbolic random geometric graph $G_{\mathbb{H}}$ consists of a $N$ uniformly random points (within a disk of radius $R$ centred at the origin) of the hyperbolic plane $\mathbb{H}$, connected ...
apg's user avatar
  • 532
1 vote
0 answers
57 views

Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability

Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...
messi22's user avatar
  • 53
1 vote
0 answers
85 views

Limit of alternating sum of factorial moments which diverge

Consider the non-negative, integer valued random variable $X$, and its $i^{\text{th}}$ factorial moment $E_{i}[X]$. Then we have that $$ P(X=0) = \sum _{i=0}^{\infty} \frac{(-1)^i E_{r}[X]}{ i!} $$ ...
apg's user avatar
  • 532
0 votes
0 answers
69 views

Reference request: Spectral gap for cubic random graphs

I gather the following is well known: Fact: There exists some $\epsilon>0$ such that with probability approaching $1$ as $n\to\infty$, a random cubic (i.e. $3$-regular) graph on $n$ vertices has ...
RegularGraph's user avatar
2 votes
1 answer
84 views

Lower bound on the number of balanced graphs

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs and ...
35T41's user avatar
  • 123
0 votes
0 answers
66 views

Likelihood ratio of non-trivial cycles in an inhomogeneous random square lattice graph embedded on a toroidal surface

Consider a square lattice (random) graph $G$ embedded on a toroidal surface. Each edge $(i, j)$ of the graph has an associated likelihood probability $p_{ij}$. The probabilities $p_{ij}$ come from a ...
Sanchayan Dutta's user avatar
0 votes
0 answers
88 views

What to do when the second moment method does not provide a sufficient bound for $P(X=0)$

We have that for a real valued random variable $X$, $$ P(X=0) \leq \frac{\text{Var}(X)}{\left(\mathbb{E}(X)\right)^2} $$ known as Chebyshev's inequality. Consider a random variable $X \in \{0,1,2,\...
apg's user avatar
  • 532
6 votes
0 answers
99 views

Hamilton cycles in random graphs with just enough connectivity

What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
Dmytro Taranovsky's user avatar
1 vote
0 answers
101 views

Width of the critical window in a random graph

In an Erdős–Rényi random graph $G(n,p)$, the giant component emerges with thresholding function $p(n) = c/n$, where $c>1$. When $c=1$, and $\lambda \in \mathbb{R}$, we can write or "...
apg's user avatar
  • 532
1 vote
1 answer
214 views

What is the exact definition of a sharp transition?

In "Sharp threshold phenomena in statistical physics", H. Duminil-Copin, Japanese J. of Math. 14, 2019, a sharp transition of a boolean function is defined as follows: A sequence of ...
apg's user avatar
  • 532
0 votes
0 answers
65 views

Vertex percolation on bipartite graphs

This is essentially a repost of this math overflow post since it didn't get any reception. Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with ...
q_bert's user avatar
  • 1
6 votes
2 answers
495 views

Threshold function for a graph not being planar

A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property. It is well-known that every ...
W. Paul Liu's user avatar
8 votes
2 answers
267 views

Selection of an n-vertex graph at random

Let's say I want to select, at random, an $n$-vertex graph $G=(V,E)$ from the set of all $n$-vertex graphs. One way to do this would be to take the empty graph on $n$ vertices and then add each ...
Rhyd Lewis's user avatar
1 vote
1 answer
122 views

Discrepancy of random bipartite graphs (2)

This question is a modification of the one asked here, which turned out to ask for something too strong to be true. Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
Antoine Labelle's user avatar
3 votes
1 answer
164 views

Discrepancy of random bipartite graphs

This is a crosspost from MathStackExchange (original question). Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$). Define a ...
Antoine Labelle's user avatar
10 votes
1 answer
417 views

(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$

Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
Augusto Santos's user avatar
2 votes
2 answers
124 views

Which infinite random graphs with percolation threshold $p_c=0$ are transient?

I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...
Christian Mönch's user avatar
1 vote
1 answer
249 views

Hammersley-Clifford theorem

The paper spatial interaction and the statistical analysis of lattice systems by Besag (1974) presents an alternative proof for the Hammersley-Clifford theorem. In order to prove the HM theorem, Besag ...
BelwarDissengulp's user avatar
1 vote
0 answers
54 views

Angles between edges of a geometric graph and graph invariants

Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph? I'm interested to see what else is ...
apg's user avatar
  • 532
5 votes
3 answers
453 views

Probability of an edge in a random graph

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence. ...
Matthieu Latapy's user avatar
3 votes
1 answer
139 views

The most pseudorandom subgraph of a dense graph

A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy ...
alpmu's user avatar
  • 785
2 votes
1 answer
142 views

Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...
Karagounis Z's user avatar
2 votes
1 answer
79 views

Are the eigenvalues of the 1D lattice with random weights known?

Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...
Sam's user avatar
  • 187
1 vote
1 answer
117 views

how to compute the probability that a random graph has two components? [closed]

This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph: A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs....
Xin Niu's user avatar
  • 113
0 votes
0 answers
139 views

Expected chromatic number of random subgraph

Let $G$ be a fixed graph and let $G_p$ be a random subgraph of $G$ where every edge is kept independently with probability $p$. According to [1] and [2] the paper [3] proves $$ \mathbb{E}[\chi(G_p)] \...
Prokofiev's user avatar
1 vote
0 answers
19 views

Is homomorphism density of partially labeled graph continuous with respect to cut metric

Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
Raghav's user avatar
  • 351
1 vote
0 answers
65 views

Canonical representation of the a probability distribution for Hammersley Clifford Theorem

I'm reading the following paper http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/GibbsFieldEst/BesagJRSSB1974.pdf On page 7 they give the result that $$Q(\textbf{x}) = \sum_{1 \leq i \leq n} ...
Pavan Sangha's user avatar
4 votes
0 answers
278 views

Research on graph theory

I am interested in graph theory. My background is mainly algebraic. I have been researching algebraic geometry for five years so I assume that the transition to the graph theory realm shouldn't be so ...
Samantha Smith's user avatar
1 vote
1 answer
91 views

Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution

I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following: Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...
MikeG's user avatar
  • 587
6 votes
1 answer
429 views

Graphs resembling the math genealogy graph must have concentration in a small number of families?

I was talking with a non-mathematician the other week at a workshop about the fact that many mathematicians, like myself, are indexed in the math genealogy database. We talked a little about how many ...
Josiah Park's user avatar
  • 3,152
1 vote
0 answers
84 views

Longest close common subsequence but for continuous random variables

We have two copied sequences of correlated continuous positive random variables that are independent of each other $(X_{n})\perp(Y_{n})$ and equal in distribution $X_{n}\stackrel{dis}{=}Y_{n}$ for ...
Thomas Kojar's user avatar
  • 2,770
3 votes
0 answers
111 views

Random graph - probability threshold for any linear size set to contain a fixed clique

Let $t\geq 3$ and $0<\varepsilon<1$ be fixed. Denote by $K_t$ the clique on $t$ vertices, and by $G_{n,p}$ the binomial random graph. Question: Is the threshold for the probability that "...
Thomas Lesgourgues's user avatar
1 vote
0 answers
83 views

In percolation on a lattice, how is "infected" status correlated for points in a region around the origin?

Consider independent bond percolation on $\mathbb{Z}^2$, with $p>p_c$ so that the process is supercritical. For any site $x$ let $Y_x$ be the indicator of $x$ belonging to the infinite open cluster....
Ben Golub's user avatar
  • 1,058
0 votes
0 answers
71 views

Contiguity of uniform random regular graphs and uniform random regular graphs which have a perfect matching

Let us consider $\cal{G}_{_{n,d}}$ as the uniform probability space of d-regular graphs on the n vertices $\{1, \ldots, n \}$ (where $dn$ is even). We say that an event $H_{_{n}}$ occurs a.a.s. (...
Hossein's user avatar

1
2 3 4 5
7