All Questions
Tagged with random-graphs graph-theory
211 questions
0
votes
0
answers
55
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
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 ...
- 143
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 349
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 ...
- 1,190
1
vote
0
answers
89
views
Gamma and Poisson distributions and their relations to the randomness
I'm reading the following paper:
https://academic.oup.com/bioinformatics/article/32/1/122/1743683
and in Figure 3 (Section 4.4) the authors have shown some vertex degree distributions:
enter image ...
5
votes
1
answer
386
views
Are directed graphs with out-degree exactly 2 strongly connected with probability 1?
Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not ...
- 6,969
2
votes
1
answer
80
views
Positive-semidefiniteness of Laplacian of signed graph
Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$.
my question.
If $\...
- 405
0
votes
0
answers
52
views
Does "epsilon-regular" equal to "cut distance less than epsilon"?
Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?
$G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
- 349
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_\...
- 6,353
1
vote
0
answers
98
views
Szemeredi Regularity Lemma - Reasonable Bounds
Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
- 5,407
1
vote
0
answers
164
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.8k
3
votes
0
answers
151
views
Smallest dominating set
Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
- 3,499
1
vote
0
answers
91
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 11
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 $...
- 1,190
4
votes
1
answer
211
views
Erdős–Rényi random graphs — reproducing 2 inequalities
In Erdős and Renyi's 1959 paper On random graphs I
, I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}.
Eq.\eqref{1} is:
$$
P \le \...
- 43
1
vote
0
answers
100
views
Benjamini-Schramm convergence: convergence on metric balls implies weak convergence?
In the famous paper by Benjamini-Schramm 2001, they consider the space of rooted graphs with uniformly bounded degrees, this space modulo rooted graph isomorphism is denoted by $\mathcal X$.
This ...
- 502
2
votes
0
answers
91
views
Graphon convergence of uniform weighted graphs
I have a question that I need at some point my research. Suppose that the upper-triangular entries of an $n\times n$ symmetric matrix $A$ are i.i.d. Uniform$(0,1)$. Does the weighted graph with ...
- 241
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 ...
- 1,407
1
vote
1
answer
128
views
Random graph uniformly sample from the special graphs
We know two basic random graph models:$G(n,p)$ and $G(n,m)$. $G(n,m)$ consists of all graphs with $n$ vertices and $m$ edges, in which the graphs have the same probability. We know that $G(n,p)$ and $...
- 91
5
votes
1
answer
319
views
Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$
Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$?
...
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 ...
- 41
3
votes
0
answers
59
views
Minimum induced subtree cover number of a graph
For an arbitrary simple finite graph $G$, without multiple edges between any two nodes and without any loop, the minimum induced subtree cover number, which is denoted by $stc(G)$, is defined to be ...
- 4,784
8
votes
1
answer
392
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
- 3,499
1
vote
1
answer
543
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 ...
- 21
1
vote
0
answers
115
views
Probability of (single) connecting paths in Erdos-Renyi graphs
In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of
there ...
- 129
4
votes
1
answer
216
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 ...
- 1,561
6
votes
1
answer
257
views
Expected doubling constant of a random Erdős–Rényi graph
Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
- 5,407
2
votes
1
answer
96
views
Lower bound on the number of balanced graphs
Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...
- 143
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 ...
- 7,525
6
votes
2
answers
717
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 ...
- 557
8
votes
2
answers
394
views
Selection of an n-vertex graph at random
Let's say I want to select, at random, an $n$-vertex graph $G=(V,E)$ from the set of all $n$-vertex graphs.
One way to do this would be to take the empty graph on $n$ vertices and then add each ...
- 151
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$ ...
- 3,446
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 ...
- 3,446
1
vote
0
answers
64
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 ...
- 640
5
votes
3
answers
836
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.
...
- 1,444
3
votes
1
answer
163
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 ...
- 805
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 ...
- 153
0
votes
0
answers
178
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)] \...
4
votes
0
answers
351
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 ...
- 439
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 ...
- 3,209
3
votes
0
answers
147
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 "...
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 ...
2
votes
1
answer
211
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) \...
- 640
1
vote
0
answers
72
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 ...
- 9,720
4
votes
1
answer
566
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 ...
user130903
2
votes
3
answers
230
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 ...
- 9,720
1
vote
0
answers
40
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 ...
- 11
4
votes
3
answers
430
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 ...
- 9,720
-1
votes
2
answers
419
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 ...
- 1
2
votes
0
answers
281
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 ...
- 1,216