Questions tagged [random-graphs]

The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.

Filter by
Sorted by
Tagged with
10 votes
1 answer
360 views

(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$

Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
user avatar
1 vote
2 answers
80 views

Which infinite random graphs with percolation threshold $p_c=0$ are transient?

I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...
user avatar
1 vote
1 answer
89 views

Hammersley-Clifford theorem

The paper spatial interaction and the statistical analysis of lattice systems by Besag (1974) presents an alternative proof for the Hammersley-Clifford theorem. In order to prove the HM theorem, Besag ...
user avatar
1 vote
0 answers
43 views

Angles between edges of a geometric graph and graph invariants

Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph? I'm interested to see what else is ...
user avatar
  • 466
5 votes
3 answers
187 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. ...
user avatar
1 vote
1 answer
90 views

The most pseudorandom subgraph of a dense graph

A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy ...
user avatar
  • 725
0 votes
0 answers
32 views

Asymptotic probability of a short path in the LEAF problem

When reading about total NP search problems (specifically their oracle versions) I started analysing the computational problem $\text{LEAF}$: An instance $(G,v_0)$ is given by an undirected graph $G$, ...
user avatar
  • 173
2 votes
1 answer
119 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 ...
user avatar
2 votes
1 answer
59 views

Are the eigenvalues of the 1D lattice with random weights known?

Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...
user avatar
  • 139
1 vote
1 answer
105 views

how to compute the probability that a random graph has two components? [closed]

This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph: A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs....
user avatar
  • 113
0 votes
0 answers
108 views

Expected chromatic number of random subgraph

Let $G$ be a fixed graph and let $G_p$ be a random subgraph of $G$ where every edge is kept independently with probability $p$. According to [1] and [2] the paper [3] proves $$ \mathbb{E}[\chi(G_p)] \...
user avatar
1 vote
0 answers
14 views

Is homomorphism density of partially labeled graph continuous with respect to cut metric

Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
user avatar
1 vote
0 answers
45 views

Canonical representation of the a probability distribution for Hammersley Clifford Theorem

I'm reading the following paper http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/GibbsFieldEst/BesagJRSSB1974.pdf On page 7 they give the result that $$Q(\textbf{x}) = \sum_{1 \leq i \leq n} ...
user avatar
4 votes
0 answers
224 views

Research on graph theory

I am interested in graph theory. My background is mainly algebraic. I have been researching algebraic geometry for five years so I assume that the transition to the graph theory realm shouldn't be so ...
user avatar
1 vote
1 answer
70 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$, ...
user avatar
  • 433
6 votes
1 answer
413 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 ...
user avatar
  • 3,084
1 vote
0 answers
73 views

Longest close common subsequence but for continuous random variables

We have two copied sequences of correlated continuous positive random variables that are independent of each other $(X_{n})\perp(Y_{n})$ and equal in distribution $X_{n}\stackrel{dis}{=}Y_{n}$ for ...
user avatar
  • 1,378
3 votes
0 answers
73 views

Random graph - probability threshold for any linear size set to contain a fixed clique

Let $t\geq 3$ and $0<\varepsilon<1$ be fixed. Denote by $K_t$ the clique on $t$ vertices, and by $G_{n,p}$ the binomial random graph. Question: Is the threshold for the probability that "...
user avatar
1 vote
0 answers
78 views

In percolation on a lattice, how is "infected" status correlated for points in a region around the origin?

Consider independent bond percolation on $\mathbb{Z}^2$, with $p>p_c$ so that the process is supercritical. For any site $x$ let $Y_x$ be the indicator of $x$ belonging to the infinite open cluster....
user avatar
  • 1,058
0 votes
0 answers
62 views

Contiguity of uniform random regular graphs and uniform random regular graphs which have a perfect matching

Let us consider $\cal{G}_{_{n,d}}$ as the uniform probability space of d-regular graphs on the n vertices $\{1, \ldots, n \}$ (where $dn$ is even). We say that an event $H_{_{n}}$ occurs a.a.s. (...
user avatar
1 vote
0 answers
63 views

Understanding the finale of the proof of Komlós' and Szemerédi's limit distribution of Hamiltonian random graphs

My question is about the end of the proof of Theorem 1 in [Komlós, Szemerédi (1983)], more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my ...
user avatar
1 vote
1 answer
117 views

Bound on $i$th largest eigenvalue in a large Erdos-Renyi graphs

Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice ...
user avatar
4 votes
0 answers
168 views

Spectral norm bound on adjacency matrix from an Erdos-Renyi graph

Let $G(n,p)$ be an Erdos-Renyi graph, where $p \sim \log^k(n) /n$ for small fixed integer $k$. If $A$ is the adjacency matrix, then I am looking for a sharp upper bound on $\|A-\mathbb{E}[A]\|$ that ...
user avatar
  • 3,077
1 vote
1 answer
64 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 ...
user avatar
2 votes
1 answer
116 views

The complexity of expansion ratio (Cheeger constant) of a graph

Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...
user avatar
1 vote
0 answers
54 views

Another betweenness centrality measure: neighbourhood centrality

Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind). Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
user avatar
2 votes
0 answers
46 views

Cycle statistics of random endomorphism

Let $S$ be a set with $n$ elements and let $f:S\to S$ be a random function, chosen uniformly among the $n^n$ possibilities. Considering $f$ as a directed graph of constant outdegree $1$, i. e. with ...
user avatar
  • 2,877
2 votes
1 answer
137 views

Probabilistic bound to the number of edge disjoint triangles in a random graph

Let $G$ be a random graph with $n$ vertices, and let $\delta(G)$ be the maximum number of triangles in $G$. Question. How to prove the bound $$P(\delta(G)) \leq m - t \sqrt{f(m)}) \leq 2e^{-t^2 / 4}$...
user avatar
8 votes
1 answer
678 views

