All Questions
Tagged with random-graphs probability-distributions
12 questions
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 ...
- 4,219
1
vote
0
answers
89
views
Gamma and Poisson distributions and their relations to the randomness
I'm reading the following paper:
https://academic.oup.com/bioinformatics/article/32/1/122/1743683
and in Figure 3 (Section 4.4) the authors have shown some vertex degree distributions:
enter image ...
1
vote
0
answers
68
views
A one-sided/monotone version of min/max-stable distributions -- does this have a name?
In a couple of papers I am working on (in random graph theory) I have encountered the following property of certain probability distributions, which I will describe shortly, and I am wondering if this ...
- 5,429
1
vote
1
answer
602
views
Hammersley-Clifford theorem
The paper spatial interaction and the statistical analysis of lattice systems by Besag (1974) presents an alternative proof for the Hammersley-Clifford theorem.
In order to prove the HM theorem, Besag ...
- 128k
1
vote
0
answers
105
views
Understanding the finale of the proof of Komlós' and Szemerédi's limit distribution of Hamiltonian random graphs
My question is about the end of the proof of Theorem 1 in [Komlós, Szemerédi (1983)], more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my ...
- 71
-2
votes
1
answer
82
views
Ensemble averaging in a random graph (or network) in the large $N$ limit [closed]
I have a random graph/network described by the adjacency matrix $(a_{ij})_{N\times N}$ where $a_{ij}=1$ with probability $p$. Each node in the graph is associated with a continuous quantity $\eta_i=\...
- 137
2
votes
1
answer
900
views
Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$
Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following:
...
- 1,465
1
vote
1
answer
104
views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
- 188k
1
vote
0
answers
166
views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
- 13.9k
1
vote
0
answers
255
views
Multiple Bipartite graphs and matchings
I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
- 903
0
votes
0
answers
216
views
Computation on Random Bipartite graphs
I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...
- 903
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....
