<p>This book will be helpful:</p>

<p><a href="http://books.google.co.uk/books/about/Extremal_combinatorics.html?id=g6X2VWuB8qIC" rel="nofollow">http://books.google.co.uk/books/about/Extremal_combinatorics.html?id=g6X2VWuB8qIC</a></p>

CC BY-SA 3.0
2012-03-25T19:36:11.617Z
Yeah,thanks for mention the book. I have got one
Yao Wang
CC BY-SA 3.0
2012-03-23T15:51:46.970Z
2012-03-23T15:51:46.970Z
h.a
<p>another book by stasys jukna[1] who was cited in the other answer has some key "applications". as always applications can be subjective, but in TCS a key application many would agree on is complexity class separations. there are about 30 references to ramsey graphs in this book as counted by a pdf search.</p>

<p>jukna makes the case that ramsey theory is about large structures guaranteed to contain some kind of "feature" and these can be shown to exist by shannon-style or shannon-reminiscent counting arguments, but building <em>explicit</em> constructions is very difficult and rarely accomplished in the literature. this is apparently highly analogous, possibly even directly linked, to the inability to explicitly construct complex circuits even though they are known to exist. construction of such circuits is key in complexity class separations. this is further emphasized by constructions in juknas book that directly tie graph complexity to complexity class separations (although so far not directly through ramsey graphs).</p>

<p>therefore this (same?/crosscutting?) phenomenon seems to be something like the "dark matter" of computer science. it is known to be there, it can be indirectly measured, but cannot be directly exhibited so to speak, and it is yet mysterious. jukna implies ramsey type thms or constructions could possibly be a bridge-type thm for complexity class separations (see sec 1.7).</p>

<p>see also sec 1.5, "where are all the complex functions"? however it is not so straightfwd, in constrast see also sec 11.7 where he uses ramsey graphs to show how "combinatorially complicated" graphs eg ramsey graphs are not nec "computationally complicated".</p>

<p>[1] Boolean function complexity, Advances and Frontiers by Stasys Jukna, 2011</p>

CC BY-SA 3.0
2012-03-28T15:09:43.530Z
2012-03-28T15:09:43.530Z
vzn
<p>The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory.</p>

<p>Or rather than being applied to TCS, the enumerative combinatorics or Ramsey theory is related to TCS because we use TCS techs and algorithms to tackle their problems.</p>

<p>I dont know very deep theory works, so please treat it easy.</p>

CC BY-SA 3.0
2012-03-23T02:13:34.487Z
http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html
Huck Bennett
CC BY-SA 3.0
2012-03-23T03:18:18.837Z
Exactly what I am seeking for. Thanks much.@Huck. Moreover,enumerative combinatorics seems has a natural relations with #P-problems. Does it helps with research on #P? say dichotomy of complexity.
Yao Wang
CC BY-SA 3.0
2012-03-23T09:27:54.513Z
Enumerative combinatorics is the basis of the study of average complexity of algorithms and data stuctures. See http://algo.inria.fr/flajolet/Publications/ViFl90.pdf for example.
Lamine
CC BY-SA 3.0
2012-03-23T14:15:46.160Z
@Lamine another part of what I need. Thanks much. Very impressive detailed content
Yao Wang
CC BY-SA 3.0
2012-03-29T20:46:16.950Z
You might want to hunt around the [ramsey-theory tag](http://cstheory.stackexchange.com/questions/tagged/ramsey-theory) and also take a look at [this question on applications of ramsey theory](http://cstheory.stackexchange.com/q/9500/1037).
Artem Kaznatcheev
<co.combinatorics><soft-question><big-list>
Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?
Yao Wang
# Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?

(Asked by: username_0 on 2012-03-23)

The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory.

Or rather than being applied to TCS, the enumerative combinatorics or Ramsey theory is related to TCS because we use TCS techs and algorithms to tackle their problems.

I dont know very deep theory works, so please treat it easy.

**Tags:** co.combinatorics, soft-question, big-list

> **Comments:**
> **username_1**: http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html  
> **username_0**: Exactly what I am seeking for. Thanks much.@Huck. Moreover,enumerative combinatorics seems has a natural relations with #P-problems. Does it helps with research on #P? say dichotomy of complexity.  
> **username_2**: Enumerative combinatorics is the basis of the study of average complexity of algorithms and data stuctures. See http://algo.inria.fr/flajolet/Publications/ViFl90.pdf for example.  
> **username_0**: @username_2 another part of what I need. Thanks much. Very impressive detailed content  
> **username_3**: You might want to hunt around the [ramsey-theory tag](http://cstheory.stackexchange.com/questions/tagged/ramsey-theory) and also take a look at [this question on applications of ramsey theory](http://cstheory.stackexchange.com/q/9500/1037).  

---

## 2 answers

### Answer by username_4 on 2012-03-23. Score: 3

This book will be helpful:

<http://books.google.co.uk/books/about/Extremal_combinatorics.html?id=g6X2VWuB8qIC>

> **Comments:**
> **username_0**: Yeah,thanks for mention the book. I have got one  

---

### Answer by username_5 on 2012-03-28. Score: 0

another book by stasys jukna[1] who was cited in the other answer has some key "applications". as always applications can be subjective, but in TCS a key application many would agree on is complexity class separations. there are about 30 references to ramsey graphs in this book as counted by a pdf search.

jukna makes the case that ramsey theory is about large structures guaranteed to contain some kind of "feature" and these can be shown to exist by shannon-style or shannon-reminiscent counting arguments, but building *explicit* constructions is very difficult and rarely accomplished in the literature. this is apparently highly analogous, possibly even directly linked, to the inability to explicitly construct complex circuits even though they are known to exist. construction of such circuits is key in complexity class separations. this is further emphasized by constructions in juknas book that directly tie graph complexity to complexity class separations (although so far not directly through ramsey graphs).

therefore this (same?/crosscutting?) phenomenon seems to be something like the "dark matter" of computer science. it is known to be there, it can be indirectly measured, but cannot be directly exhibited so to speak, and it is yet mysterious. jukna implies ramsey type thms or constructions could possibly be a bridge-type thm for complexity class separations (see sec 1.7).

see also sec 1.5, "where are all the complex functions"? however it is not so straightfwd, in constrast see also sec 11.7 where he uses ramsey graphs to show how "combinatorially complicated" graphs eg ramsey graphs are not nec "computationally complicated".

[1] Boolean function complexity, Advances and Frontiers by Stasys Jukna, 2011


---

