All Questions
Tagged with pr.probability graph-theory
290 questions
8
votes
2
answers
343
views
Cubic almost-vertex-transitive graphs with given spanning tree
Consider the infinite 3-regular tree. Pick a vertex $C$, the "center".
For any integer $L\ge 1$ consider the closed ball, in the graph distance, of radius $L$ around $C$. Let $T_L$ be the induced ...
2
votes
0
answers
159
views
Distribution of path probabilities for a finite absorbing Markov chain
I am interested in the distribution of path probabilities for a finite
absorbing (but otherwise well behaved) Markov chain. Has this topic
been considered in the literature?
A bit of Googling ...
- 15.4k
15
votes
2
answers
547
views
Random graphs in $\mathbb R^2$ (or random rays from $\mathbb Z^2$)
The model:
Suppose that for each lattice point in $\mathbb Z^2$ we pick a random direction uniformly and independently. At time $t=0$ we start drawing rays starting from each lattice point in the ...
- 13.6k
14
votes
2
answers
988
views
Properties of Some Random Graphs
Working in a problem the following family of graphs appears naturally. Consider the set $A_{n}=\{1,2,3,\ldots,n\}$ and let $\mathcal{C_{n}}$ be the set of all permutations of $A_{n}$ of order $n$ (...
- 221
3
votes
0
answers
98
views
Asymptotic results on statistical graph models
This post is partly inspired by this post.
Reference request: results on the asymptotic distribution of singular values related to a random orthogonal matrix
While it is well-known that two basic ...
- 8,071
4
votes
0
answers
249
views
Good introduction to Benjamini- Schramm limits [closed]
So I was wondering if someone might be able to suggest a good intro paper/ article for getting a feel for Benjamini- Schramm limits as well as getting a sense of the kinds of results that people have ...
- 29.8k
4
votes
1
answer
317
views
Infinite Tree with Poisson Clocks
Let $\mathcal{T}$ be the infinite countable $3$-regular tree graph. Pick a vertex in this graph, call it the root. Let the root carry the value $0$.
Next, assign $1$ to the neighbours of the root. ...
- 403
15
votes
2
answers
755
views
Random noncrossing chords of a circle
Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord.
The disk is then partitioned ...
- 4,713
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
- 1,643
8
votes
3
answers
602
views
Decimating the infinite grid graph
Let $G$ be the graph whose nodes are the points of
$\mathbb{Z}^d$ in the nonnegative orthant (i.e., all
coordinates are $\ge 0$), with edges connecting each
pair of points separated by unit distance.
...
- 151k
0
votes
0
answers
72
views
A random variable standing for the size of connected component including a given node in a tree
Suppose we have a tree $T = (V,E)$, in which each nodes $v_i \in V$ has a probability $p_i$ to vanish. Let $v_0\in V$, we define random variable $\boldsymbol{X} = \boldsymbol{X}(T, v_0)$ stands for ...
- 1,551
19
votes
2
answers
2k
views
Graph with Poisson Clock at each Vertex
Let $G$ be a connected, undirected graph, with countably infinite set of vertices and countably infinite set of edges. Assume that the degree of each vertex is finite, and moreover, the degrees of all ...
- 19k
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
0
votes
1
answer
463
views
Expected number of connected components as $V(G)$ grows large
Let $E^c_n$ be the expected number of connected components of a simple undirected graph on the vertex set $\{1,\ldots,n\}$. (Every possible edge in $\big\{\{a, b\}: a, b\in \{1,\ldots,n\} \land a \neq ...
- 4,991
7
votes
1
answer
222
views
Algorithm to generate random commuting permutations
I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In ...
- 8,688
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
4
votes
1
answer
141
views
Fuzzy layers in graphs and neural networks
I wonder if the following statistical description of the layer architecture of finite graphs has been considered before and where I can find some references (especially under which name).
Consider a ...
CommunityBot
- 1
5
votes
1
answer
479
views
Expected Size of Independent Set
Q. Let $G = (V, E)$ be a graph with $V = \{v_1, \cdots, v_n\}$ and $E = \{(v_i, v_{i+1}) \mid 1 \leq i < n\}$. If we repeatedly remove vertices from $G$ uniformly randomly until the set of vertices ...
- 109k
0
votes
0
answers
34
views
What kind of prior on edge existence would form graphs that are unions of complete (sub)graphs?
Suppose a graph has $n$ vertices.
First question: is it possible to give a (nontrivial) prior probability on edge existence so that if a graph is created by querying the prior on the $\binom{n}{2}$ ...
- 118
1
vote
0
answers
109
views
Number of $H$-free graphs
Sorry if this is basic for MO. But the people at SE couldn't help me.
I'd like to get an estimate on the number of (labeled) $H$-free graphs on $n$ vertices, i.e. graphs in which no set of $|V(H)|$ ...
- 11
4
votes
1
answer
568
views
inequality with exponents
We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v \...
CommunityBot
- 1
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 37.7k
10
votes
0
answers
222
views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
- 986
2
votes
1
answer
160
views
Do product distributions (or graph products) eventually cluster as more products are taken?
Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
CommunityBot
- 1
2
votes
0
answers
115
views
Influence of independent variables on boolean functions?
Suppose a simple connected graph $G$ where its vertices are assumed to be independent. An event with uncertainty corresponds to each vertex. My instructor guides me that even though the vertices (...
- 143
1
vote
0
answers
87
views
How to estimate the size of balanced biclique in random bipartite graph?
We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...
- 11
14
votes
2
answers
387
views
What are some useful invariants for distinguishing between random graph models?
Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert model
...
- 3,388
2
votes
1
answer
277
views
Proof that it's possible to colour all elements in set, that all subsets will be bicolored
(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact).
=================
...
- 13.4k
1
vote
1
answer
123
views
$q$-connectedness of random digraphs obtained from a fixed graph
Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).
Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...
- 28k
11
votes
2
answers
714
views
Pursuit-Evasion type game on graph ("Flyswatter game")
An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
- 14.2k
8
votes
1
answer
174
views
Equalizing Geometric means of Graph Cycles
Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
CommunityBot
- 1
0
votes
0
answers
168
views
A path optimisation problem
Consider a graph of $n$ nodes randomly located in $[0,1]^2$. Each node moves following a path randomly chosen from the set of all possible paths. Regard nodes as attackers. A policeman seeks an ...
- 8,597
2
votes
1
answer
285
views
Edge-perspective degree distribution
I was reading this paper when I came across something called the edge-perspective degree distribution in a network. Consider a graph $G$, the degree distribution of whose nodes is $f(d)$. They say the ...
- 1,897
1
vote
1
answer
242
views
Two types of random walkers on square lattice
Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index $1$...
CommunityBot
- 1
1
vote
1
answer
173
views
Probability of paths to the boundary of a tree
Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...
- 3,937
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
1
vote
0
answers
46
views
Is there an effective algorithm for finding "minimal discovery times" for large graphs?
Consider a large, probably sparse graph with Markovian random walkers on it.
Define the discovery time as the expected time to first reach a vertex by
random walk from a uniform start. Are there ...
- 19.6k
3
votes
1
answer
165
views
First passage percolation for general graphs
There have been many questions about the behavior of first-passage percolation on specific graphs. In particular, it seems like cliques, grids, random graphs, and ladders are well-studied. But I can't ...
- 23.2k
1
vote
1
answer
312
views
Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?
Let $G=(V,E)$ be an undirected random graph such that
$V$ is the set of nodes, and $E$ is the set of edges
Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, 40]$ ...
CommunityBot
- 1
6
votes
0
answers
149
views
Does squaring a directed random graph more than double its out-degree?
As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...
- 151k
7
votes
1
answer
757
views
Length of nearest neighbor path in travel salesman problem
Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...
CommunityBot
- 1
4
votes
1
answer
365
views
Expected number of leaf nodes in some theoretical graph models
If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of:
(A) a random graph (e.g., Erdos-Renyi graph),
(B) a small-world graph (e....
CommunityBot
- 1
0
votes
0
answers
165
views
Expected length of minimum spanning trees
For a simple, finite, connected and complete graph $K_n = (V(K_n), E(K_n))$ with vertex set $V(K_n)$ and edge set $E(K_n)$, we assign a non-negative independent and identical distributed random weight ...
- 10.9k
9
votes
4
answers
371
views
Diameter of random segment intersection graph?
I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...
- 2,158
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1
1
vote
1
answer
638
views
Threshold for perfect Matchings in Bipartite graph
Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...
- 31
1
vote
2
answers
2k
views
Expected matching in a bipartite graph
Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
- 4,589
0
votes
1
answer
560
views
Random walk on the hypercube
Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...
- 6,210
1
vote
0
answers
159
views
Probabilistic proof for expander existence [closed]
I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders).
I've been using the search ...
- 111
3
votes
1
answer
119
views
Create matrix containing values in [0,1] where sum of all diagonals and anti-diagonals is fixed
The problem I am facing sounds at first glance pretty simple. However, as very often, it seems more complicated than I first assumed:
I want to calculate a matrix $P = (p_{j,k}) \in \mathbb{R}^{n \...
