All Questions
73 questions
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
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
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
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
1
vote
0
answers
46
views
Diameter of component graph of uniform spanning forests on the amenable transitive graph with super polynomial growth
According to the paper Benjamini, Kesten, Peres, and Schramm - Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12 (Annals, 2004), the diameter of the component graph of the ...
- 41
1
vote
1
answer
545
views
Vertex degree on random graphs
Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$,
where $G_{n,p}$ is a graph with $n$ vertices and the ...
- 21
4
votes
1
answer
217
views
Quasi-random vs pseudo-random graphs
My question is somehow concerning terminology on extremal graph theory.
Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
- 1,561
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
2
answers
725
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 557
1
vote
1
answer
152
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
- 3,446
3
votes
1
answer
192
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
- 3,446
5
votes
3
answers
840
views
Probability of an edge in a random graph
Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...
- 1,444
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
6
votes
1
answer
521
views
Graphs resembling the math genealogy graph must have concentration in a small number of families?
I was talking with a non-mathematician the other week at a workshop about the fact that many mathematicians, like myself, are indexed in the math genealogy database. We talked a little about how many ...
- 3,209
1
vote
1
answer
119
views
Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?
We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...
4
votes
1
answer
567
views
Random graphs and Benjamini-Schramm convergence
I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...
user130903
-1
votes
2
answers
421
views
How to define probability over graphs?
How can one formally define a random graph variable?
If G is a random graph variable, then any finite graph is a realization of G. Formally a r.v maps the set of outcomes to a measurable space (may be ...
- 1
23
votes
4
answers
979
views
What nodes of a graph should be vaccinated first?
Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node).
Choose some random number "K" of nodes which are "infected" initially.
So we ...
- 24.9k
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
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
6
votes
1
answer
421
views
Probability in Chromatic number upper bound of induced subgraph
Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced ...
- 61
4
votes
1
answer
1k
views
Critical probability for Erdos-Renyi digraphs to be strongly connected
Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
- 147
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
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,937
1
vote
0
answers
140
views
Count shortest path with different lengths in random graph
Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
- 1,495
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,209
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
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 ...
- 13.2k
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
287
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
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
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 ...
- 57
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
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)...
- 5,063
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 ...
- 57
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 ...
- 1,561
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
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
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
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 \...
- 151
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
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 ...
- 23
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
1
vote
0
answers
109
views
Number of $H$-free graphs
Sorry if this is basic for MO. But the people at SE couldn't help me.
I'd like to get an estimate on the number of (labeled) $H$-free graphs on $n$ vertices, i.e. graphs in which no set of $|V(H)|$ ...
- 11
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
14
votes
2
answers
387
views
What are some useful invariants for distinguishing between random graph models?
Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert model
...
- 29.2k
1
vote
1
answer
312
views
Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?
Let $G=(V,E)$ be an undirected random graph such that
$V$ is the set of nodes, and $E$ is the set of edges
Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, 40]$ ...
- 321
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
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1