All Questions
Tagged with pr.probability graph-theory
85 questions with no upvoted or accepted answers
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
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
10
votes
0
answers
742
views
Torus Graph Dynamics
Consider the torus graph, or the toroidal grid, which looks like
(The graph's vertices are the bold dots).
I will discuss only square torus graphs, where there is an equal number of vertices in a "...
- 403
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
10
votes
0
answers
533
views
Abelian sandpile models
This question is about a popular probabilistic model on graphs studied in physics, mostly, for the standard lattice in ${\mathbb R}^n$ but also on other graphs (this model is of the same spirit as ...
user6976
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
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
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
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
4
votes
0
answers
118
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
- 48.9k
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
4
votes
0
answers
672
views
Bayesian Networks and Polytree
I am a bit puzzled by the use of polytree to infer a posterior in a Bayesian Network (BN).
BN are defined as directed acyclic graphs. A polytree is DAG whose underlying undirected graph is a tree. ...
- 41
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
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
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
4
votes
0
answers
183
views
Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)
Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, i....
- 163
4
votes
0
answers
128
views
Metrized categories
Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let $\...
- 8,512
4
votes
0
answers
256
views
Graph distance of close points within the minimum spanning tree
My question is the following: Given $N$ uniform IID points $X=(X_1,...,X_N)$ on the unit cube of $\mathbb{R}^d$, take $X_1$ and another point, say $X_{(1)}$, "close" to $X_1$ (i.e. connected to $X_1$ ...
- 1,352
4
votes
0
answers
617
views
Expected number of components with multiple cycles in a subgraph of a square lattice
Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the edge-...
- 1,444
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
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
3
votes
0
answers
87
views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 6,353
3
votes
0
answers
190
views
Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree
We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$.
In a sequential fashion, we select ...
- 1,677
3
votes
0
answers
83
views
Growth models with lookahead
Given a connected graph $G$ with a connected subgraph $H$, we can consider the uniform distribution on the set of all sequences $H_0, H_1, \dots, H_r$ where $r = |E(G) \setminus E(H)|$, $H_0 = H$, $...
- 19.7k
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
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
3
votes
0
answers
474
views
What is the expected Cheeger constant of a random graph?
Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would ...
- 29.2k
3
votes
0
answers
146
views
The mean number of vertices in small connected components of random geometric graphs
I place $N$ points on a circular plane of radius $R$, and draw edges to connect points that are less than or equal to some distance $D$ to form a set of graphs or cliques $G_i$. As a function of $N$, ...
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
2
votes
0
answers
51
views
Subgraphs of random graphs with a given degree sequence
Let $\mathbf{d}=(d_1,\dots, d_n)$ be a given degree sequence with $3\leq d_i\leq \Delta$ for every $i$, where $\Delta$ is constant. Let $G(n,\mathbf{d})$ denote the random graph uniformly distributed ...
- 143
2
votes
0
answers
215
views
An approach to the prime number theorem with Rademacher variables and a recursive formula for the prime pi function?
Consider the bipartite graphs defined here:
Why is this bipartite graph a partial cube, if it is?
We do random walks on them with equal propability and since the graphs are finite and connected the ...
- 3,064
2
votes
0
answers
90
views
Odd $k$-cycle counts in graph with adjacency matrix $A$ is leading term in $\operatorname{tr} A^k$?
In a recent paper of Neeman, Radin, and Sadun, Moderate Deviations in Cycle Count, in the first line of section 7.3 they wrote $\tau_k(A)=\frac{\operatorname{tr}A^k}{n^k}+O(\frac 1n)$, but I don't ...
- 715
2
votes
0
answers
344
views
Probability that a graph and its complement are connected
It's well known that for any graph $G = (V,E)$ that if $G$ is not connected, then its compliment $\overline{G}$ is connected. So, it's impossible to have both $G$ and $\overline{G}$ be disconnected. ...
- 139
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
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
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
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