MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true that

Almost all bipartite graphs of order $2n$ have bipartitons of size $n$?

Is there any known result of this type? Is there anything related to other invariants in almost all bipartite graphs (max degree, number of edges)?

Also, as far as I know there are no asymptotic enumerations of the number of bipartite graphs hence I am wondering if there are any (nontrivial) upper/lower bounds for the number of bipartite graphs of order $n,$ perhaps taking other invariants into account as well?

share|cite|improve this question
You may want to parameterize "almost all". In particular you might specify which properties and which small functions f such that failure of a property occurs for at most f(1/n) percentage of graphs of order n. For general algebraic structures, some work has been done by Freese "two kinds of probability in algebra" and others. Doing an iterated citation search starting with Freese's 1990 paper may be fruitful. Gerhard "Ask Me About System Design" Paseman, 2012.12.20 – Gerhard Paseman Dec 20 '12 at 17:57
Look up "random bipartite graph", but beware that most of the time the bipartition is fixed and only the edges are randomly chosen. A rough calculation indicates that some constant fraction (strictly between 0 and 1) of all bipartite graphs of order $2n$ have a bipartition with both parts of size $n$. Almost all of them have a bipartition with parts of size between $n-j(n)$ and $n+j(n)$, for any increasing function $j(n)$. – Brendan McKay Dec 20 '12 at 22:47
This question seems related to mine:… – domotorp Dec 21 '12 at 0:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.