All Questions
Tagged with pr.probability graph-theory
290 questions
1
vote
1
answer
91
views
Probability process involving blocking paths of rooted tree
Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that
(i) Every root-leaf path of $T$ contains at least ...
- 3,475
4
votes
1
answer
567
views
Random graphs and Benjamini-Schramm convergence
I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...
user130903
-2
votes
1
answer
181
views
Stationary distribution of a weighted directed acyclic graph
Is there any way to calculate the equilibrium (stationary) distribution for a weighted directed acyclic graph?
Some references emphasized adjacency matrix to be symmetric.
https://arxiv.org/abs/1012....
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
3
votes
1
answer
153
views
Randomized version of Turán's theorem II
$\newcommand{\om}{\omega}$Let $\om(G)$ denote the number of vertices in a largest clique of an (undirected) graph $G$ with the set $[n]:=\{1,\dots,n\}$ of vertices. Then
\begin{equation}
\om(G)\ge\...
- 128k
5
votes
1
answer
209
views
Randomized version of Turán's theorem
Turán's theorem says the following.
Take any natural $n$ and $r$. Suppose that
\begin{equation*}
|G|>\Big(1-\frac1r\Big)\frac{n^2}2, \tag{0}
\end{equation*}
where $|G|$ is the number of edges of ...
- 128k
0
votes
0
answers
133
views
is there an example in planar graph that using probabilistic methods
The probabilistic method is a technique for proving the
existence of an object with certain properties by showing that
a random object chosen from an appropriate probability
distribution has the ...
- 1,851
-1
votes
2
answers
421
views
How to define probability over graphs?
How can one formally define a random graph variable?
If G is a random graph variable, then any finite graph is a realization of G. Formally a r.v maps the set of outcomes to a measurable space (may be ...
- 1
9
votes
2
answers
1k
views
An elementary question in bond percolation
Consider a locally finite, connected graph and "bond (edge) percolation" on this graph. Each edge is open with probability $p.$ There is a parameter $\alpha$, $0<\alpha<1.$
The ...
2
votes
1
answer
298
views
Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm
Take the traveling salesman problem, but with three slight twists:
You can choose a different start vertex for each of the two algorithms.
Each path from one vertex to another is of unique, arbitrary ...
- 21
4
votes
3
answers
247
views
Does there exist a non-recurrent acyclic graph with sublinear expansion?
Let $\Gamma$ be a simple, locally finite, acyclic graph. Let $v_0$ be some vertex in $\Gamma$.
We let $X_n$ denote the simple random walk on $\Gamma$ where $X_0 = v_0$. If we almost surely have $\...
- 3,499
1
vote
0
answers
75
views
Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?
Sorry for the verbose title, but the question is super specific. If you happen to know a site better suited for these types of question, feel free to direct me.
The article to which I am referring to ...
- 151
23
votes
4
answers
979
views
What nodes of a graph should be vaccinated first?
Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node).
Choose some random number "K" of nodes which are "infected" initially.
So we ...
- 24.9k
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
- 129
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
0
votes
1
answer
75
views
The probability of generating a ring graph by following the Erdos-Renyi model G(N,p) [closed]
The Erdos-Renyi random graph model G(N,p) describes a way to generate a network with N nodes, the probability that there is a link between any two nodes is p. I am wondering about the probability of ...
- 13
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
10
votes
2
answers
270
views
Maximal in-degree in directed voting graph
Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...
- 48.9k
0
votes
1
answer
77
views
Fourth moment of a random-variable with block-tridiagonal structure
Let x be a random variable in $\mathbb{R}^d$, $J$ a block tridiagonal $d\times d$ matrix, and probability of $x$ is defined as follows
$$p(x)\propto \exp(-x'Jx)$$
For a fixed $d\times d$ matrix $v$ ...
- 2,252
3
votes
1
answer
166
views
Reference request - random regular graphs vs random graphs w/ degree sequence
There are some properties that are easily studied for random d-regular graphs, but that are very hard to extend to random graphs with a given degree sequence (e.g. whether a graph is w.h.p. ...
- 435
6
votes
1
answer
421
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 ...
- 61
2
votes
1
answer
843
views
Interpretation of probability statements in Nina Zubrilina's paper
I asked this question on Math.stackexchange but got no answer.
In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is
$$\operatorname{...
- 41
7
votes
1
answer
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495
11
votes
2
answers
353
views
Exponential decay of voltage potential difference
Consider the following adjacency matrix of a complete graph:
$$A=(e^{-|i-j|})_{1\leq i\neq j\leq n}$$
with 0 on the diagonal. Let $D=diag\{d_1,...,d_n\}$ be the degree matrix where $d_i=\sum_{j\neq i}...
- 1,495
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$...
- 147
6
votes
0
answers
301
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 ...
- 1,444
11
votes
1
answer
370
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 ...
- 6,937
4
votes
1
answer
158
views
Support of random closed walk in arbitrary graph
Researching a question related to closed walks on graphs, I have come across the following problem. Let $G$ be a connected graph on $n$ vertices and $k=O(\log(n))$. Pick a random closed walk on $G$ as ...
- 175
1
vote
0
answers
223
views
Expected number of directed cycle in a directed complete graph
Consider the randomized, directed complete graph G = (V, E) where for each pair of vertices u, v ∈ V, we add either the directed edge (u → v) or the directed edge (v → u) chosen uniformly at random. ...
- 19
1
vote
0
answers
140
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 ...
- 1,495
6
votes
2
answers
2k
views
How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?
I have a question about the combinatorial Laplacian $\Delta$ which is defined by
$$\Delta(u,v)=c(u)1_{u=v}-c(u,v)$$
where $u, v$ are some vertices in the graph $G=(V, E)$, and $c(u,v)$ is a ...
- 288
1
vote
0
answers
54
views
Age of the most recent common ancestor for the neutral Wright-Fisher model
The neutral Wright-Fisher model with $n$ individuals is a genealogical model often used in population genetics that can be described as follows: at all generations, there are exactly $n$ individuals, ...
- 11
1
vote
0
answers
45
views
What is the number of iterations needed for the message passing algorithm to converge when applied to an acyclic factor graph?
I understand that the message passing algorithm (Belief Propagation algorithm), when applied to a factor graph consists in an exchange in messages between the factor nodes and the variable nodes, ...
- 39
6
votes
1
answer
361
views
Random walks on infinite directed regular graphs
Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...
- 26k
1
vote
1
answer
436
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 ...
- 1,209
2
votes
2
answers
110
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 ...
- 1,209
0
votes
0
answers
39
views
hypergraph product that preserve expansion properties
I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...
- 340
1
vote
0
answers
61
views
What is the minimal $m$ for which the independence graph is $n$-universal?
Suppose, an $m$ sided die is rolled. Let's define the independence graph $I_m$ as a graph with the set of all possible events as vertices, and edges between two events iff they are independent.
...
- 2,618
7
votes
3
answers
330
views
Quantifying the noninvertibility of a function
Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
- 19.7k
1
vote
1
answer
267
views
Finding good flows to upper bound effective resistance
Thomson's principle for electrical networks states that if $G$ is a network (a weighted graph), $a$, $b$ are vertices of $G$, then the effective resistance between vertices $a$ and $b$ in $G$ is given ...
- 662
6
votes
2
answers
266
views
Lovasz local lemma for the edge model
In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...
- 2,339
4
votes
1
answer
245
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 ...
- 13.2k
2
votes
0
answers
321
views
Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?
In Bobkov and Tetali - Modified Log-Sobolev Inequalities, Mixing and Hypercontractivity (extended version Modified Logarithmic Sobolev Inequalities in Discrete Settings), at the beginning of section 3,...
- 105
2
votes
0
answers
83
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}...
- 13.9k
2
votes
1
answer
286
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 ...
- 649
3
votes
1
answer
337
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$...
- 101
4
votes
0
answers
672
views
Bayesian Networks and Polytree
I am a bit puzzled by the use of polytree to infer a posterior in a Bayesian Network (BN).
BN are defined as directed acyclic graphs. A polytree is DAG whose underlying undirected graph is a tree. ...
- 41
4
votes
1
answer
594
views
Martingales and intersection of random walks
Let $G=(V,E)$ be a graph with $n$ vertices. Consider a pair of independent simple random walks $(X,Y)$ on the graph, each of length $L$ starting from a node $v \in V$. We denote a length-$L$ random ...
- 519
7
votes
1
answer
498
views
Understanding Gillman's proof of the Chernoff bound for expander graphs
My question is about the proof of Claim 1 in this paper: Gillman (1993).
At the end of the proof, the author says:
The matrix product $U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$, ...
- 105
6
votes
1
answer
225
views
Restricted independent set of the cycle graph $C_{3n}$
Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.
QUESTION: Is it possible ...
- 9,501