3
votes
1answer
68 views

Independent Sets in random geometric graphs

I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...
2
votes
0answers
33 views

Hamiltonicity of random graphs with high girth

We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll ...
3
votes
0answers
84 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
0
votes
2answers
80 views

different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...
4
votes
1answer
111 views

Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value? I'm specially interested in what happens for small values of p, ...
1
vote
0answers
47 views

Simulation of disassortative random graphs

Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in ...
3
votes
0answers
161 views

Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
5
votes
6answers
409 views

Random planar, bipartite graphs

I have a need to generate random planar graphs none of which have an odd cycle, i.e., bipartite graphs. I know there is a substantial two-decade literature on random planar graphs, little with which I ...
3
votes
1answer
221 views

Expected Value for a Connected Graph

Consider a connected graph of N nodes. Assign randomly to each node a distinct number from 1 to N. For each node consider the maximum adjacent value or itself if all adjacent values are smaller. ...
3
votes
3answers
353 views

random networks and prime numbers

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that $\pi(n)\sim n/log(n)$ for ...
4
votes
3answers
164 views

Tracking automorphism groups of graph processes

Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...
0
votes
0answers
57 views

Maximum Independent set of sparse graphs with few triangles

Notations used $\alpha(G) = $ Max sized independent set of graph $G$. $n(G) = $ Number of vertex in graph $G$. Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being ...
0
votes
0answers
95 views

Adjacent matrix of undirected graph with a giant component

Assuming there is a undirected random graph $G=(V,E)$, $|V|=N$ and its adjacent matirx is $A$. What is the sufficient and necessary conditions of A for that there is a giant component of graph $G$? ...
3
votes
0answers
117 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$, ...
1
vote
1answer
432 views

Probability of two vertices being connected in a random graph

Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...
-3
votes
1answer
166 views

adjacency matrix of random geometric graphs [closed]

Consider a graph with N nodes. All nodes are distributed as a Poisson point process with density of λ in a L*L area. There is an edge between two nodes if and only if the distance between them is less ...
2
votes
0answers
88 views

Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...
2
votes
2answers
236 views

Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?

As far as I understand my literature, the probability of a random graph being fully connected tends toward one as the number of edges approaches a value of size $O(n \log(n))$ The way I read this, ...
1
vote
0answers
60 views

Can this application of the moment closure method to epidemics on networks be made rigorous?

Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ ...
2
votes
1answer
242 views

Removing edges from Erdős–Rényi graph to make two nodes disconnected

Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says "There ...
4
votes
1answer
501 views

How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one. But what is known about the ...
5
votes
1answer
172 views

The structure of small components in random graphs with a given degree sequence

Background and definitions Consider a random graph on $n$ vertices with a nicely behaved degree sequence. That is, letting $d_i(n)$ denote the number of vertices of degree $i$, suppose that for all ...
3
votes
0answers
65 views

Is there precedent in the literature for a variant of a random geometric graph where vertices are the centroids of discs placed by random sequential adsorption (RSA)?

Imagine I form a random graph by simulating random sequential adsorption (RSA) of discs (each with the same radius $r$) on $[0,1]^2$ until I cover the plane at a density $\leq U$, where $U \leq ...
0
votes
1answer
100 views

Is there a proper way to define a threshold vertex density for a random graph s.t. the graph is fully connected?

Imagine one generates some form of random graph (e.g. a random geometric graph) and via simulation, calculates the probability that there exists an edge-wise path between all vertices in the graph as ...
2
votes
2answers
250 views

The probability distribution for vertex degree in a unit disc graph generated from random points on a plane

Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx ...
0
votes
1answer
238 views

Two different definitions of Erdos-Rényi random graph

There are two or more ways to define an Erdos-Rényi random graph. Let consider the following two: 1) $G_n=(V_n,E_n)$ with vertex set $V_n=(1,\dots,n)$ and edge set $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ ...
0
votes
0answers
184 views

counting k-cliques not also (k+1) on random graphs

consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges. looking for a formula that counts the number of these graphs that have a $k$-clique but not a ...
3
votes
1answer
324 views

How random are random spanning trees?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ...
0
votes
1answer
122 views

Generating spatially-aware degree-preserving random graphs?

