All Questions
Tagged with pr.probability graph-theory
290 questions
9
votes
1
answer
526
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
Problem: Consider a random walk on the lattice $\mathbb{Z}^2$ where on each iteration a particle either stays at its current location or moves to a neighboring vertex with probability 1/5. We start ...
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
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 ...
8
votes
3
answers
1k
views
Singularity of sparse random matrices
The following topic came up in conversation with my office-mate Lionel: Let $p$ be a fixed prime, $c$ a fixed positive real parameter and $n$ a large number. Consider a random $(0,1)$ matrix with ...
- 156k
8
votes
2
answers
339
views
Does entropy of the random walk control the return probability
Given an infinite connected graph $G$ of bounded degree with vertex set $X$, let $P_x^n$ the time $n$ distribution of the simple random walk started at the vertex $x$ (so $P^n_x(y)$ is the probability ...
- 4,432
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
8
votes
0
answers
304
views
"Meritocratic" pyramid schemes
There have been a couple of times in my life when people from multi-level marketing organizations attempted to recruit me. I listened to what they had to say, and both times I did not get involved ...
- 2,075
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
7
votes
3
answers
801
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II
For some context see Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
As per Noah's answer and JBL's comment this was false as stated. However, I think the following ...
7
votes
3
answers
1k
views
Randomly contracting edges of a graph - expected number of vertices?
Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.
I would like to compute (or at least obtain a lower bound) for $E[|V(G')|]$ in ...
- 3,463
7
votes
2
answers
2k
views
Assigning positive edge weights to a graph so that the weight incident to each vertex is 1.
Let $\Gamma=(G,E)$ be a connected undirected graph, with no loops or multiple edges. $G$ is finite or countably infinite. For each edge $e=\{x,y\}\in E$, we assign a positive, symmetric edge weight $...
- 269
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
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
7
votes
1
answer
382
views
Diameter bound for graphs: spectral and random walk versions
This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
7
votes
2
answers
1k
views
Why is the spectrum of Erdős–Renyi random graph approximately symmetric?
I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,
and $np\to c=2,3$.
The plots above are already ...
- 715
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
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
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
7
votes
1
answer
222
views
Bound on queries to a tree with unusual probabilities
Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
- 209
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 ...
- 1,769
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
7
votes
0
answers
100
views
The uniform odd and even subgraph of $\mathbb{Z}^2$
Given a (first finite and later infinite) graph $G =(V,E)$ the uniform even graph is the uniform probability measure on the set of spanning even subgraphs. That is subgraphs (V, E') with $E' \subset E$...
- 1,054
7
votes
0
answers
171
views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,462
6
votes
2
answers
725
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 557
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
6
votes
1
answer
521
views
Graphs resembling the math genealogy graph must have concentration in a small number of families?
I was talking with a non-mathematician the other week at a workshop about the fact that many mathematicians, like myself, are indexed in the math genealogy database. We talked a little about how many ...
- 3,209
6
votes
2
answers
729
views
Has the following kind of (minimum degree $d$) random graph been studied?
The following random construction is simple enough that I am guessing it must have been studied. Fix $d \ge 3$, and let $n > d$. For each of the $n$ vertices, pick exactly $d$ other vertices to ...
- 7,857
6
votes
3
answers
790
views
'Focusing' the mass of the Probability Density Function for a Random Walk
Consider a random walk on a two-dimensional surface with circular reflecting boundary conditions (say, of radius 'R'). Here, for a fixed-size area, one finds a larger fraction of the probability ...
- 811
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
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
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
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
6
votes
1
answer
644
views
Random path in a graph
Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
- 4,432
6
votes
2
answers
720
views
Local concentration of measure on Erdos-Rényi graph
Let $G_n=(V_n,E_n)$ be an Erdos-Rényi random graph, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ ...
- 293
6
votes
1
answer
356
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
6
votes
1
answer
595
views
Number of connected components in a graph from G(n,m)
Hello,
$G(n,m)$ is the family of all graphs with $n$ vertices and $m$ edges (I consider $m < n$).
Each graph in $G(n,m)$ is selected with uniform probability.
What is the probability that the ...
- 61
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
- 7,545
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
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
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
5
votes
3
answers
314
views
Tracking automorphism groups of graph processes
Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...
- 15.5k
5
votes
1
answer
774
views
Probabilities of a random walk exiting a set
Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...
- 4,432
5
votes
1
answer
272
views
Random graphs nonisomorphic to unit distance graphs
I've encountered an interesting problem but can solve it only partially:
Prove that random graph $G\sim G\left(n,\frac cn\right)$, $c=const$, almost surely is isomorphic to some unit distance graph ...
- 75
5
votes
1
answer
708
views
First Passage Percolation on Trees
Let $T$ be a rooted Galton-Watson random tree generated accordingly to a probability distribution $\mu$. Now assign to each edge $e$ a random non-negative weight $w_e$ distributed a accordingly to a ...
- 3,626
5
votes
1
answer
980
views
"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?
Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
- 53
5
votes
2
answers
474
views
Another graph characteristic
This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...
- 9,720
5
votes
3
answers
840
views
Probability of an edge in a random graph
Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...
- 1,444
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
5
votes
1
answer
281
views
Transfer-impedance matrix for edge correlations in random spanning tree
Suppose $G$ is a (weighted) connected graph and
let $T$ denote a random spanning tree of $G$,
chosen uniformly (or respecting the edge weights).
It is known that for any distinct edges $e, f$
$$\...
- 2,175
5
votes
1
answer
1k
views
Intuition on Kronecker Product of a Transition Matrix
Let $T$ be a $N\times N$ transition matrix for a markov chain with $N$ states. Thus $T_{ij}$ is the probability of transition from state $i$ to state $j$ (and thus rows summing to one). Now consider ...
- 1,421