150 votes
Accepted
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known ...
- 6,977
45 votes
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community, an asymptotic variant of ...
- 6,636
30 votes
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
@user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished: If I understand your comment to my ...
- 6,977
14 votes
What nodes of a graph should be vaccinated first?
Not a complete answer, but I don’t yet have enough reputation to comment: one way to measure the “importance” of a vertex w.r.t. it’s degree and the degrees of its neighbors goes by the name of shell ...
- 150
13 votes
Accepted
Graphs resembling the math genealogy graph must have concentration in a small number of families?
Precisely this question was the starting point of the Galton - Watson theory of branching processes. To quote the opening paragraph of their 1875 paper On the Probability of the Extinction of Families:...
- 17.6k
13 votes
Accepted
How random are Fraïssé limits really?
As Emil says, Fraïssé limits in general should not be thought of as random, but as generic. Kabluchko and Tent give a nice explanation of how they are generic. To summarize: Given a finite relational ...
- 2,196
12 votes
Do these polynomials have alternating coefficients?
To illustrate the suggestion of Richard Stanley about positivity of real parts of zeroes, here are the zeroes of $Q_{20}$. The pattern seems to be the same for all of them. Another empirical ...
12 votes
Accepted
What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?
Consider subgraphs consisting of two cycles with an edge in common (i.e. a theta-graph or something more complex). The number of such labelled graphs with $t$ vertices is at most $n^t$, and the ...
- 38.3k
11 votes
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
One reference is Chapter 5 of Random Graphs by Janson, Łuczak, and Ruciński. Their proof uses the theory of Galton–Watson branching processes, so it is not quite the same argument that ...
- 88.1k
11 votes
Accepted
What is the theory of the random poset?
It is confusing to call this the “random poset”, as it is very different from what is usually called random posets in the literature (in accordance with random graphs): e.g., random posets have height ...
- 50.6k
10 votes
Accepted
Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?
I can answer question 1, at least. The mean of $f$ is always positive (unless every connected component of the graph $G$ is regular, in which case the mean of $f$ is zero). To see this, we rewrite the ...
- 9,040
9 votes
Selection of an n-vertex graph at random
There is a very efficient method. See Nicholas C. Wormald Generating Random Unlabelled Graphs
- 38.3k
9 votes
Threshold function for a graph not being planar
In the Erdős–Rényi model, the threshold for the planarity is know to be $t(n) = 1/n$. Perhaps one of the easiest ways to see this is the following. If $p=o(1/n)$, then a straightforward union bound ...
- 1,209
8 votes
Accepted
What is the Essential Difference Between Random Matrices and Random Graphs?
I suppose the main point is that the typically studied random graph models are not directed or weighted and they generally don't have self loops. Under your correspondence, this means they are ...
- 30.1k
8 votes
Threshold function for a graph not being planar
Consider the model where a random graph is made by adding one edge at a time chosen uniformly at random from edges not yet present. Łuczak, Pittel and Wierman (1994) showed that there is a function $f(...
- 38.3k
8 votes
Accepted
Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$
It certainly tends to $0$. The way to see it almost without any computation is to mark any $n$ disjoint edges. Then, when deciding the fate of the remaining edges, each vertex has $p=2^{2-2n}{2n-2\...
- 63.9k
8 votes
Accepted
Are directed graphs with out-degree exactly 2 strongly connected with probability 1?
No. The probability that a given vertex doesn't have any incoming edge is $(1-\frac1n)^{2n}\to e^{-2}$, so the graph will not be strongly connected with probability at least $e^{-2}$ (asymptotically). ...
- 3,403
7 votes
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
One can also deduce the $G(n,p)$ result from the $G(n,m)$ result: one way to generate $G(n,p)$ is to choose $m$ from the binomial distribution with $\binom{n}{2}$ trials and probability $p$, then ...
- 1,697
7 votes
Open Problems in Random Graphs
Check out the Open Problem Garden, which lists this problem: Due to MO user @BorisBukh.
- 153k
7 votes
What nodes of a graph should be vaccinated first?
I took a look at a very simple model: SIR for 2 population groups with the interaction matrix $A=\begin{bmatrix}\alpha & \lambda\\\mu & \beta\end{bmatrix}$, which, roughly speaking, ...
- 63.9k
7 votes
Accepted
Does the random graph interpret the random directed graph?
No, the random graph cannot interpret the random binary relation. I’ll just answer the title question with the goal of illustrating a technique; I haven't considered $k$-ary structures. The approach ...
- 1,926
7 votes
Accepted
(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$
Let me answer the first question: Q: Does $F=\sum_{i=0}^{\infty} A^i (A^i)^{\top}$ for non-symmetric $A$ have a closed-form solution analogous to the solution $\sum_{i=0}^{\infty} A^{2i}=\left( I-A^2 \...
- 201k
7 votes
Accepted
Discrepancy of random bipartite graphs
The expected degree of a vertex is $k$, which we are keeping fixed as $n\to\infty$. As $n\to\infty$, the vertex degree distribution converges to Poisson($k$). In particular, a proportion roughly $e^{-...
- 3,977
6 votes
Accepted
Conditional probability that a random spanning tree contains the edge e
There is no constant upper bound, as shown by the following example. Take two vertices $v, u$ and connect them with $n \geq 2$ edge-disjoint paths of two edges. This graph has $n 2^{n - 1}$ spanning ...
- 5,752
6 votes
Accepted
Citations graphs: what is known?
A great deal is known about citation graphs. For example, an analysis of the citation graph for the computer science literature answers the three questions in the OP as: • the connected component has ...
- 201k
5 votes
Uniform sampling of random connected graph with given number of vertices/edges
I don't know if this has been programmed. I'll describe one method based on counting. Let $c_{n,m}$ be the number of labelled connected graphs with $n$ vertices and $m$ edges. Choose a pair of ...
- 38.3k
5 votes
Accepted
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
The most satisfying solution I've seen so far are these notes by Sabastian Roch (see section 2.2.3, and in particular claim 2.25). He first argues that the only components besides the giant one are ...
- 470
5 votes
Accepted
Probability of a subset of Bernoulli's being all 1's
For the concrete question, it’s equivalent to asking for the cdf of the binomial distribution. This is well known. In general, this is a very hard problem. Janson’s Inequality is not a second moment ...
- 1,697
5 votes
Accepted
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
The answer to this question is No. Let us assume $V = \{1,2,3,4,5,6\}$ and consider degree sequences $a = [3,2,2,1,0,0]$, $b = [1,0,0,3,2,2]$ and $c = a+b = [4,2,2,4,2,2]$. The only simple graph with ...
- 1,534
Only top scored, non community-wiki answers of a minimum length are eligible