I would like to know the asymptotic number of labelled disconnected (simple) graphs with n vertices and $\lfloor \frac 12{n\choose 2}\rfloor$ edges.
[Math] How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges
asymptoticsco.combinatoricsgraph theory
Related Solutions
Updated 4/17/11:
(Originally, this answer contained a different proof of the result below for $k=3$. Not only did the proof not generalize, but it was wrong.)
The maximum number of edges in a strongly-connected digraph with $n \geq k+1$ vertices and no cycles of length at most $k$ is $${\binom{n}{2}} - n(k-2) + \frac{(k+1)(k-2)}{2}.$$ (A digraph where every vertex is reachable from every other vertex by a directed path is called strongly connected.)
Gordon Royle conjectured this bound an gave an example achieving it for $k=3$. For general $k$ and $n$ the bound is attained by the following construction, almost identical to the one provided by Nathann Cohen in the comments:
Let vertices $x_1,x_2,\ldots,x_{n-k+2}$ form a transitive tournament with $x_i \to x_j$ being an edge for all $1 \leq i < j \leq n-k+2$. Now delete the edge $x_1 \to x_{n-k+2}$ and replace it with a path $x_{n-k+2} \to x_{n-k+3} \to \ldots \to x_n \to x_1$. (The vertices $x_{n-k+3},\ldots, x_n$ will have in-degree one and out-degree one in the resulting graph.)
It remains to prove that the above number is a valid upper bound. The proof is by induction on $n$.
Simple counting shows that the bound is valid if $G$ is a directed cycle. It is tight if $G$ is a cycle of length $k+1$. Assume now that $G$ is not a cycle. Then there exist $\emptyset \neq X \subsetneq V(G)$ such that $G|X$ is strongly connected. (For example, one can choose the vertex set of any induced cycle in $G$.) Choose $X$ maximal subject to the above. Let $u \to v_1$ be an edge of $G$ with $u \in X$, $v_1 \not \in X$, and let $P$ be a shortest path in $G$ from $v_1$ to $X$. Let $P=v_1 \to v_2 \to \ldots \to v_l \to w$.
Note that adding to $G|X$ any path starting and ending in $X$ produces a strongly connected digraph. It follows from the choice of $X$ that any non-trivial such path must include all the vertices in $V(G)-X$. In particular, if $l\geq 3$, $v_2,\ldots,v_{l-1}$ have no neighbors in $X$.
Let us further assume that $u$ and $w$ are chosen so that the directed path $Q$ from $w$ to $u$ in $G|X$ is as short as possible. (Perhaps, $w=u$.) Then $V(P) \cup V(Q)$ induces a cycle in $G$, and so $v_1$ and $v_l$ have at least $k-2$ non-neighbors on $V(P) \cup V(Q)$. At least $k-l$ of those non-neighbors are in $X$ if $l\geq 2$. Therefore there are at least $k-2$ non-edges (pairs of non-adjacent vertices) between $X$ and $V(G)-X$ if $l=1$, and at least $$2(k-l)+(l-2)(k+1) \geq l(k-2)$$ non-edges if $l \geq 2$. By the induction hypothesis there are at least $|X|(k-2)- \frac{(k+1)(k-2)}{2}$ non-edges between vertices of $X$, and therefore at least $$(l+|X|)(k-2)- \frac{(k+1)(k-2)}{2}=n(k-2) - \frac{(k+1)(k-2)}{2}$$ non-edges in total, as desired.
It seems that what Andrew wants to count are what are called in enumerative contexts "bicolored graphs". A bicolored graph is a graph in which the vertices have been colored black and white so that every edge joins two vertices of different colors. A bipartite (or bicolorable) graph is a graph that has a bicoloring. A bicolorable graph with $k$ connected components has $2^k$ bicolorings. (In nonenumerative contexts the distinction between bipartite and bicolored is usually unimportant.) In addition, in counting bicolored graphs one might or might not consider switching the two colors to give an equivalent graph. All of the versions of the enumeration problem have been solved. Counting unlabeled bicolored graphs (with no color-switching equivalence) is a straightforward application of Burnside's lemma; counting unlabeled bipartite graphs is tricky.
It's not too hard to find appropriate references by searching MathSciNet. (Hint: "color" is sometimes spelled "colour".)
Incidentally, the number of labeled bicolored graphs on $n$ vertices is $$\sum_{m=0}^n 2^{m(n-m)}\binom{n}{m}.$$
Best Answer
The vast majority of disconnected graphs have a single isolated vertex.
Let $A$ be a nonempty proper subset of $\{1,...,n\}$ of size $a$. Let $s(a)$ be the number of graphs with $e=\lfloor \frac12 {n \choose 2}\rfloor$ edges which have no edges from $A$ to $A^c$.
We want to count the union of all of these. Inclusion-exclusion works, with the dominant terms coming from when $a=1$.
An upper bound is the sum of $s(a)$ over all $A$ of size at most $n/2$, which is at most $n ~s(1)$ + ${n\choose 2}s(1)$ + $2^ns(3)$.
To get a lower bound, subtract the number of graphs with no edges connecting $A$ to $A^c$ or edges connecting $B$ to $B^c$ for all disjoint $\{A,B\}$. Denote this by $s(\#A,\#B)$. So, subtract
${n\choose2}s(1,1) + 3^ns(1,2)$ from $n~s(1)$.
The rest should be routine estimates on $s(1)$, $s(2)$, $s(3)$, $s(1,1)$, and $s(1,2)$.
$s(a,b) \le s(a+b)$.
$s(a) = ({n\choose 2} -a(n-a))$ choose $e$.
Let the total number of graphs with $e$ edges be $\#G = s(0)$.
$$s(a)/\#G = \prod_{i=0}^{a(n-a)-1} \frac{\lceil{n\choose2}/2\rceil-i}{{n\choose2}-i}.$$
$s(2)/s(1) \le 2^{-n+3}$.
$s(3)/s(1) \le 2^{-2n+8}$.
The dominant term in both the upper bound and the lower bound is $n~s(1)$.
If I calculated correctly, that's asymptotic to $\frac 2 e n 2^{-n} ~\#G$.