All Questions
Tagged with pr.probability graph-theory
290 questions
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
508
views
Proof and interpretation of the following percolation theory result for $n\times n$ square grid
While I was discussing this question with @JamesMartin, he mentioned a result here that:
In a $n\times n$ finite square grid, if $p\geq p_c+\epsilon$, such
that $\epsilon>0$ and $p_c$ is the ...
user123818
2
votes
0
answers
173
views
Why do larger random matrices maximize their number of clusters with lower densities?
Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$.
Define a cluster of cells as a maximal connected component in the ...
- 41
2
votes
0
answers
103
views
Is this correct: Inflection points of Euler number graph in Island-Mainland transition correspond to spanning cluster site percolation threshold?
I'm writing with respect to the paper Khatun, Dutta, and Tarafdar - "Islands in Sea" and "Lakes in Mainland" phases and related transitions simulated on a square lattice.
Here's a link to a PDF ...
user119567
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
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
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 ...
2
votes
0
answers
66
views
Fixing (non)-independency of a the subfamilies of finitely many events.
I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...
- 166
2
votes
0
answers
83
views
Asymptotic results in unbalanced left $d$-regular expander graphs
Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...
- 409
2
votes
0
answers
108
views
Shortest loop containing 0 in continuum percolation
I am interersted in continuum percolation with intensity $\lambda>0$. Formally, let $X$ be a Poisson point process in $\mathbb{R}^d$ with intensity $\lambda$ and $G$ the graph obtained by ...
- 1,352
2
votes
0
answers
81
views
Subgraphs of bounded tree-width and preserving edges of original graph
Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties:
Each edge of $G$ has at least some probability $p$ of going into $G'$
The ...
- 3,475
2
votes
0
answers
285
views
Connectivity in random points on a grid using a rope of fixed length.
This problem is a by product of another problem. I would like to restate this problem as a sort of a puzzle.
Suppose we have a $l \times b$ grid. We select $k$ points on the grid randomly and ...
- 21
1
vote
1
answer
313
views
Expected length of the shortest polygonal chain connecting N random points in the unit square
N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...
1
vote
2
answers
2k
views
Proving a random bipartite graph contains a perfect matching
I have the following problem
consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...
- 903
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 ...
- 1,769
1
vote
2
answers
2k
views
Probability of first return to starting vertex in Random walk on regular finite graph
Hi, this is related to this earlier question.
Given Random walk on a regular graph $G=(V,E)$. The Random walk is simple so that transition probabilities are $1/\text{deg}(v_i)$, and time is in ...
- 65
1
vote
1
answer
173
views
Could you provide some TSP examples from real world to test a new algorithm?
It's well known that to find a hamilton cycle is NPC, while TSP is NPH.
But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
- 175
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]$ ...
- 321
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 ...
- 903
1
vote
1
answer
119
views
Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?
We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
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
1
vote
2
answers
116
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 ...
- 57
1
vote
1
answer
114
views
Probability for a group of stones to live on an infinite Go board
Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
- 5,169
1
vote
1
answer
330
views
Probability of connected graph on torus
Let $G = (V, E)$ be a graph on n vertices constructed in the following way:
Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$.
Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...
- 75
1
vote
2
answers
323
views
Correlation in graph coloring
Let $G$ be a (simple) graph.
Given $k \ge \chi(G)$, define $Cor(G,k,u,v)$ to be the proportion among all $k$-colorings of $G$ for which the vertices $u$ and $v$ have the same color.
Questions:
...
- 11
1
vote
1
answer
545
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 ...
- 21
1
vote
1
answer
152
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$ ...
- 3,446
1
vote
1
answer
183
views
Expectation of edge weights on the complete graph
Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
- 26.9k
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
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
1
vote
1
answer
188
views
KPZ relation $\chi = 2 \xi -1$ in a random geometric graph
If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
- 640
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 ...
- 24.2k
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$...
user82424
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 ...
- 903
1
vote
1
answer
295
views
Equivalent Markov Random Fields
Hi,
Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ?
Thanks!
- 167
1
vote
0
answers
41
views
Asymptotic mixing time and Euclidean probability distance for path graphs
We are given a simple path graph $P(V,E)$ with vertex set $V$ and edge set $E$, having $n=|V|$ nodes. Given an initial distribution $\mathbf{\mu}$ over $V$, let $d_t(\mathbf{\mu},\pi)$ be defined as $\...
- 1,677
1
vote
0
answers
72
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 359
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
1
vote
0
answers
84
views
Percolative process distribution not equivalent to coupon collector problem distribution
I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
- 47
1
vote
0
answers
62
views
Nonintersecting witnesses of connectivity events in graphs
In my research I stumbled across a following result:
Let $G = (V, E)$ be a multigraph with three chosen vertices $a, b, c \in V$. We color its edges into red and blue colors: $E = R \sqcup S$. Events ...
1
vote
0
answers
60
views
Correct dependence for "Local Coloring"
In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
- 3,499
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 ...
- 41
1
vote
0
answers
86
views
Min-sum belief propagation not working on a chain model with equal unary potentials
Given is a chain factor graph as presented in the image below with the following properties:
Each node can take values 0 or 1
All unary potentials are equal (e.g. $U(a)=0$) for every node $a$
All ...
1
vote
0
answers
340
views
Random walk on non-abelian free group
Let $F_2$ be the free non-abelian group with generators $a, b\in F_2$.
Has the "random walk" where we start with the identity and then multiply it by $a$ or $b$ or $a^{-1}$ or $b^{-1}$ ...
- 11
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
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
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
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