Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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
7 votes
1 answer
156 views

Nearest neighbors on random complete graph

Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
David Aldous'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
0 answers
148 views

Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]

Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$. Question: Is (the simple random walk on) $G$ transient almost surely?
none Yuan's user avatar
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
723 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
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
1 vote
1 answer
125 views

Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution

I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following: Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...
MikeG's user avatar
  • 715
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
23 votes
4 answers
978 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
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,917
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
4 votes
1 answer
275 views

Probability of a subset of Bernoulli's being all 1's

Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
Marco's user avatar
  • 408
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
2 answers
256 views

Model for random graphs where clique number remains bounded

In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?
Nicolas Boerger'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
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
7 votes
1 answer
257 views

Collecting proofs of the birth of the giant component

I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$. I know the original proof of Erdös-Rényi, the proof that ...
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
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
6 votes
0 answers
105 views

Long loops in critical random graphs

A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by $$ \mathbb{E} X_k=\frac1{2k}{e^...
Johannes Kleinholz's user avatar
21 votes
2 answers
548 views

Do these polynomials have alternating coefficients?

In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence $$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$ Thus: ...
François G. Dorais's user avatar
2 votes
0 answers
93 views

Erdös-Renyi Model with prescribed subgraph

In the Erdös-Rényi model for random graphs there is a lot of results stating sharp phase transitions for the probability of a random graph to contain a fixed prescribed ...
Nicolas Boerger's user avatar
8 votes
0 answers
240 views

Stepanov phase transition in random graph

Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi. At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
Olivier's user avatar
  • 468
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
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 ...
Pavan Sangha's user avatar
1 vote
2 answers
2k views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
Pavan Sangha's user avatar
1 vote
1 answer
638 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
Pavan Sangha's user avatar
1 vote
2 answers
2k views

Proving a random bipartite graph contains a perfect matching

I have the following problem consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...
Pavan Sangha's user avatar
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 ...
Pavan Sangha's user avatar
1 vote
1 answer
353 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
murv's user avatar
  • 75
4 votes
0 answers
220 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. Assumptions about the graph: You may ...
real's user avatar
  • 323
1 vote
1 answer
420 views

Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
Olivier's user avatar
  • 468
7 votes
4 answers
1k views

Recent impressive combinatorial developments in probability theory

In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv) ... I suspect that, for at least a decade, the most ...
an12's user avatar
  • 1,302
13 votes
2 answers
383 views

Comparing two measures on trees on $n$ vertices

A standard measure on trees on $n$ vertices is the Uniform Spanning Tree (UST) on the complete graph. This is the measure where every tree has equal probability, $1 / n^{n-2}$ by Cayley's formula. ...
Matthew Kahle's user avatar
7 votes
2 answers
417 views

Dynamics of a random "quadratic" directed graph

Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" ...
JSE's user avatar
  • 19.2k
57 votes
4 answers
15k views

Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
Matthew Kahle's user avatar
5 votes
1 answer
1k views

Self Avoiding Walk Enumerations

Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
Alex R.'s user avatar
  • 4,952
9 votes
1 answer
1k views

Vertex connectivity of random graphs?

Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
Justin Melvin's user avatar