What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...
user avatar
3 votes
1 answer
214 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
2 votes
3 answers
187 views

Random graphs defined by a set of tiles

Related to this question, which I asked at MSE, I'd like to ask this one here: Consider a (large) graph $G$ and its multi-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the ...
user avatar
1 vote
0 answers
34 views

Eigenvalue bounds of a random graph with a clique

I'm looking into this paper and having some problems proving (ii) of proposition 2.1. I don't quite understand how the lemma is proved. I also read the original paper where the lemma comes from but ...
user avatar
4 votes
3 answers
343 views

How to show that random graphs cannot be embedded with short edges

For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio $$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
user avatar
0 votes
2 answers
167 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 ...
user avatar
3 votes
0 answers
60 views

Random graphs with prescibed degrees and triangles

In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
user avatar
2 votes
0 answers
128 views

Generating a random graph with bounds on degree and diameter

What would be a way to generate a random simple graph with diameter lesser than a given number, and in which there are given lower and upper bounds (bounds being uniform across vertices) on the degree ...
user avatar
  • 1,126
2 votes
0 answers
57 views

Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
user avatar
8 votes
1 answer
241 views

Does the random graph interpret the random directed graph?

The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary ...
user avatar
4 votes
3 answers
323 views

Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
user avatar
23 votes
4 answers
897 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 ...
user avatar
2 votes
1 answer
294 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 ...
user avatar
9 votes
1 answer
219 views

Is there a good algebraic model of random n-hypergraphs?

Suppose $F$ is a finite field and $-1$ is a square in $F$. Let $E$ be the binary relation on $F$ where $(a,b) \in E$ iff $a - b$ is a square. Then $(F,E)$ is called a Paley graph. Paley graphs are ...
user avatar
5 votes
2 answers
233 views

Triangle coloring in random graph

Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...
user avatar
  • 491
0 votes
1 answer
95 views

Sources of information on algorithms for finding Hamiltonian cycles (Pósa)

I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...
user avatar
  • 1
5 votes
0 answers
136 views

Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here. I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
user avatar
2 votes
0 answers
118 views

Expansion of random subgraphs of a bi-regular bipartite graph

Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree. We know $G$ is a good spectral expander. ...
user avatar
  • 205
3 votes
1 answer
111 views

making a random uniform hypergraph linear

Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{...
user avatar
4 votes
1 answer
211 views

Structures for random graphs with structure

Background[You may skip this and go immediately to the Definitions.] Crucial features of a (random) graph or network are: the degree distribution $p(d)$ (exponential, Poisson, or power law) the mean ...
user avatar
3 votes
1 answer
85 views

Hyper-degree sequences: How to count them and how to construct hyper-graphs from them?

From an answer to this question I have learned how to ask this question properly. Consider a $k$-uniform hypergraph on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges)...
user avatar
3 votes
0 answers
142 views

Two kinds of generating functions

Sorry for a possibly off-the-topic question, but I am afraid to gain the necessary overview to give an answer (supposed the question is not ill-posed) is beyond my capabilities. In the course of ...
user avatar

1
2 3 4 5 6