Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T02:51:59.565Z Has data issue: false hasContentIssue false

On the Evolution of Triangle-Free Graphs

Published online by Cambridge University Press:  15 February 2005

ANGELIKA STEGER
Affiliation:
Institute of Theoretical Computer Science, ETH Zürich, 8092 Zürich, Switzerland (e-mail: steger@inf.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let ${\cal T}(n,m)$ denote the set of all labelled triangle-free graphs with $n$ vertices and exactly $m$ edges. In this paper we give a short self-contained proof of the fact that there exists a constant $C>0$ such that, for all $m\geq Cn^{3/2}\sqrt{\log n}$, a graph chosen uniformly at random from ${\cal T}(n,m)$ is with probability $1-o(1)$ bipartite.

Information

Type
Paper
Copyright
© 2005 Cambridge University Press