All Questions
Tagged with pr.probability graph-theory
290 questions
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,687
2
votes
2
answers
110
views
Difference between two largest degrees
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$.) Let $S$ be the ...
- 1,209
0
votes
0
answers
39
views
hypergraph product that preserve expansion properties
I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...
- 63.9k
1
vote
0
answers
61
views
What is the minimal $m$ for which the independence graph is $n$-universal?
Suppose, an $m$ sided die is rolled. Let's define the independence graph $I_m$ as a graph with the set of all possible events as vertices, and edges between two events iff they are independent.
...
- 2,618
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 ...
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 ...
- 10.4k
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 ...
- 680
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 ...
- 8,992
4
votes
1
answer
245
views
Probability of a vertex being a "degree-celebrity" in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other ...
- 4,746
0
votes
0
answers
145
views
Finding expectation of size of a subgraph
I have been trying to implement a algorithm but got stuck in finding expectation of the size of the subgraph.
n - size of the network.
d - at most number of communities a node could participate ...
- 2,821
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
286
views
Behaviour of global clustering for common random graph models
In order to develop some intuition for some of the commonly used random graph models, I've been looking at the global clustering coefficient as a means of comparing them. In particular, for the ...
- 128k
3
votes
1
answer
337
views
Eigenvalues of random graphs
At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
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
5
votes
1
answer
222
views
Switching oriented paths in a graph
Consider an oriented graph (e.g. a finite part of the standard grid with some random orientations).
Each minute the following operation takes place: we choose uniformly randomly an ordered pair $(A,B)...
CommunityBot
- 1
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
3
votes
2
answers
1k
views
Non-backtracking random walk in regular (finite) graphs
I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
- 37.7k
2
votes
1
answer
232
views
If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?
Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting ...
- 14.2k
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 ...
- 14.2k
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 ...
- 23k
1
vote
0
answers
117
views
Entropy of endpoints of a random walk in a dense graph
Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$.
Let $X$ be a random vertex of $G$ chosen proportional to ...
- 761
3
votes
1
answer
108
views
Expected size of matchings in a cubic graph
Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?
In other ...
- 37.7k
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 ...
- 101
2
votes
1
answer
607
views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
- 4,713
3
votes
1
answer
822
views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
- 151k
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
3
votes
1
answer
206
views
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
- 649
0
votes
1
answer
3k
views
How to compute the clustering coefficient of a random graph?
How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient ...
CommunityBot
- 1
12
votes
3
answers
1k
views
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
- 470
1
vote
0
answers
86
views
A Random Graph Process
I'd like to understand the following random graph process. I'm not sure if it's difficult or straightforward, so apologies if this is below the level of mathoverflow, but I've gotten no response on ...
- 345
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
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$
$$\...
- 13.6k
4
votes
2
answers
4k
views
Expected global clustering coefficient for Erdős–Rényi graph
What is the expected global clustering coefficient $\mathbb{E}[C_{GC}]$ for the Erdős–Rényi random graph (ER-graph) $\mathcal{G}(n,p)$ (expectation is over the ensemble of all ER-graphs) as $n \...
2
votes
1
answer
90
views
Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?
This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix?
In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
- 30.1k
3
votes
1
answer
184
views
Why is number of single cell clusters always greatest in a random matrix?
Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
- 4,589
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 ...
- 54.2k
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
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 ...
- 13.6k
2
votes
1
answer
299
views
Can this particular random matrix model be converted/related to any existing graph theory model?
Context:
This a sequel to the question: Is the Erdős–Rényi giant component result applicable here?
Consider a matrix whose elements are independently assigned a value
$1$ with probability $p$ ...
- 13.6k
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 ...
CommunityBot
- 1
2
votes
2
answers
357
views
Is the Erdős–Rényi giant component result applicable here?
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 ...
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 "...
- 13.6k
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 ...
- 12.9k
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 ...
- 2,545
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 ...
- 24.8k
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} ...
- 233
4
votes
1
answer
669
views
Number of independent sets of a random tree
Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average ...
- 37.7k
14
votes
2
answers
2k
views
A random walk on an infinite graph is recurrent iff ...?
Q. Is there a master theorem that can be used to determine whether or not
a simple random walk (choose a random neighboring vertex as the next step)
on a given infinite graph
leads to ...
- 151k
0
votes
1
answer
181
views
Bound on queries to a tree with unusual probabilties -- follow-up
This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...
- 209
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