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
0 votes
0 answers
318 views

The diameter of random regular graphs

In 1982, B. Bollobas and Vega in the paper gave the configurational model to generate $r$-regular random graphs. They gave the following theorem (Theorem 1 in the paper). Theorem: Let $r\geq 3$ and $\...
Ranveer Singh's user avatar
2 votes
1 answer
123 views

Relation between random graph models $G^{(B)}_{n,m}$ and $G_{n,m}$

In Frieze, Alan; Karoński, Michał, Introduction to random graphs, in Section 1.3 Pseudo-Graphs, there is a model of random multi-graphs, which is denoted as $\mathbb{G}^{(B)}_{n,m}$. Def. A random ...
Victor's user avatar
  • 655
6 votes
1 answer
369 views

Probability in Chromatic number upper bound of induced subgraph

Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced ...
Ever Garden's user avatar
1 vote
1 answer
165 views

Survey/references on random geometric $K$-NN – $K$-nearest-neighbour graphs?

[Edit:] Some related info on number of connected components of NN-graphs can be found here: https://cstheory.stackexchange.com/a/47037/2408 Sample $N$ points in $\mathbb{R}^d$ from some distribution $...
Alexander Chervov's user avatar
-2 votes
1 answer
68 views

Ensemble averaging in a random graph (or network) in the large $N$ limit [closed]

I have a random graph/network described by the adjacency matrix $(a_{ij})_{N\times N}$ where $a_{ij}=1$ with probability $p$. Each node in the graph is associated with a continuous quantity $\eta_i=\...
maurizio's user avatar
  • 137
4 votes
1 answer
1k views

Critical probability for Erdos-Renyi digraphs to be strongly connected

Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
math_lover's user avatar
6 votes
0 answers
282 views

Probability that a random multigraph is simple

Question. Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
Matthieu Latapy's user avatar
11 votes
1 answer
354 views

Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?

Is the following lemma a well known result in graph theory? I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
Claus's user avatar
  • 6,777
3 votes
1 answer
296 views

Relation between expected values of eigenvalues of Laplacian matrix of a graph and eigenvalues of expected Laplacian matrix of that graph?

Particularly, I am dealing with Erdős–Rényi random 𝐺(𝑛,𝑝), so the expected Laplacian matrix of 𝐺(𝑛,𝑝) is 𝑝(𝐽𝑛−𝐼𝑛), where 𝐽𝑛 and 𝐼𝑛 are one and identity matrices, respectively. In ...
Anđela Todorović's user avatar
1 vote
0 answers
130 views

Count shortest path with different lengths in random graph

Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
neverevernever's user avatar
1 vote
1 answer
274 views

An attempt to find expected value of clique number of special random graph

Let $G(n)=(V,\mathcal{E})$ be a random graph definded as follows: $V=[n]=\{1,2, ... ,n\}$ and for all $i,j\in V$ so that $i\ne j$ we have $\{i,j\}\in\mathcal{E}$ with probability $p$. Where $p\in[0,1]...
mkultra's user avatar
  • 123
0 votes
0 answers
82 views

4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ...
Johnny Cage's user avatar
  • 1,543
12 votes
1 answer
526 views

Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?

$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The ...
Chris Ferrie's user avatar
5 votes
1 answer
114 views

Attacking a network at minimum cost

A target system is modelled as a giant, undirected, simple graph $G$ (simple meaning no hyperedge) that can be scrutinized in adequate detail to budget and plan the attack: its topology changes slowly ...
François Jurain's user avatar
2 votes
1 answer
768 views

Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$

Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following: ...
Learning math's user avatar
4 votes
0 answers
79 views

Expected number of bridges in a random subgraph

I am researching connectivity in random subgraphs and have come across the following problem. A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
Peter's user avatar
  • 175
3 votes
1 answer
212 views

Unique maximum degree in tournament

Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $p(n)$ denote ...
pi66's user avatar
  • 1,199
1 vote
1 answer
375 views

Size of minimum cut in random graph

Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
pi66's user avatar
  • 1,199
2 votes
2 answers
109 views

Difference between two largest degrees

Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $S$ be the ...
pi66's user avatar
  • 1,199
1 vote
1 answer
100 views

Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?

Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
Learning math's user avatar
1 vote
0 answers
27 views

Bound on the number of bridges between vertices in a sampled subgraph

I am researching connectivity in sampled subgraphs and have come across the following problem. A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
Peter's user avatar
  • 175
10 votes
4 answers
476 views

When is a large graph with a given degree sequence likely to be connected?

Are there any results on whether a large random graph with a given degree distribution is likely to be connected? In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions ...
Szabolcs Horvát's user avatar
1 vote
1 answer
243 views

Continuum percolation in 1d

What is known about continuum percolation in 1d? By this, I mean, for $d \in \mathbb{N}$, the Poisson-Boolean model of disks of radius $r_0 \in \mathbb{R}$ with centres arranged randomly in $[0,1]^{d}...
apg's user avatar
  • 612
8 votes
1 answer
393 views

Graphons and Graphs

The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and ...
Douglas W.'s user avatar
0 votes
1 answer
69 views

