All Questions
Tagged with pr.probability graph-theory
290 questions
3
votes
1
answer
276
views
Zero-one law in binomial random graph model $G(n,p)$
Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
- 39
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
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
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).
=================
...
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
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 ...
- 183
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 ...
- 367
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 ...
- 519
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 ...
- 113
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
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
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
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 ...
- 31
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
...
- 29.2k
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 \...
- 341
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
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 ...
- 367
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 ...
- 1
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 ...
- 151k
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
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....
- 355
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 \...
7
votes
1
answer
191
views
Is there a Degenerate Dependency Local Lemma?
The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...
- 19k
5
votes
0
answers
136
views
What's the variance in the Six Degrees model?
Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.
I interpret the punchline as saying that if I start ...
- 30.3k
1
vote
0
answers
255
views
Multiple Bipartite graphs and matchings
I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
- 903
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
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
2
votes
2
answers
220
views
Removing subtrees
Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...
- 11.3k
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
0
votes
0
answers
216
views
Computation on Random Bipartite graphs
I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...
- 903
1
vote
1
answer
353
views
Probability of each edge in K-clique [closed]
For $c \in R$ and $k \in N$, $k \geq 3$ let
$p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$.
I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
- 75
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
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
3
votes
2
answers
440
views
Graph game minimum vertex degree
Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):
BR claims an unclaimed edge from $E$, adds it to ...
- 75
4
votes
0
answers
220
views
Navigation in a graph
The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...
- 323
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 ...
- 355
5
votes
1
answer
705
views
Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question
Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ fixed)...
- 123
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
1
answer
115
views
mean length of the non-crossing graphs on n points
My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
- 1,352
7
votes
2
answers
335
views
Wait time to grid network disconnection with failing edges
Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node
connected to its four neighbors, with the top row connected to the bottom,
and the right column connected to the left.
Suppose ...
- 151k
4
votes
2
answers
2k
views
Do Random Walks on the Hexagonal Lattice have a limit?
For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of $\mathbb{R}^...
- 3,245
4
votes
0
answers
184
views
Does the concept of connective constant make sense for any tiling of the plane?
First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...
- 3,245
5
votes
1
answer
261
views
Epidemic threshold
Need some help / ideas to proceed. Stuck for a while on this.
In the literature of epidemic theory, it is found that the epidemic threshold is $1/\lambda_{\max}(A)$ where $\lambda_{\max}(A)$ is the ...
- 355
6
votes
0
answers
172
views
Uniformly sampling from the set of all simplicial maps
Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial maps ...
- 15.5k
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 ...
12
votes
1
answer
419
views
Coloring $K_n$ via edge-weight sums
This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...
- 151k
4
votes
3
answers
4k
views
Stationary distribution for bipartite graph
I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...
- 51