Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
35T41's user avatar
  • 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 ...
Xin Zhang's user avatar
  • 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_\...
Christopher King's user avatar
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 $...
Xin Zhang's user avatar
  • 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 ...
SMS's user avatar
  • 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 ...
none Yuan's user avatar
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 ...
Nir Kfir's user avatar
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 ...
Johnny Cage's user avatar
  • 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 ...
Dmytro Taranovsky's user avatar
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 ...
W. Paul Liu's user avatar
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$ ...
Antoine Labelle's user avatar
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 ...
Antoine Labelle's user avatar
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. ...
Matthieu Latapy's user avatar
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 ...
Karagounis Z's user avatar
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 ...
Josiah Park's user avatar
  • 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 ...
Bernard Vatant's user avatar
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 ...
user avatar
-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 ...
susheel's user avatar
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 ...
Alexander Chervov's user avatar
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 ...
lenhhoxung's user avatar
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. ...
DJA's user avatar
  • 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 ...
Ever Garden's user avatar
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$...
math_lover's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
Claus's user avatar
  • 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 ...
neverevernever's user avatar
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 ...
pi66's user avatar
  • 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 ...
pi66's user avatar
  • 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 ...
Manfred Weis's user avatar
  • 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}...
Turbo's user avatar
  • 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 ...
user929304's user avatar
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$...
Piero Giacomelli's user avatar
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 ...
Henry Zagreb's user avatar
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 ...
LeechLattice's user avatar
  • 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)...
Nikita Kalinin's user avatar
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 ...
Henry Zagreb's user avatar
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 ...
Johnny Cage's user avatar
  • 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 ...
user929304's user avatar
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 ...
Sam Spiro's user avatar
  • 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 ...
Joel's user avatar
  • 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 \...
Fabian Ying's user avatar
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 ...
apg's user avatar
  • 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 ...
John K's user avatar
  • 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^{...
Minkov's user avatar
  • 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)|$ ...
El Manolo's user avatar
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} ...
nikita.Popov's user avatar
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 ...
Paul Siegel's user avatar
  • 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]$ ...
Wieshawn's user avatar
  • 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 ...
Joseph O'Rourke's user avatar
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 ...
Sam's user avatar
  • 1