16

Take the following graph: start with the complete graph $K_5$, and replace every edge by $n/10$ paths of length $2$. The resulting graph has $n+5$ vertices, $2n$ edges, and crossing number $n^2/100$.
For random graphs with expected number of edges $e>10n$, Pach and Tóth showed that their crossing number is at least $e^2/4000$ almost surely.
Edit: In ...

15

I'm going to show that, for any $x>2^{-d}$, this is $O(x^{n})$. By Ricardo's lower bound, this is tight.
Given a set of $n$ points of diameter at most $1$, take all the points you get from those points by rounding the coordinates up or down to multiples of $\epsilon$. This new set of points will contain the old set of points in its convex hull, and since ...

12

In this recent paper of Erdos, Knowles, Yau, and Yin, it is shown that in the bulk of the spectrum, the spacing between eigenvalues of an Erdos-Renyi graph on $n$ vertices obeys GOE statistics asymptotically. This implies that most of the eigenvalues are simple (i.e. $n-o(n)$ of the $n$ eigenvalues are simple) asymptotically almost surely, so that the ...

answered Apr 22 '13 at 14:49

Terry Tao

72.8k2020 gold badges283283 silver badges369369 bronze badges

12

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 observation: seems that
$$
\frac{Q_n(1-x)}{(1-x)^{n-2}(1+x)}=1+(n-3)x+\left(\binom{n-2}2+1\right)x^2
+\left(\binom{n-1}3+n-3\right)x^3+\left(\binom n4+\binom{n-2}2+1\...

12

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 probability of each is at most $(d/n)^{t+1}$ since they have at least $t+1$ edges. Summing over $t$ shows that the expected number of such subgraphs goes to 0 for $d\...

11

I am certainly not the best person to answer this question, as I do not have much insight to share regarding how to approach this kind of problems. My only (fairly obvious) suggestion is to estimate the relevant quantities in any way possible. In this process, it can be very helpful to reduce the calculations to lower dimensions, and the Fubini theorem will ...

answered Jun 15 '13 at 10:50

Ricardo Andrade

5,91855 gold badges3636 silver badges6767 bronze badges

11

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 Erdős and Rényi gave, but one nice thing about Janson et al. is that they discuss both graph models.

answered Oct 3 '18 at 0:44

Timothy Chow

48.4k1515 gold badges215215 silver badges381381 bronze badges

10

Here's one. You can think of the graph construction process as gradually building a set $S$ of vertices that have been touched so far, beginning with a random two vertices. Let $S_k$ be the set of the first $k$ vertices in this process.
Now $p(n)$ is exactly the probability that, after the first two vertices, each additional edge we select either has both ...

10

I have no idea where the figure $n^{0.02}$ comes from. I would usually say it's well known that the maximum degree is $O(\log n)$ (actually even this is an overestimate). It's for example found in an Erd\H{o}s-R\'enyi paper with a title about random matrices, I think; or surely in any of the 'Random Graphs' books.
In any case, it is very easy to prove. One (...

10

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 sum of the values of $f$ as
$$\sum_{v \in V} f(v) = \sum_{v \in V} \sum_{w\text{ s.t. }\{v,w\} \in E} \left(\frac{\deg(w)}{\deg(v)} - 1\right) = \sum_{\{v,w\} ...

9

The complete bipartite graph $K_{3,n}$ has 3n edges and crossing number $cn^2$.

7

A whole body of results in probability with strong combinatorial flavour are around 2-dimensional stochastic models. Some of this progress started 15 years ago but much was achieved in the last decade. Much of this research has combinatorial flavour. This includes conformal invariance for planar percolation on the triangular grid; The stochastic Lowevner ...

answered Jul 30 '12 at 12:38

Gil Kalai

22.7k3232 gold badges195195 silver badges287287 bronze badges

7

Have a look at Chapter 11 of Alon and Spencer's The Probabilistic Method. They focus entirely on the case $p = \Theta(1/n)$, and the smallest p they consider is of the form $c/n$, which perhaps counts as "small p" as in your question. In 11.6, they study the smallest case $c < 1$ in detail (they refer to this case as Very Subcritical). The results are ...

7

(16) They split the sum in (13) for $M<s\leq \frac n 2$ and $\frac n 2 < s < n- \frac {2 N_c} n$. In the first case they use (14) and, since the terms are positive, they enlarge the sum to $M<s<\infty$. In the second range they use (15) to estimate the sum, then they substitute $s'=n-s$, and then they extend to $\frac {2N_c}n <s'<\infty$....

7

In this case, assuming $c\lt 1$ is independent of $n$, the number of cycles is asymptotically Poisson with constant mean $f(c)$. So asymptotically there is a constant nonzero probability $e^{-f(c)}$ that there are no cycles. With a rough calculation that needs checking, I got
$$ e^{-f(c)} = \sqrt{1-c}\,\exp\bigl({{\textstyle\frac14}c(2+c)}\bigr).$$
You can ...

7

To add to the preceding answer: The absolute values of the coefficients appear normal (in particular, unimodal): Which means that the technology developed, in, eg,
Lebowitz, J.L.; Pittel, B.; Ruelle, D.; Speer, E.R., Central limit theorems, Lee-Yang zeros, and graph-counting polynomials, J. Comb. Theory, Ser. A 141, 147-183 (2016). ZBL1334.05065.
May be ...

7

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 generate $G(n,m)$. Since the standard deviation of $m$ (in the range of $p$ you care about) is around $\sqrt{n}$, and the threshold window for connectivity is much ...

7

Check out the Open Problem Garden,
which lists this problem:
Due to MO user @BorisBukh.

answered Jan 20 '19 at 1:59

Joseph O'Rourke

133k2222 gold badges269269 silver badges783783 bronze badges

6

Two quick remarks.
First, given a directed graph you can always forget about edge orientation (saying that an unoriented edge is open iff one of its orientations was open in the directed version), and by domination, if $p \leq c/N$ with $c<1/2$ the usual Erdös-Renyi results will tell you something: the largest strongly connected component will be at most ...

6

Let me try to talk you out of your current viewpoint.
I am interested in language translation also and am somewhat familiar with the existing techniques. The most popularly the n-gram algorithm - look at the n words behind and n words in front of a word to "determine its meaning". These fail catastrophically in trying to translate from a language such as ...

6

The simplest source of cospectral graphs is lists of strongly regular graphs, lots of which are easily available from Ted Spence's web page at http://www.maths.gla.ac.uk/~es/srgraphs.php.
Otherwise you can use Sage to generate small graphs (up to 10 or so vertices) and then filter out cospectral pairs or groups. I expect the built in Sage function for ...

6

A random tournament is strongly connected with probability tending to 1 exponentially fast, and all strongly connected tournaments have hamiltonian cycles.

6

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 trees. The number of spanning trees containing any fixed edge $e$ is $(n + 1)2^{n - 2}$. However, for any $v-u$ path $e, f$ the number of spanning trees ...

6

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 limited to symmetric matrices whose diagonal entries are zero and whose off-diagonal entries are either zero or one - a rather specific class of random matrices, and ...

answered Sep 9 '18 at 9:23

Paul Siegel

24.5k1313 gold badges101101 silver badges180180 bronze badges

5

(To answer Anthony, I'm taking the two graphs to be on the same vertex set.)
This is an argument, without details, that the answer is $\Omega(n^{3/2})$.
Generate the graphs two vertices at a time. As each pair of vertices is generated and their adjacencies with the previous vertices are chosen randomly, put one vertex on each side of the cut. Choose which ...

5

A quick proof sketch that the ratio goes to 0: Let $a$ and $b$ be points in the unit ball of distance 2. (The existence of such does not hold in an arbitrary metric space!) As we add more and more points to our set in an i.i.d. manner, we will with probability 1 eventually find points $x$ and $y$ with $d(x,a)< 1/2$ and $d(y,b)< 1/2$. Then $d(x,y)>1$...

answered Jun 16 '13 at 3:39

Bjørn Kjos-Hanssen

21.8k33 gold badges4343 silver badges9696 bronze badges

5

The random placement of points you described is called Poisson point process (in the limit). The resulting graph is called Random Geometric Graph. Searches will yield a good crop of papers about these graphs.
The degree distribution (again, in the limit) is Poisson with parameter equal to the expected number of points in a disc of radius 1.

answered Apr 6 '13 at 18:12

Ori Gurel-Gurevich

6,46111 gold badge2121 silver badges3636 bronze badges

5

First make a "random" quadrangulation, then take a random subgraph of that. Since every planar bipartite graph can be made into a quadrangulation by adding edges, at least you know that every outcome is possible (though perhaps far from equally probable).
To make a "random" quadrangulation, start with a square then repeatedly choose a path of length 2 (...

5

The crossing number of $C_3\times C_n$, the Cartesian product of the cycle $C_3$ and $C_n$, is given by $cr(C_3\times C_n)=n$ (see here), which satisfies your conditions: the number of vertices is $3n$ and the number of edges is $6n$.
In fact, it is conjectured that the crossing number of $C_m\times C_n$, the Cartesian product of the cycle $C_m$ and $C_n$,...

5

Actually, even the crossing number of the random 3-regular graph on $n$ vertices has crossing number $\Theta(n^2)$. This follows from the lower bound obtained by Bollobás for the isoperimetric number of random regular graphs (European Journal of Combinatorics, Vol. 9 (1988), pp. 241-244); the random $k$-regular graph (for any fixed $k$) thus has large ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

random-graphs × 238graph-theory × 148

pr.probability × 96

co.combinatorics × 67

reference-request × 23

random-matrices × 15

spectral-graph-theory × 13

stochastic-processes × 9

probability-distributions × 9

percolation × 9

mg.metric-geometry × 8

random-walks × 8

statistical-physics × 7

matrices × 5

extremal-graph-theory × 5

st.statistics × 4

bipartite-graphs × 4

nt.number-theory × 3

gr.group-theory × 3

linear-algebra × 3

lo.logic × 3

discrete-geometry × 3

markov-chains × 3

hypergraph × 3

trees × 3