# Ramsey Number Lower Bound

DevFeed: [Ramsey Number Lower Bound](<https://devfeed.tech/articles/ramsey-number-lower-bound-40293.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/12/02/ramsey-number-lower-bound/>)

Published: 2012-12-02T15:17:26Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [combinatorics](<https://devfeed.tech/tags/combinatorics.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [number-theory](<https://devfeed.tech/tags/number-theory.md>), [probabilistic-method](<https://devfeed.tech/tags/probabilistic-method.md>), [ramsey-numbers](<https://devfeed.tech/tags/ramsey-numbers.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>)

## AI overview

The article proves a lower bound for the diagonal Ramsey number R(m,m). By randomly coloring the edges of a complete graph, it shows that if binom(n,m)2^(1−binom(m,2)) is less than 1, there exists a coloring with no monochromatic m-vertex subgraph, so R(m,m) > n.

## Source excerpt

Define the Ramsey number $ R(k,m)$ to be the minimum number $ n$ of vertices required of the complete graph $ K_n$ so that for any two-coloring (red, blue) of the edges of $ K_n$ one of two things will happen: There is a red $ k$-clique; that is, a complete subgraph of $ k$ vertices for which all edges are red. There is a blue $ m$-clique. It is known that these numbers are always finite, but it is very difficult to compute them exactly.