All Questions
Tagged with pr.probability graph-theory
290 questions
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$...
- 101
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 ...
- 9,501
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
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
3
votes
1
answer
376
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
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
3
votes
1
answer
761
views
Removing edges from Erdős–Rényi graph to make two nodes disconnected
Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says
"There ...
- 163
3
votes
1
answer
153
views
Randomized version of Turán's theorem II
$\newcommand{\om}{\omega}$Let $\om(G)$ denote the number of vertices in a largest clique of an (undirected) graph $G$ with the set $[n]:=\{1,\dots,n\}$ of vertices. Then
\begin{equation}
\om(G)\ge\...
- 128k
3
votes
1
answer
166
views
Reference request - random regular graphs vs random graphs w/ degree sequence
There are some properties that are easily studied for random d-regular graphs, but that are very hard to extend to random graphs with a given degree sequence (e.g. whether a graph is w.h.p. ...
- 435
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
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
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 \...
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
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 "...
user125648
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
2
answers
1k
views
expected number of cycles in a "random" bipartite directed graph
Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn ...
- 65
2
votes
2
answers
304
views
Uniformly random planar map
Is there a way to sample a planar map uniformly at random? I am aware of the Cori-Vauquelin-Schaeffer bijection that can be used to sample and study uniformly random quadrangulations. There are other ...
- 1,989
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 ...
- 41
2
votes
2
answers
286
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
- 1,190
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
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).
=================
...
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
2
votes
1
answer
199
views
Average cluster size of a n-size vector
Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector.
My goal is to calculate the average cluster size for all ...
- 47
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$ ...
user123818
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
2
votes
1
answer
141
views
Spanning subgaph with trivial Poisson boundaries
Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some $k$-...
- 4,432
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
2
votes
1
answer
156
views
Some identities from graph theory and probability
The other day I attended a seminar about probability. I took some notes and I am now revising it and trying to understand some steps that were omitted by the lecturer. To formulate my question, ...
- 1,305
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
- 129
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 ...
- 649
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 ...
- 121
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 ...
- 2,185
2
votes
1
answer
115
views
Randomly chosen walk of fixed length
Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...
- 138
2
votes
1
answer
248
views
Connected components in random regular graphs
Suppose we take a random regular graph $G_{2n, r}$, where $n$ is large. Let us also assume that $r$ is fixed, (not dependent on $n$). Let's say that half of the vertices of the graph are colored black ...
- 1,407
2
votes
1
answer
165
views
Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?
A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...
- 153
2
votes
1
answer
298
views
Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm
Take the traveling salesman problem, but with three slight twists:
You can choose a different start vertex for each of the two algorithms.
Each path from one vertex to another is of unique, arbitrary ...
- 21
2
votes
1
answer
843
views
Interpretation of probability statements in Nina Zubrilina's paper
I asked this question on Math.stackexchange but got no answer.
In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is
$$\operatorname{...
- 41
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 ...
user125648
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
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