In the study of biological neural networks, researchers sometimes compare hypotheses vs. a degree-preserving random null model. One major criticism against this approach is that connections in neural ...
4
votes
1answer
244 views

Cut-distance between two Erdos-Renyi random graphs

Consider two Erdos-Renyi random graphs $G_1,G_2$ on $n$ nodes, with the edges in each graph generated independently at random with probability $1/2$. My question is about the cut-distance between ...
4
votes
0answers
210 views

Expected number of components with multiple cycles in a subgraph of a square lattice

Short version Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the ...
0
votes
0answers
136 views

Graph theory meta-question

If property (P) holds for perfect graphs and almost all graphs does it hold for all graphs?
2
votes
1answer
161 views

matchings in hypergraphs

I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform ...
6
votes
1answer
339 views

How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?

Let $E(n,t)$ be the number of mathematicians with finite positive Erdős number $n$ at time $t$. As old mathematicians leave, and new mathematicians come, how does $E(n,t)$ change over time ? We can ...
8
votes
1answer
595 views

Correlation-Function for Random Graph Ising Model

For non-Ising'ers: Given a graph, we study the probability-distribution on the set of colorings ("Spin-up" and "-down") generated by a given correlation ("force to equality") between adjacient nodes ...
3
votes
2answers
243 views

Question on Sparse Random Graphs

I saw stated in a paper the following result but without a reference or a proof. Let $G$ be an Erdos-Renyi random graph with $n$ nodes and probability of connection $c/n$ with $c>1$. Let $H$ be ...
1
vote
1answer
241 views

Connectivity of a graph with fixed number of vertices and edges

Hi, first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge. So this is the ...
5
votes
1answer
284 views

A more efficient way to generate random graphs with a given degree sequence?

In graph data mining it is often useful to generate random (simple) graphs with a given degree sequence (e.g. in searching for network motifs), and ideally these would be uniformly at random. [For ...
3
votes
2answers
295 views

Can you randomly sample graphs with quadratic growth?

Let $\mathcal{G}$ be the set of all infinite connected graphs with the following properties: Every vertex has $4$ neighbors For every vertex, there are $8$ vertices that have distance exactly $2$ ...
6
votes
3answers
1k views

Random bipartite graphs

Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I ...
7
votes
2answers
898 views

Probability of Generating a Connected Graph

$N$ points are generated randomly within a unit square, with a uniform distribution. What is the probability that the points form a connected graph, given that two points are connected if the distance ...
0
votes
1answer
263 views

How many graphs with given average degree and average number of outgoing nodes?

Hi, does anyone know if it is known what is the number of undirected graphs with the following properties: Number of nodes: $N$, a big number, Average degree: $z_1$, Average number of outgoing ...
8
votes
1answer
441 views

Change in the average geodesic distance of a graph when flipping a single edge

Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra ...
6
votes
4answers
238 views

Finite graphs that realize all types over $n$-element sets

Call a graph $G$ $n$-saturated if for every set $A$ of size $n$ of vertices and all $B\subseteq A$ there is a vertex $v\not\in A$ that forms an edge with all $w\in B$ and does not form an edge with ...
1
vote
1answer
183 views

PR[$\lambda_2 > x$] in $G_{np}$ model

Hi! Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than $x$ to the parameter $p$ in the $G_{np}$ model?
9
votes
2answers
709 views

Properties of Some Random Graphs

Working in a problem the following family of graphs appears naturally. Consider the set $A_{n}=\{1,2,3,\ldots,n\}$ and let $\mathcal{C_{n}}$ be the set of all permutations of $A_{n}$ of order $n$ ...
4
votes
2answers
921 views

Probability, that a graph G does not contain a cycle

Hello, given graph $G=(V,E)$ with $n=|V|$ and $k=|E|$, what is the probability that it does not contain any cycle $C_l$ for $l\geq3?$ The requested clarification: My intention was to form the ...
7
votes
4answers
1k views

“sparse graphs are locally tree-like”

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
1
vote
2answers
873 views

Max cut value in a random graph

Let $G = G(n, 1/2)$ be an Erdos-Renyi graph in which each edge $e = (u,v)$ is present in the graph independently with probability $1/2$. For a subset of the vertices $S$, the cut value $c(S)$ is equal ...
11
votes
3answers
602 views

Rainbow matchings (in random graphs)

Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) ...