Skip to main content

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
1 vote
0 answers
29 views

positive-semidefiniteness of laplacian of signed graph

Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}=\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$. my question. If $\...
tony's user avatar
  • 403
2 votes
0 answers
61 views

Average number of cycles in a directed regular graph?

A directed random regular graph is a graph where all vertices have exactly $d_{\rm in}$ edges going in and $d_{\rm out}$ going out. If the graph is undirected, i.e. all vertices have degree $d$, then ...
stopro's user avatar
  • 87
0 votes
0 answers
41 views

Does "epsilon-regular" equal to "cut distance less than epsilon"?

Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal? $G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
bc a's user avatar
  • 149
3 votes
0 answers
75 views

Is the probability distribution of a graphon given as a graph limit computable?

Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
Christopher King's user avatar
1 vote
0 answers
84 views

Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
ABIM's user avatar
  • 4,809
7 votes
2 answers
222 views

Evolution of the empirical mean of a list as we remove elements proportional to their value

Consider a list of $N$ integers $k_1,k_2,\dots k_N$, drawn independently from some distribution $P(k)$ with $k_i \geq 1$. We denote its mean with $\langle k\rangle=\sum_{k=1}kP(k)$. The first two ...
papad's user avatar
  • 272
1 vote
0 answers
159 views

Locally "unshortable" paths in graphs

Setup: Consider a connected graph G, with diameter "d". Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
Alexander Chervov's user avatar
0 votes
0 answers
60 views

Expected number of edges in the neighborhood of vertices in random graphs

Question: given a vertex $v$ of a symmetric random graph $G$ without self loops and parallel edges, what is the expected number edges in the subgraph induced by the vertices $u\in G\setminus v:\ (u,v)...
Manfred Weis's user avatar
  • 12.8k
3 votes
0 answers
140 views

Smallest dominating set

Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
Zach Hunter's user avatar
  • 3,413
1 vote
0 answers
81 views

Diameters of random bipartite graphs

Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
Zijian Wang's user avatar
2 votes
0 answers
84 views

Do Fagin's zero-one laws hold on stochastic block model?

Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
SagarM's user avatar
  • 131
7 votes
1 answer
137 views

Nearest neighbors on random complete graph

Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
David Aldous's user avatar
2 votes
2 answers
245 views

Finding an easy example applying the general Lovász local lemma

Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks. General Lovász local lemma: Consider a set $...
Xin Zhang's user avatar
  • 1,140
4 votes
1 answer
202 views

Erdős–Rényi random graphs — reproducing 2 inequalities

In Erdős and Renyi's 1959 paper On random graphs I , I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}. Eq.\eqref{1} is: $$ P \le \...
RickB88's user avatar
  • 43
0 votes
0 answers
60 views

Finding small connected subgraphs of a random regular graph

Fix parameters $m,f,b$. I do not believe it matters for the general form of the question, but in the problem I am examining $m,f,b$ are all powers of $2$ with $m \gg f > b$. For example $m=2^{25},f=...
smarky's user avatar
  • 1
1 vote
0 answers
52 views

Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph

Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
yy98's user avatar
  • 11
2 votes
2 answers
136 views

Example of random walk in a random environment (RWRE) saying things on the environment

I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment. To clarify a bit, ...
Cal's user avatar
  • 59
1 vote
0 answers
69 views

Benjamini-Schramm convergence: convergence on metric balls implies weak convergence?

In the famous paper by Benjamini-Schramm 2001, they consider the space of rooted graphs with uniformly bounded degrees, this space modulo rooted graph isomorphism is denoted by $\mathcal X$. This ...
Fredy's user avatar
  • 492
0 votes
0 answers
46 views

A question related to contiguity of random regular graphs

I am looking for a reference for the following fact. Let $r\geq 3$ be constant, let $G(n,r-2)$ be a random (simple) $(r-2)$-regular graph and let $H(n)$ be an independent random Hamiltonian cycle (on ...
35T41's user avatar
  • 123
0 votes
0 answers
29 views

Do finite components get smaller as supercritical random graphs with an arbitrary degree sequence get denser?

I asked this question a few weeks ago on MSE but did not receive any responses so I am going to ask a related but more specific question here. First some notation. Let $\mathbb{G} = \mathbb{G}(n,\...
deej's user avatar
  • 21
1 vote
0 answers
76 views

Graphon convergence of uniform weighted graphs

I have a question that I need at some point my research. Suppose that the upper-triangular entries of an $n\times n$ symmetric matrix $A$ are i.i.d. Uniform$(0,1)$. Does the weighted graph with ...
Probabilist's user avatar
0 votes
0 answers
7 views

Statistics of connected-component sizes of minimum-weight $f$-factors in random planar geometric graphs

An $f$-factor is an $f$-regular subgraph with the same vertex set $V$ and a subset of the edges $E$ of some given undirected graph $G(V,E)$ Question: what is known about the statistical properties of ...
Manfred Weis's user avatar
  • 12.8k
0 votes
0 answers
98 views

Phase-transitions for a property of random bipartite graphs

Let $N_1$, $N_2$, and $k$ be positive integers. Let $V_1$ and $V_2$ be finite sets with $|V_i| = N_i \ge 1$. Consider a bipartite graph $G=(V_1,V_2,E)$ constructed as follows. For every $x \in V_1$, ...
dohmatob's user avatar
  • 6,764
1 vote
0 answers
55 views

A one-sided/monotone version of min/max-stable distributions -- does this have a name?

In a couple of papers I am working on (in random graph theory) I have encountered the following property of certain probability distributions, which I will describe shortly, and I am wondering if this ...
Joel Ottar's user avatar
1 vote
0 answers
129 views

Random graphs constructed by many large matchings

Let $G_{n,d}$ be $d$-regular random graph. We know that for $d \geq 3$, $G \in G_{n,d}$ a.a.s. has a $1$-factorisation when $n$ is even. So, the resulting graph that obtained from randomly choosing $d$...
Yuhang Bai's user avatar
2 votes
1 answer
208 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,335
1 vote
1 answer
120 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 $...
Yuhang Bai's user avatar
2 votes
0 answers
75 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
5 votes
1 answer
298 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
46 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
3 votes
0 answers
59 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,748
2 votes
0 answers
145 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
71 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
8 votes
1 answer
381 views

What is this Ramsey problem?

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
Zach Hunter's user avatar
  • 3,413
1 vote
1 answer
468 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
112 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
194 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,543
6 votes
1 answer
240 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,809
0 votes
0 answers
44 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
  • 612
1 vote
0 answers
75 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
91 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
  • 612
2 votes
1 answer
95 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
69 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
121 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
  • 612
6 votes
0 answers
143 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
144 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
  • 612
1 vote
1 answer
292 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
  • 612
6 votes
2 answers
628 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
359 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
145 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

1
2 3 4 5
7