Small subgraphs of the random graph

If I look at the distribution of the number of small subgraphs in the random graph isomorphic to a connected graph $H$, this is asymptotically Poisson. What proportion of these small subgraphs ...
apg's user avatar
  • 612
4 votes
1 answer
241 views

Probability of a vertex being a "degree-celebrity" in a random graph

If $G(n,p)$ is a random graph of the Erdös-Rényi model, what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$ Please feel free to relate answers to other ...
Manfred Weis's user avatar
  • 12.6k
3 votes
0 answers
90 views

Largest component and number of components of random mappings with bounded in-degree

Let $S$ be a finite set of size $n$ and consider all functions $f$ from $S$ to itself, such that the preimage $f^{-1} (k)$ obeys $0 \leq |f^{-1} (k)| \leq m$. Let $F$ be chosen uniformly at random ...
mam's user avatar
  • 131
2 votes
1 answer
150 views

Electrode assignment problem in resistive networks

Main question In the context of resistor networks, and particularly purely from a graph theory point of view, is there a consistent way of assigning the two electrode nodes in order to compare the ...
user929304's user avatar
4 votes
1 answer
264 views

Probability of a subset of Bernoulli's being all 1's

Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
Marco's user avatar
  • 408
2 votes
0 answers
81 views

Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?

$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
Turbo's user avatar
  • 13.7k
2 votes
2 answers
246 views

Model for random graphs where clique number remains bounded

In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?
Nicolas Boerger's user avatar
2 votes
1 answer
258 views

Behaviour of global clustering for common random graph models

In order to develop some intuition for some of the commonly used random graph models, I've been looking at the global clustering coefficient as a means of comparing them. In particular, for the ...
user929304's user avatar
6 votes
0 answers
114 views

The properties of almost all directed graphs

A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
Aidan Rocke's user avatar
  • 3,827
4 votes
1 answer
145 views

Almost all simple graphs are small world networks

Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
Aidan Rocke's user avatar
  • 3,827
3 votes
1 answer
316 views

Eigenvalues of random graphs

At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
pgiacome's user avatar
  • 101
2 votes
2 answers
194 views

Is there a way to generate a graph of specified treewidth

The treewidth is a parameter of the graph that describes its similarity to a tree. Treewidth is NP-hard to find. For the introduction please see wikipedia The question is how to generate interesting ...
qbit-'s user avatar
  • 23
3 votes
1 answer
378 views

Difference of pseudoinverse bound under assumptions

This seems like a standard problem, but unable to find a solution online. Suppose we have two singular PSD matrices A and B with the following assumptions: $ 0 < x \leq ||A|| \leq y$ $ 0 < ||...
MJagota's user avatar
  • 33
3 votes
1 answer
537 views

Asymptotic formula for the number of connected graphs

It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality: \begin{equation} \lvert G_N \rvert = 2^{N \choose 2} \tag{1} \end{equation} Recently, I wondered how much bigger $\...
Aidan Rocke's user avatar
  • 3,827
2 votes
0 answers
24 views

Edgeweight-Conditions for "Statistically Self-similar" Complete Weighted Graphs

Given a complete symmetric weighted graph with $n$ vertices, for such a graph there always exists a minimum spanning tree and, under the assumption of the uniqueness of that tree, the vertex degrees ...
Manfred Weis's user avatar
  • 12.6k
1 vote
2 answers
115 views

How to use probability to find a matching in a family of graphs?

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
Henry Zagreb's user avatar
2 votes
2 answers
471 views

Modularity in a graph -- derivation of modularity score

Background I am currently reading "Modularity and community structure in networks" (2006) by Newman [1]. In it, he derives a score for the modularity of a graph ...
ngmir's user avatar
  • 121
2 votes
0 answers
61 views

Transversal deviation in first passage percolation

Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
apg's user avatar
  • 612
3 votes
1 answer
105 views

Expected size of matchings in a cubic graph

Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$? In other ...
LeechLattice's user avatar
  • 9,421
1 vote
1 answer
175 views

Figuring out a consistent definition for the percolation backbone

In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...
user929304's user avatar
5 votes
1 answer
218 views

Switching oriented paths in a graph

Consider an oriented graph (e.g. a finite part of the standard grid with some random orientations). Each minute the following operation takes place: we choose uniformly randomly an ordered pair $(A,B)...
Nikita Kalinin's user avatar
1 vote
1 answer
92 views

What is the expected distance between the sides of a random subgraph of the grid?

Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
Zur Luria's user avatar
  • 1,613
3 votes
1 answer
729 views

Open Problems in Random Graphs [closed]

I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
Henry Zagreb's user avatar
0 votes
2 answers
237 views

Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
hookah's user avatar
  • 1,096
7 votes
1 answer
245 views

Collecting proofs of the birth of the giant component

I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$. I know the original proof of Erdös-Rényi, the proof that ...
Johnny Cage's user avatar
  • 1,543
2 votes
2 answers
944 views

Non-backtracking random walk in regular (finite) graphs

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
Johnny Cage's user avatar
  • 1,543

1 2
3
4 5
7