All Questions
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 ...
- 1,190
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
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
5
votes
1
answer
209
views
Randomized version of Turán's theorem
Turán's theorem says the following.
Take any natural $n$ and $r$. Suppose that
\begin{equation*}
|G|>\Big(1-\frac1r\Big)\frac{n^2}2, \tag{0}
\end{equation*}
where $|G|$ is the number of edges of ...
- 128k
1
vote
0
answers
75
views
Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?
Sorry for the verbose title, but the question is super specific. If you happen to know a site better suited for these types of question, feel free to direct me.
The article to which I am referring to ...
- 151
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
4
votes
1
answer
141
views
Fuzzy layers in graphs and neural networks
I wonder if the following statistical description of the layer architecture of finite graphs has been considered before and where I can find some references (especially under which name).
Consider a ...
- 9,720
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....
- 163
4
votes
2
answers
1k
views
Probability distribution over cluster size in Erdős–Rényi random graph.
My question is about the probability distribution over the possible size of the containing cluster of a randomly chosen node in an Erdős–Rényi random graph.
Let G(n,p) be an Erdős–Rényi random graph (...
- 41
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$ ...