Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 Mar 23 '12 at 3:18
Enumerative combinatorics is the basis of the study of average complexity of algorithms and data stuctures. See algo.inria.fr/flajolet/Publications/ViFl90.pdf for example. –  Lamine Mar 23 '12 at 9:27
@Lamine another part of what I need. Thanks much. Very impressive detailed content –  Yao Wang Mar 23 '12 at 14:15
You might want to hunt around the ramsey-theory tag and also take a look at this question on applications of ramsey theory. –  Artem Kaznatcheev Mar 29 '12 at 20:46
add comment

2 Answers

This book will be helpful:


share|improve this answer
Yeah,thanks for mention the book. I have got one –  Yao Wang Mar 25 '12 at 19:36
add comment

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

share|improve this answer
add comment

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.