Questions tagged [random-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
81 views

Spectral sparsification of graphs with negative edge weights

I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question. It is ...
K V's user avatar
  • 1
6 votes
5 answers
457 views

Relationship between Random Graph Theory and TCS

Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to ...
MikeG's user avatar
  • 113
1 vote
0 answers
77 views

Prune length distribution of random binary tree

Consider a random binary tree with $N$ leaves. Each node (except the root node) has a degree of exactly three (two children and one parent). No further restriction is placed on the structure of the ...
user152789811's user avatar
3 votes
0 answers
261 views

Power law for degree distribution of random KNN graphs?

Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d" and consider a KNN (K-nearest neigbour) graph for some K. Look at the degree ...
Alexander Chervov's user avatar
10 votes
3 answers
1k views

Number of connected components of a random nearest neighbor graph?

Let us sample some big number N points randomly uniformly on $[0,1]^d$. Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph). Question What would the ...
Alexander Chervov's user avatar
9 votes
2 answers
343 views

How long does it take to find a short cycle in a random graph?

Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
GMB's user avatar
  • 2,403
10 votes
0 answers
173 views

Diameter of "almost" always connected Erdős-Renyi graphs

Let $G=(V,E)$ be a random Erdős-Renyi Graph, i.e., $G\in\mathcal{G}(n,p)$. It is well known that if $p=(\log n +c +o(1))/n$ with $c\in\Re$ then $$ P(G \text{ is connected})=e^{-e^{-c}}\ . $$ However, ...
Lamine's user avatar
  • 1,138
4 votes
1 answer
184 views

Probability of a $k$-path in a random graph

Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$, the following fact is well known: \begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\...
R B's user avatar
  • 9,448
2 votes
0 answers
123 views

Random Multigraph ER-like model?

I was looking into multigraphs recently and I couldn't find a simple "goto" model for generating random multigraphs along the lines of the ER model of simple graphs. Specifically, I was hoping to find ...
Konstantinos Koiliaris's user avatar
0 votes
0 answers
62 views

Expected size of the min-cut, under edge perturbations

Suppose we have a graph $G(V, E)$. Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$. Create a random modification of the graph: Drop each ...
Daniel's user avatar
  • 749
5 votes
1 answer
367 views

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

Peter Shor commented on this post: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar. What can we say ...
0x90's user avatar
  • 463
7 votes
2 answers
386 views

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such ...
mm8511's user avatar
  • 203
7 votes
1 answer
561 views

Connectivity of a random regular graph of degree $d$

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be ...
Vivek Bagaria's user avatar
2 votes
0 answers
331 views

expected number of edges for fixed min cut

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges. Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
user1798883's user avatar
8 votes
1 answer
1k views

Probability of two vertices being connected by some path in a random directed graph

Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$). What are the known results for the following problem: Fix two vertices $v$ and $u$...
Daniel's user avatar
  • 749
23 votes
2 answers
698 views

Which graph parameters are NOT concentrated on random graphs?

It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, ...
Andras Farago's user avatar
3 votes
0 answers
114 views

How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?

Let $G=(V,E)$ be an undirected, random $r$-regular graph. Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$. I'm looking for the distribution of the number of ...
R B's user avatar
  • 9,448
4 votes
1 answer
248 views

Expected length of longest construction path in Barabási–Albert Model

The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by ...
Dave Clarke's user avatar
  • 16.7k
4 votes
0 answers
466 views

The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
Dimitris's user avatar
  • 1,356
5 votes
1 answer
182 views

What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what'...
winston's user avatar
  • 51
18 votes
2 answers
505 views

Separating words with random DFAs

One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any ...
Geoffrey Irving's user avatar
7 votes
3 answers
200 views

Independent Node Degree in Undirected Graphs

Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in ...
Volker Turau's user avatar
23 votes
1 answer
537 views

How big is the variance of the treewidth of a random graph in G(n,p)?

I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$ and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(...
Kostas's user avatar
  • 331
9 votes
0 answers
507 views

Statistical relationship between diameter and density in strongly connected random digraphs

I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
Alex Repain's user avatar