All Questions
Tagged with pr.probability graph-theory
290 questions
13
votes
1
answer
2k
views
Counting subtrees of a random tree ("random Catalan numbers")
Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number
of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).
...
- 4,922
11
votes
1
answer
435
views
(almost) statistical independence of nodes degrees in a graph
Wireless networks are typically modeled as random geometric graphs. The number of nodes $N$ in the network is drawn from a Poisson distribution with intensity $\lambda$
$$P(N = n) = \frac{\lambda^n ...
- 241
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
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$ (...
- 3,626
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
- 7,857
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
0
votes
1
answer
292
views
Probability of preserving connectivity between pair of vertices in weighted graph
Let $G=(V,E)$ be an undirected graph and $p \colon E \mapsto (0,1]$ defines weights of its edges.
Let's fix two connected vertices $v_1, v_2 \in V$.
Random graph $G'=(V,E')$ is obtained from $G$ by ...
- 3
9
votes
1
answer
695
views
Probability of return vs. probability of return in minimal number of steps
Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ ...
- 965
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
9
votes
1
answer
860
views
Random walk on a simple finite network
Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).
Take a random walker that wonders around ...
- 965
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 4,922
4
votes
0
answers
580
views
Monotonic properties of harmonic functions on graphs
I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
- 965
11
votes
3
answers
743
views
Rainbow matchings (in random graphs)
Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) ...
- 3,323
24
votes
6
answers
3k
views
Shortest grid-graph paths with random diagonal shortcuts
Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...
- 151k
11
votes
2
answers
880
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
- 4,922
3
votes
0
answers
229
views
For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?
Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(...
- 2,252
9
votes
3
answers
569
views
Statistics for Second order properties of Random graphs
Hi!
Let G(N) be the number of graphs with vertices {1, 2, ..., N} and GN(F) be the number of those of them which satisfy graph property F. There is a beautiful result by Glebskii and Fagin that limit ...
- 1,175
21
votes
11
answers
4k
views
What are some good examples of non-monotone graph properties?
It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is ...
- 7,857
3
votes
1
answer
472
views
Path cardinality for random $(a+b)$-ary infinite trees
Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching ...
- 995
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 ...
- 151k
12
votes
3
answers
1k
views
Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?
Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following ...
- 1,068
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
19
votes
5
answers
8k
views
What is the probability that two random walkers will meet?
It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will ...
- 301
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
2
votes
2
answers
487
views
Cover time of weighted graphs
Consider a connected graph $G$ with non-negative weights on each edge. The sum of edge weights is the same for each vertex, call this sum $W$. A random walk on the graph at vertex $u$ transitions an ...
- 89
4
votes
1
answer
232
views
Negative Association of Component Size in Random Hypergraph
I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d << k$ and $n = 4k d^2$ or so.
The hyperedges are placed independently uniformly at random. I would like to have a ...
- 241
10
votes
1
answer
527
views
Random geometric graphs and spanners
I would grateful to learn of work mixing
random geometric graphs with random graphs under
the
Erdős-Renyi model, and in particular concerning spanners.
Select $n$ points uniformly at random from the ...
- 151k
9
votes
1
answer
1k
views
Vertex connectivity of random graphs?
Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
- 383
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 ...
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 ...
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
- 24.7k
12
votes
3
answers
782
views
Connectedness of random distance graph on integers
This is not my field, a friend needs the answer for the following question. Suppose we have a decreasing probability function, $p: N \rightarrow [0,1]$ such that $sum_n p(n) = \infty$. Take the graph ...
- 19k
4
votes
6
answers
751
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
- 599
5
votes
1
answer
339
views
How to estimate the growth of the probability that $G(n, M)$ contains a $k$-clique
Let $k\geq 3$ be a fixed positive integer. Define
$t_k(M)=\Pr[G(n, M) \text{contains a}\ k-\text{clique}]$, where $G(n, M)$ is the random graph uniformly distributed on all $n$-vertex graphs with $m$...
- 363
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider ...
- 24.7k
0
votes
1
answer
307
views
How to estimate the fraction of graphs with small clique among the graphs with certain edges
Among all $n$-vertex graphs with $M$ edges and constant $k$, how to estimate the fraction of graphs of clique less than $k$? Thanks.
- 3
21
votes
6
answers
3k
views
"The" random tree
One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
- 68.9k
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
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